From 8c50a7afd401686f645fb26676fbcaedb8d4ab62 Mon Sep 17 00:00:00 2001 From: Daniel Eklöf Date: Thu, 25 Nov 2021 19:22:52 +0100 Subject: osc8: update URI ranges as we print data, *not* when the URI is closed MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit At first, an OSC-8 URI range was added when we received the closing OSC-8 escape (i.e. with an empty URI). But, this meant that cursor movements while the OSC-8 escape was in effect wasn’t handled correctly, since we’d add a range that spanned the cursor movements. Attempts were made to handle this in the cursor movement functions, by closing and re-opening the URI. However, there are too many corner cases to make this a viable approach. Scrolling is one such example, line-wrapping another. This patch takes a different approach; emit, or update the URI range when we print to the grid. This models the intended behavior much more closely, where an active OSC-8 URI act like any other SGR attribute - it is applied to all cells printed to, but otherwise have no effect. To avoid killing performance, this is only done in the “generic” printer. This means OSC-8 open/close calls must now “switch” the ASCII printer. Note that the “fast” printer still needs to *erase* pre-existing OSC-8 URIs. Closes #816 --- grid.c | 152 ++++++++++++++++++++++++++++++++++++++++++++++++++--------------- 1 file changed, 117 insertions(+), 35 deletions(-) (limited to 'grid.c') diff --git a/grid.c b/grid.c index 459fa369..2dcbaa55 100644 --- a/grid.c +++ b/grid.c @@ -844,6 +844,117 @@ ensure_row_has_extra_data(struct row *row) row->extra = xcalloc(1, sizeof(*row->extra)); } +static void +verify_no_overlapping_uris(const struct row *row) +{ +#if defined(_DEBUG) + const struct row_data *extra = row->extra; + tll_foreach(extra->uri_ranges, it1) { + const struct row_uri_range *r1 = &it1->item; + + tll_foreach(extra->uri_ranges, it2) { + const struct row_uri_range *r2 = &it2->item; + + if (r1 == r2) + continue; + + if ((r1->start <= r2->start && r1->end >= r2->start) || + (r1->start <= r2->end && r1->end >= r2->end)) + { + BUG("OSC-8 URI overlap: %s: %d-%d: %s: %d-%d", + r1->uri, r1->start, r1->end, + r2->uri, r2->start, r2->end); + } + } + } +#endif +} + +void +grid_row_uri_range_put(struct row *row, int col, const char *uri, uint64_t id) +{ + ensure_row_has_extra_data(row); + + struct row_data *extra = row->extra; + tll_rforeach(extra->uri_ranges, it) { + struct row_uri_range *r = &it->item; + + if (r->end + 1 < col) { + /* Ranges are sorted, and this means all the remaining + * URIs *end* before ‘col’ */ + break; + } + + if (r->start <= col && r->end >= col) { + /* + * ‘col’ is *inside* an existing range + */ + + if (r->id == id) { + /* ‘col’ is already inside a matching URI range */ + goto out; + } + + /* Splice old range */ + if (r->start == r->end) + tll_remove(extra->uri_ranges, it); + else if (r->start == col) + r->start++; + else if (r->end == col) + r->end--; + else { + xassert(r->start < col); + xassert(r->end > col); + + struct row_uri_range new_tail = { + .start = col + 1, + .end = r->end, + .id = r->id, + .uri = xstrdup(r->uri), + }; + + r->end = col - 1; + + xassert(r->start <= r->end); + xassert(new_tail.start <= new_tail.end); + + tll_insert_after(extra->uri_ranges, it, new_tail); + } + + break; /* Break out add and a new range for ‘col’ */ + } + + else if (r->id != id) + continue; + +#if 0 /* Trust the URI ID, for now... */ + if (strcmp(r->uri, uri) != 0) + continue; +#endif + + else if (likely(r->end + 1 == col)) { + r->end = col; + goto out; + } + + else if (col + 1 == r->start) { + r->start = col; + goto out; + } + } + + struct row_uri_range new_range = { + .start = col, + .end = col, + .id = id, + .uri = xstrdup(uri), + }; + grid_row_uri_range_add(row, new_range); + +out: + verify_no_overlapping_uris(row); +} + void grid_row_uri_range_add(struct row *row, struct row_uri_range range) { @@ -858,20 +969,7 @@ grid_row_uri_range_add(struct row *row, struct row_uri_range range) tll_push_front(row->extra->uri_ranges, range); out: - ; -#if defined(_DEBUG) - tll_foreach(row->extra->uri_ranges, it1) { - tll_foreach(row->extra->uri_ranges, it2) { - if (&it1->item == &it2->item) - continue; - - xassert(it1->item.start != it2->item.start); - xassert(it1->item.start != it2->item.end); - xassert(it1->item.end != it2->item.start); - xassert(it1->item.end != it2->item.end); - } - } -#endif + verify_no_overlapping_uris(row); } void @@ -929,36 +1027,22 @@ UNITTEST struct row_data row_data = {.uri_ranges = tll_init()}; struct row row = {.extra = &row_data}; -#define row_has_no_overlapping_uris(row) \ - do { \ - tll_foreach((row)->extra->uri_ranges, it1) { \ - tll_foreach((row)->extra->uri_ranges, it2) { \ - if (&it1->item == &it2->item) \ - continue; \ - xassert(it1->item.start != it2->item.start); \ - xassert(it1->item.start != it2->item.end); \ - xassert(it1->item.end != it2->item.start); \ - xassert(it1->item.end != it2->item.end); \ - } \ - } \ - } while (0) - grid_row_uri_range_add(&row, (struct row_uri_range){1, 10}); xassert(tll_length(row_data.uri_ranges) == 1); xassert(tll_front(row_data.uri_ranges).start == 1); xassert(tll_front(row_data.uri_ranges).end == 10); - row_has_no_overlapping_uris(&row); + verify_no_overlapping_uris(&row); grid_row_uri_range_add(&row, (struct row_uri_range){11, 20}); xassert(tll_length(row_data.uri_ranges) == 2); xassert(tll_back(row_data.uri_ranges).start == 11); xassert(tll_back(row_data.uri_ranges).end == 20); - row_has_no_overlapping_uris(&row); + verify_no_overlapping_uris(&row); /* Erase both URis */ grid_row_uri_range_erase(&row, 1, 20); xassert(tll_length(row_data.uri_ranges) == 0); - row_has_no_overlapping_uris(&row); + verify_no_overlapping_uris(&row); /* Two URIs, then erase second half of the first, first half of the second */ @@ -970,7 +1054,7 @@ UNITTEST xassert(tll_front(row_data.uri_ranges).end == 4); xassert(tll_back(row_data.uri_ranges).start == 16); xassert(tll_back(row_data.uri_ranges).end == 20); - row_has_no_overlapping_uris(&row); + verify_no_overlapping_uris(&row); tll_pop_back(row_data.uri_ranges); tll_pop_back(row_data.uri_ranges); @@ -984,9 +1068,7 @@ UNITTEST xassert(tll_front(row_data.uri_ranges).end == 4); xassert(tll_back(row_data.uri_ranges).start == 7); xassert(tll_back(row_data.uri_ranges).end == 10); - row_has_no_overlapping_uris(&row); - -#undef row_has_no_overlapping_uris + verify_no_overlapping_uris(&row); tll_free(row_data.uri_ranges); } -- cgit v1.3 From ccee08a393f4c55994e921b43a16f5942816d764 Mon Sep 17 00:00:00 2001 From: Daniel Eklöf Date: Fri, 26 Nov 2021 19:55:27 +0100 Subject: osc8: uri ranges: use a dynamically re-sizable array instead of a tllist --- grid.c | 404 ++++++++++++++++++++++++++++++++++++++++++++----------------- grid.h | 13 +- terminal.h | 6 +- url-mode.c | 15 ++- 4 files changed, 317 insertions(+), 121 deletions(-) (limited to 'grid.c') diff --git a/grid.c b/grid.c index 2dcbaa55..e1b7ce38 100644 --- a/grid.c +++ b/grid.c @@ -49,19 +49,26 @@ grid_snapshot(const struct grid *grid) if (row->extra != NULL) { const struct row_data *extra = row->extra; - struct row_data *new_extra = xcalloc(1, sizeof(*new_extra)); - - tll_foreach(extra->uri_ranges, it) { - struct row_uri_range range = { - .start = it->item.start, - .end = it->item.end, - .id = it->item.id, - .uri = xstrdup(it->item.uri), + struct row_data *new_extra = xmalloc(sizeof(*new_extra)); + struct row_uri_range *ranges = + xmalloc(extra->uri_ranges.count * sizeof(ranges[0])); + + for (size_t i = 0; i < extra->uri_ranges.count; i++) { + const struct row_uri_range *range = &extra->uri_ranges.v[i]; + + ranges[i] = (struct row_uri_range){ + .start = range->start, + .end = range->end, + .id = range->id, + .uri = xstrdup(range->uri), }; - tll_push_back(new_extra->uri_ranges, range); } + new_extra->uri_ranges.v = ranges; + new_extra->uri_ranges.size = extra->uri_ranges.count; + new_extra->uri_ranges.count = extra->uri_ranges.count; + clone_row->extra = new_extra; } else clone_row->extra = NULL; @@ -224,17 +231,20 @@ grid_resize_without_reflow( if (old_row->extra == NULL) continue; - tll_foreach(old_row->extra->uri_ranges, it) { - if (it->item.start >= new_rows) { + for (size_t i = 0; i < old_row->extra->uri_ranges.count; i++) { + const struct row_uri_range *old_range = + &old_row->extra->uri_ranges.v[i]; + + if (old_range->start >= new_rows) { /* The whole range is truncated */ continue; } struct row_uri_range range = { - .start = it->item.start, - .end = min(it->item.end, new_cols - 1), - .id = it->item.id, - .uri = xstrdup(it->item.uri), + .start = old_range->start, + .end = min(old_range->end, new_cols - 1), + .id = old_range->id, + .uri = xstrdup(old_range->uri), }; grid_row_uri_range_add(new_row, range); } @@ -310,8 +320,11 @@ static void reflow_uri_range_end(struct row_uri_range *range, struct row *new_row, int new_col_idx) { - xassert(tll_length(new_row->extra->uri_ranges) > 0); - struct row_uri_range *new_range = &tll_back(new_row->extra->uri_ranges); + struct row_data *extra = new_row->extra; + xassert(extra->uri_ranges.count > 0); + + struct row_uri_range *new_range = + &extra->uri_ranges.v[extra->uri_ranges.count - 1]; xassert(new_range->id == range->id); xassert(new_range->end < 0); @@ -344,7 +357,8 @@ _line_wrap(struct grid *old_grid, struct row **new_grid, struct row *row, } } - if (row->extra == NULL) + struct row_data *extra = row->extra; + if (extra == NULL) return new_row; /* @@ -352,8 +366,10 @@ _line_wrap(struct grid *old_grid, struct row **new_grid, struct row *row, * ranges on the previous row, and re-open them on the * next/current row. */ - if (tll_length(row->extra->uri_ranges) > 0) { - struct row_uri_range *range = &tll_back(row->extra->uri_ranges); + if (extra->uri_ranges.count > 0) { + struct row_uri_range *range = + &extra->uri_ranges.v[extra->uri_ranges.count - 1]; + if (range->end < 0) { /* Terminate URI range on the previous row */ @@ -550,12 +566,15 @@ grid_resize_and_reflow( /* Does this row have any URIs? */ struct row_uri_range *range; - if (old_row->extra != NULL && tll_length(old_row->extra->uri_ranges) > 0) { - range = &tll_front(old_row->extra->uri_ranges); + struct row_data *extra = old_row->extra; + size_t uri_range_idx = 0; + + if (extra != NULL && extra->uri_ranges.count > 0) { + range = &extra->uri_ranges.v[uri_range_idx]; /* Make sure the *last* URI range's end point is included in the copy */ const struct row_uri_range *last_on_row = - &tll_back(old_row->extra->uri_ranges); + &extra->uri_ranges.v[extra->uri_ranges.count - 1]; col_count = max(col_count, last_on_row->end + 1); } else range = NULL; @@ -703,12 +722,13 @@ grid_resize_and_reflow( if (range->end == end - 1) { reflow_uri_range_end(range, new_row, new_col_idx - 1); - xassert(&tll_front(old_row->extra->uri_ranges) == range); + xassert(&extra->uri_ranges.v[uri_range_idx] == range); grid_row_uri_range_destroy(range); - tll_pop_front(old_row->extra->uri_ranges); - range = tll_length(old_row->extra->uri_ranges) > 0 - ? &tll_front(old_row->extra->uri_ranges) + uri_range_idx++; + + range = uri_range_idx < extra->uri_ranges.count + ? &old_row->extra->uri_ranges.v[uri_range_idx] : NULL; } } @@ -752,8 +772,8 @@ grid_resize_and_reflow( if (row->extra == NULL) continue; - tll_foreach(row->extra->uri_ranges, it) - xassert(it->item.end >= 0); + for (size_t i = 0; i < row->extra->uri_ranges.count; i++) + xassert(row->extra->uri_ranges.v[i].end >= 0); } /* Verify all old rows have been free:d */ @@ -849,14 +869,12 @@ verify_no_overlapping_uris(const struct row *row) { #if defined(_DEBUG) const struct row_data *extra = row->extra; - tll_foreach(extra->uri_ranges, it1) { - const struct row_uri_range *r1 = &it1->item; - - tll_foreach(extra->uri_ranges, it2) { - const struct row_uri_range *r2 = &it2->item; + for (size_t i = 0; i < extra->uri_ranges.count; i++) { + const struct row_uri_range *r1 = &extra->uri_ranges.v[i]; - if (r1 == r2) - continue; + for (size_t j = i + 1; j < extra->uri_ranges.count; j++) { + const struct row_uri_range *r2 = &extra->uri_ranges.v[j]; + xassert(r1 != r2); if ((r1->start <= r2->start && r1->end >= r2->start) || (r1->start <= r2->end && r1->end >= r2->end)) @@ -870,39 +888,129 @@ verify_no_overlapping_uris(const struct row *row) #endif } +static void +verify_uris_are_sorted(const struct row *row) +{ +#if defined(_DEBUG) + const struct row_data *extra = row->extra; + const struct row_uri_range *last = NULL; + + for (size_t i = 0; i < extra->uri_ranges.count; i++) { + const struct row_uri_range *r = &extra->uri_ranges.v[i]; + + if (last != NULL) { + if (last->start >= r->start || last->end >= r->end) { + BUG("OSC-8 URI not sorted correctly: " + "%s: %d-%d came before %s: %d-%d", + last->uri, last->start, last->end, + r->uri, r->start, r->end); + } + } + + last = r; + } +#endif +} + +static void +uri_range_ensure_size(struct row_data *extra, size_t count_to_add) +{ + if (extra->uri_ranges.count + count_to_add > extra->uri_ranges.size) { + extra->uri_ranges.size += count_to_add + 4; + extra->uri_ranges.v = xrealloc( + extra->uri_ranges.v, + extra->uri_ranges.size * sizeof(extra->uri_ranges.v[0])); + } + + xassert(extra->uri_ranges.count + count_to_add <= extra->uri_ranges.size); +} + +static void +uri_range_insert(struct row_data *extra, size_t idx, struct row_uri_range range) +{ + uri_range_ensure_size(extra, 1); + + xassert(idx <= extra->uri_ranges.count); + + const size_t move_count = extra->uri_ranges.count - idx; + memmove(&extra->uri_ranges.v[idx + 1], + &extra->uri_ranges.v[idx], + move_count * sizeof(extra->uri_ranges.v[0])); + + extra->uri_ranges.v[idx] = range; + extra->uri_ranges.count++; +} + +#if 0 +static void +uri_range_append(struct row_data *extra, struct row_uri_range range) +{ + uri_range_ensure_size(extra, 1); + extra->uri_ranges.v[extra->uri_ranges.count++] = range; +} +#endif +static void +uri_range_delete(struct row_data *extra, size_t idx) +{ + xassert(idx < extra->uri_ranges.count); + grid_row_uri_range_destroy(&extra->uri_ranges.v[idx]); + + const size_t move_count = extra->uri_ranges.count - idx - 1; + memmove(&extra->uri_ranges.v[idx], + &extra->uri_ranges.v[idx + 1], + move_count * sizeof(extra->uri_ranges.v[0])); + extra->uri_ranges.count--; +} + void grid_row_uri_range_put(struct row *row, int col, const char *uri, uint64_t id) { ensure_row_has_extra_data(row); + size_t insert_idx = 0; + bool replace = false; + bool run_merge_pass = false; + struct row_data *extra = row->extra; - tll_rforeach(extra->uri_ranges, it) { - struct row_uri_range *r = &it->item; + for (ssize_t i = (ssize_t)extra->uri_ranges.count - 1; i >= 0; i--) { + struct row_uri_range *r = &extra->uri_ranges.v[i]; - if (r->end + 1 < col) { - /* Ranges are sorted, and this means all the remaining - * URIs *end* before ‘col’ */ + const bool matching_id = r->id == id; + + if (matching_id && r->end + 1 == col) { + /* Extend existing URI’s tail */ + r->end++; + goto out; + } + + else if (r->end < col) { + insert_idx = i + 1; break; } - if (r->start <= col && r->end >= col) { - /* - * ‘col’ is *inside* an existing range - */ + else if (r->start > col) + continue; + + else { + xassert(r->start <= col); + xassert(r->end >= col); - if (r->id == id) { - /* ‘col’ is already inside a matching URI range */ + if (matching_id) goto out; - } - /* Splice old range */ - if (r->start == r->end) - tll_remove(extra->uri_ranges, it); - else if (r->start == col) + if (r->start == r->end) { + replace = true; + run_merge_pass = true; + insert_idx = i; + } else if (r->start == col) { + run_merge_pass = true; r->start++; - else if (r->end == col) + insert_idx = i; + } else if (r->end == col) { + run_merge_pass = true; r->end--; - else { + insert_idx = i + 1; + } else { xassert(r->start < col); xassert(r->end > col); @@ -912,34 +1020,17 @@ grid_row_uri_range_put(struct row *row, int col, const char *uri, uint64_t id) .id = r->id, .uri = xstrdup(r->uri), }; + xassert(new_tail.start <= new_tail.end); - r->end = col - 1; + uri_range_insert(extra, i + 1, new_tail); + r->end = col - 1; xassert(r->start <= r->end); - xassert(new_tail.start <= new_tail.end); - tll_insert_after(extra->uri_ranges, it, new_tail); + insert_idx = i + 1; } - break; /* Break out add and a new range for ‘col’ */ - } - - else if (r->id != id) - continue; - -#if 0 /* Trust the URI ID, for now... */ - if (strcmp(r->uri, uri) != 0) - continue; -#endif - - else if (likely(r->end + 1 == col)) { - r->end = col; - goto out; - } - - else if (col + 1 == r->start) { - r->start = col; - goto out; + break; } } @@ -949,27 +1040,119 @@ grid_row_uri_range_put(struct row *row, int col, const char *uri, uint64_t id) .id = id, .uri = xstrdup(uri), }; - grid_row_uri_range_add(row, new_range); + + xassert(insert_idx >= 0); + xassert(insert_idx <= extra->uri_ranges.count); + + if (replace) { + grid_row_uri_range_destroy(&extra->uri_ranges.v[insert_idx]); + extra->uri_ranges.v[insert_idx] = new_range; + } else + uri_range_insert(extra, insert_idx, new_range); + + if (run_merge_pass) { + for (size_t i = 1; i < extra->uri_ranges.count; i++) { + struct row_uri_range *r1 = &extra->uri_ranges.v[i - 1]; + struct row_uri_range *r2 = &extra->uri_ranges.v[i]; + + if (r1->id == r2->id && r1->end + 1 == r2->start) { + r1->end = r2->end; + uri_range_delete(extra, i); + i--; + } + } + } out: verify_no_overlapping_uris(row); + verify_uris_are_sorted(row); +} + +UNITTEST +{ + struct row_data row_data = {.uri_ranges = {0}}; + struct row row = {.extra = &row_data}; + +#define verify_range(idx, _start, _end, _id) \ + do { \ + xassert(idx < row_data.uri_ranges.count); \ + xassert(row_data.uri_ranges.v[idx].start == _start); \ + xassert(row_data.uri_ranges.v[idx].end == _end); \ + xassert(row_data.uri_ranges.v[idx].id == _id); \ + } while (0) + + grid_row_uri_range_put(&row, 0, "http://foo.bar", 123); + grid_row_uri_range_put(&row, 1, "http://foo.bar", 123); + grid_row_uri_range_put(&row, 2, "http://foo.bar", 123); + grid_row_uri_range_put(&row, 3, "http://foo.bar", 123); + xassert(row_data.uri_ranges.count == 1); + verify_range(0, 0, 3, 123); + + /* No-op */ + grid_row_uri_range_put(&row, 0, "http://foo.bar", 123); + xassert(row_data.uri_ranges.count == 1); + verify_range(0, 0, 3, 123); + + /* Replace head */ + grid_row_uri_range_put(&row, 0, "http://head", 456); + xassert(row_data.uri_ranges.count == 2); + verify_range(0, 0, 0, 456); + verify_range(1, 1, 3, 123); + + /* Replace tail */ + grid_row_uri_range_put(&row, 3, "http://tail", 789); + xassert(row_data.uri_ranges.count == 3); + verify_range(1, 1, 2, 123); + verify_range(2, 3, 3, 789); + + /* Replace tail + extend head */ + grid_row_uri_range_put(&row, 2, "http://tail", 789); + xassert(row_data.uri_ranges.count == 3); + verify_range(1, 1, 1, 123); + verify_range(2, 2, 3, 789); + + /* Replace + extend tail */ + grid_row_uri_range_put(&row, 1, "http://head", 456); + xassert(row_data.uri_ranges.count == 2); + verify_range(0, 0, 1, 456); + verify_range(1, 2, 3, 789); + + /* Replace + extend, then splice */ + grid_row_uri_range_put(&row, 1, "http://tail", 789); + grid_row_uri_range_put(&row, 2, "http://splice", 000); + xassert(row_data.uri_ranges.count == 4); + verify_range(0, 0, 0, 456); + verify_range(1, 1, 1, 789); + verify_range(2, 2, 2, 000); + verify_range(3, 3, 3, 789); + + for (size_t i = 0; i < row_data.uri_ranges.count; i++) + grid_row_uri_range_destroy(&row_data.uri_ranges.v[i]); + free(row_data.uri_ranges.v); + +#undef verify_range } void grid_row_uri_range_add(struct row *row, struct row_uri_range range) { ensure_row_has_extra_data(row); - tll_rforeach(row->extra->uri_ranges, it) { - if (it->item.end < range.start) { - tll_insert_after(row->extra->uri_ranges, it, range); + struct row_data *extra = row->extra; + + for (ssize_t i = (ssize_t)extra->uri_ranges.count - 1; i >= 0; i--) { + const struct row_uri_range *r = &extra->uri_ranges.v[i]; + + if (r->end < range.start) { + uri_range_insert(extra, i + 1, range); goto out; } } - tll_push_front(row->extra->uri_ranges, range); + uri_range_insert(extra, 0, range); out: verify_no_overlapping_uris(row); + verify_uris_are_sorted(row); } void @@ -978,9 +1161,11 @@ grid_row_uri_range_erase(struct row *row, int start, int end) xassert(row->extra != NULL); xassert(start <= end); + struct row_data *extra = row->extra; + /* Split up, or remove, URI ranges affected by the erase */ - tll_foreach(row->extra->uri_ranges, it) { - struct row_uri_range *old = &it->item; + for (ssize_t i = 0; i < extra->uri_ranges.count; i++) { + struct row_uri_range *old = &extra->uri_ranges.v[i]; if (old->end < start) continue; @@ -990,8 +1175,8 @@ grid_row_uri_range_erase(struct row *row, int start, int end) if (start <= old->start && end >= old->end) { /* Erase range covers URI completely - remove it */ - grid_row_uri_range_destroy(old); - tll_remove(row->extra->uri_ranges, it); + uri_range_delete(extra, i); + i--; } else if (start > old->start && end < old->end) { @@ -1002,7 +1187,7 @@ grid_row_uri_range_erase(struct row *row, int start, int end) .id = old->id, .uri = old->uri != NULL ? xstrdup(old->uri) : NULL, }; - tll_insert_after(row->extra->uri_ranges, it, old_tail); + uri_range_insert(extra, i + 1, old_tail); old->end = start - 1; return; /* There can be no more URIs affected by the erase range */ } @@ -1024,51 +1209,54 @@ grid_row_uri_range_erase(struct row *row, int start, int end) UNITTEST { - struct row_data row_data = {.uri_ranges = tll_init()}; + struct row_data row_data = {.uri_ranges = {0}}; struct row row = {.extra = &row_data}; grid_row_uri_range_add(&row, (struct row_uri_range){1, 10}); - xassert(tll_length(row_data.uri_ranges) == 1); - xassert(tll_front(row_data.uri_ranges).start == 1); - xassert(tll_front(row_data.uri_ranges).end == 10); + xassert(row_data.uri_ranges.count == 1); + xassert(row_data.uri_ranges.v[0].start == 1); + xassert(row_data.uri_ranges.v[0].end == 10); verify_no_overlapping_uris(&row); + verify_uris_are_sorted(&row); grid_row_uri_range_add(&row, (struct row_uri_range){11, 20}); - xassert(tll_length(row_data.uri_ranges) == 2); - xassert(tll_back(row_data.uri_ranges).start == 11); - xassert(tll_back(row_data.uri_ranges).end == 20); + xassert(row_data.uri_ranges.count == 2); + xassert(row_data.uri_ranges.v[1].start == 11); + xassert(row_data.uri_ranges.v[1].end == 20); verify_no_overlapping_uris(&row); + verify_uris_are_sorted(&row); /* Erase both URis */ grid_row_uri_range_erase(&row, 1, 20); - xassert(tll_length(row_data.uri_ranges) == 0); + xassert(row_data.uri_ranges.count == 0); verify_no_overlapping_uris(&row); + verify_uris_are_sorted(&row); /* Two URIs, then erase second half of the first, first half of the second */ grid_row_uri_range_add(&row, (struct row_uri_range){1, 10}); grid_row_uri_range_add(&row, (struct row_uri_range){11, 20}); grid_row_uri_range_erase(&row, 5, 15); - xassert(tll_length(row_data.uri_ranges) == 2); - xassert(tll_front(row_data.uri_ranges).start == 1); - xassert(tll_front(row_data.uri_ranges).end == 4); - xassert(tll_back(row_data.uri_ranges).start == 16); - xassert(tll_back(row_data.uri_ranges).end == 20); + xassert(row_data.uri_ranges.count == 2); + xassert(row_data.uri_ranges.v[0].start == 1); + xassert(row_data.uri_ranges.v[0].end == 4); + xassert(row_data.uri_ranges.v[1].start == 16); + xassert(row_data.uri_ranges.v[1].end == 20); verify_no_overlapping_uris(&row); + verify_uris_are_sorted(&row); - tll_pop_back(row_data.uri_ranges); - tll_pop_back(row_data.uri_ranges); - xassert(tll_length(row_data.uri_ranges) == 0); + row_data.uri_ranges.count = 0; /* One URI, erase middle part of it */ grid_row_uri_range_add(&row, (struct row_uri_range){1, 10}); grid_row_uri_range_erase(&row, 5, 6); - xassert(tll_length(row_data.uri_ranges) == 2); - xassert(tll_front(row_data.uri_ranges).start == 1); - xassert(tll_front(row_data.uri_ranges).end == 4); - xassert(tll_back(row_data.uri_ranges).start == 7); - xassert(tll_back(row_data.uri_ranges).end == 10); + xassert(row_data.uri_ranges.count == 2); + xassert(row_data.uri_ranges.v[0].start == 1); + xassert(row_data.uri_ranges.v[0].end == 4); + xassert(row_data.uri_ranges.v[1].start == 7); + xassert(row_data.uri_ranges.v[1].end == 10); verify_no_overlapping_uris(&row); + verify_uris_are_sorted(&row); - tll_free(row_data.uri_ranges); + free(row_data.uri_ranges.v); } diff --git a/grid.h b/grid.h index 8ede4773..7819db4d 100644 --- a/grid.h +++ b/grid.h @@ -88,14 +88,15 @@ grid_row_uri_range_destroy(struct row_uri_range *range) static inline void grid_row_reset_extra(struct row *row) { - if (likely(row->extra == NULL)) + struct row_data *extra = row->extra; + + if (likely(extra == NULL)) return; - tll_foreach(row->extra->uri_ranges, it) { - grid_row_uri_range_destroy(&it->item); - tll_remove(row->extra->uri_ranges, it); - } + for (size_t i = 0; i < extra->uri_ranges.count; i++) + grid_row_uri_range_destroy(&extra->uri_ranges.v[i]); + free(extra->uri_ranges.v); - free(row->extra); + free(extra); row->extra = NULL; } diff --git a/terminal.h b/terminal.h index 1f3913ae..3096186f 100644 --- a/terminal.h +++ b/terminal.h @@ -102,7 +102,11 @@ struct row_uri_range { }; struct row_data { - tll(struct row_uri_range) uri_ranges; + struct { + struct row_uri_range *v; + uint32_t size; + uint32_t count; + } uri_ranges; }; struct row { diff --git a/url-mode.c b/url-mode.c index 8fb8a8a5..b565a87d 100644 --- a/url-mode.c +++ b/url-mode.c @@ -439,24 +439,27 @@ osc8_uris(const struct terminal *term, enum url_action action, url_list_t *urls) for (int r = 0; r < term->rows; r++) { const struct row *row = grid_row_in_view(term->grid, r); + const struct row_data *extra = row->extra; - if (row->extra == NULL) + if (extra == NULL) continue; - tll_foreach(row->extra->uri_ranges, it) { + for (size_t i = 0; i < extra->uri_ranges.count; i++) { + const struct row_uri_range *range = &extra->uri_ranges.v[i]; + struct coord start = { - .col = it->item.start, + .col = range->start, .row = r + term->grid->view, }; struct coord end = { - .col = it->item.end, + .col = range->end, .row = r + term->grid->view, }; tll_push_back( *urls, ((struct url){ - .id = it->item.id, - .url = xstrdup(it->item.uri), + .id = range->id, + .url = xstrdup(range->uri), .start = start, .end = end, .action = action, -- cgit v1.3 From 4eb0aa0f185ea9da604582bf8f091ab428b27997 Mon Sep 17 00:00:00 2001 From: Daniel Eklöf Date: Fri, 26 Nov 2021 20:25:07 +0100 Subject: osc8: replace grid_row_uri_range_add() with internal uri_range_append() MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit grid_row_uri_range_add() was only used while reflowing. In this case, we know the new URIs being added are always going at the end of the URI list (since we’re going top-to-bottom, left-to-right). Thus, we don’t need the insertion logic, and can simply append instead. --- grid.c | 289 +++++++++++++++++++++++++++++++---------------------------------- 1 file changed, 138 insertions(+), 151 deletions(-) (limited to 'grid.c') diff --git a/grid.c b/grid.c index e1b7ce38..a68f1ee4 100644 --- a/grid.c +++ b/grid.c @@ -15,6 +15,108 @@ #define TIME_REFLOW 0 +static void +ensure_row_has_extra_data(struct row *row) +{ + if (row->extra == NULL) + row->extra = xcalloc(1, sizeof(*row->extra)); +} + +static void +verify_no_overlapping_uris(const struct row_data *extra) +{ +#if defined(_DEBUG) + for (size_t i = 0; i < extra->uri_ranges.count; i++) { + const struct row_uri_range *r1 = &extra->uri_ranges.v[i]; + + for (size_t j = i + 1; j < extra->uri_ranges.count; j++) { + const struct row_uri_range *r2 = &extra->uri_ranges.v[j]; + xassert(r1 != r2); + + if ((r1->start <= r2->start && r1->end >= r2->start) || + (r1->start <= r2->end && r1->end >= r2->end)) + { + BUG("OSC-8 URI overlap: %s: %d-%d: %s: %d-%d", + r1->uri, r1->start, r1->end, + r2->uri, r2->start, r2->end); + } + } + } +#endif +} + +static void +verify_uris_are_sorted(const struct row_data *extra) +{ +#if defined(_DEBUG) + const struct row_uri_range *last = NULL; + + for (size_t i = 0; i < extra->uri_ranges.count; i++) { + const struct row_uri_range *r = &extra->uri_ranges.v[i]; + + if (last != NULL) { + if (last->start >= r->start || last->end >= r->end) { + BUG("OSC-8 URI not sorted correctly: " + "%s: %d-%d came before %s: %d-%d", + last->uri, last->start, last->end, + r->uri, r->start, r->end); + } + } + + last = r; + } +#endif +} + +static void +uri_range_ensure_size(struct row_data *extra, size_t count_to_add) +{ + if (extra->uri_ranges.count + count_to_add > extra->uri_ranges.size) { + extra->uri_ranges.size += count_to_add + 4; + extra->uri_ranges.v = xrealloc( + extra->uri_ranges.v, + extra->uri_ranges.size * sizeof(extra->uri_ranges.v[0])); + } + + xassert(extra->uri_ranges.count + count_to_add <= extra->uri_ranges.size); +} + +static void +uri_range_insert(struct row_data *extra, size_t idx, struct row_uri_range range) +{ + uri_range_ensure_size(extra, 1); + + xassert(idx <= extra->uri_ranges.count); + + const size_t move_count = extra->uri_ranges.count - idx; + memmove(&extra->uri_ranges.v[idx + 1], + &extra->uri_ranges.v[idx], + move_count * sizeof(extra->uri_ranges.v[0])); + + extra->uri_ranges.v[idx] = range; + extra->uri_ranges.count++; +} + +static void +uri_range_append(struct row_data *extra, struct row_uri_range range) +{ + uri_range_ensure_size(extra, 1); + extra->uri_ranges.v[extra->uri_ranges.count++] = range; +} + +static void +uri_range_delete(struct row_data *extra, size_t idx) +{ + xassert(idx < extra->uri_ranges.count); + grid_row_uri_range_destroy(&extra->uri_ranges.v[idx]); + + const size_t move_count = extra->uri_ranges.count - idx - 1; + memmove(&extra->uri_ranges.v[idx], + &extra->uri_ranges.v[idx + 1], + move_count * sizeof(extra->uri_ranges.v[0])); + extra->uri_ranges.count--; +} + struct grid * grid_snapshot(const struct grid *grid) { @@ -246,7 +348,8 @@ grid_resize_without_reflow( .id = old_range->id, .uri = xstrdup(old_range->uri), }; - grid_row_uri_range_add(new_row, range); + ensure_row_has_extra_data(new_row); + uri_range_append(new_row->extra, range); } } @@ -259,6 +362,18 @@ grid_resize_without_reflow( new_row->dirty = true; } + for (size_t r = 0; r < new_rows; r++) { + const struct row *row = new_grid[r]; + + if (row == NULL) + continue; + if (row->extra == NULL) + continue; + + verify_no_overlapping_uris(row->extra); + verify_uris_are_sorted(row->extra); + } + /* Free old grid */ for (int r = 0; r < grid->num_rows; r++) grid_row_free(old_grid[r]); @@ -313,7 +428,8 @@ reflow_uri_range_start(struct row_uri_range *range, struct row *new_row, .uri = range->uri, }; range->uri = NULL; - grid_row_uri_range_add(new_row, new_range); + ensure_row_has_extra_data(new_row); + uri_range_append(new_row->extra, new_range); } static void @@ -382,7 +498,8 @@ _line_wrap(struct grid *old_grid, struct row **new_grid, struct row *row, .id = range->id, .uri = xstrdup(range->uri), }; - grid_row_uri_range_add(new_row, new_range); + ensure_row_has_extra_data(new_row); + uri_range_append(new_row->extra, new_range); } } @@ -774,6 +891,9 @@ grid_resize_and_reflow( for (size_t i = 0; i < row->extra->uri_ranges.count; i++) xassert(row->extra->uri_ranges.v[i].end >= 0); + + verify_no_overlapping_uris(row->extra); + verify_uris_are_sorted(row->extra); } /* Verify all old rows have been free:d */ @@ -857,111 +977,6 @@ grid_resize_and_reflow( #endif } -static void -ensure_row_has_extra_data(struct row *row) -{ - if (row->extra == NULL) - row->extra = xcalloc(1, sizeof(*row->extra)); -} - -static void -verify_no_overlapping_uris(const struct row *row) -{ -#if defined(_DEBUG) - const struct row_data *extra = row->extra; - for (size_t i = 0; i < extra->uri_ranges.count; i++) { - const struct row_uri_range *r1 = &extra->uri_ranges.v[i]; - - for (size_t j = i + 1; j < extra->uri_ranges.count; j++) { - const struct row_uri_range *r2 = &extra->uri_ranges.v[j]; - xassert(r1 != r2); - - if ((r1->start <= r2->start && r1->end >= r2->start) || - (r1->start <= r2->end && r1->end >= r2->end)) - { - BUG("OSC-8 URI overlap: %s: %d-%d: %s: %d-%d", - r1->uri, r1->start, r1->end, - r2->uri, r2->start, r2->end); - } - } - } -#endif -} - -static void -verify_uris_are_sorted(const struct row *row) -{ -#if defined(_DEBUG) - const struct row_data *extra = row->extra; - const struct row_uri_range *last = NULL; - - for (size_t i = 0; i < extra->uri_ranges.count; i++) { - const struct row_uri_range *r = &extra->uri_ranges.v[i]; - - if (last != NULL) { - if (last->start >= r->start || last->end >= r->end) { - BUG("OSC-8 URI not sorted correctly: " - "%s: %d-%d came before %s: %d-%d", - last->uri, last->start, last->end, - r->uri, r->start, r->end); - } - } - - last = r; - } -#endif -} - -static void -uri_range_ensure_size(struct row_data *extra, size_t count_to_add) -{ - if (extra->uri_ranges.count + count_to_add > extra->uri_ranges.size) { - extra->uri_ranges.size += count_to_add + 4; - extra->uri_ranges.v = xrealloc( - extra->uri_ranges.v, - extra->uri_ranges.size * sizeof(extra->uri_ranges.v[0])); - } - - xassert(extra->uri_ranges.count + count_to_add <= extra->uri_ranges.size); -} - -static void -uri_range_insert(struct row_data *extra, size_t idx, struct row_uri_range range) -{ - uri_range_ensure_size(extra, 1); - - xassert(idx <= extra->uri_ranges.count); - - const size_t move_count = extra->uri_ranges.count - idx; - memmove(&extra->uri_ranges.v[idx + 1], - &extra->uri_ranges.v[idx], - move_count * sizeof(extra->uri_ranges.v[0])); - - extra->uri_ranges.v[idx] = range; - extra->uri_ranges.count++; -} - -#if 0 -static void -uri_range_append(struct row_data *extra, struct row_uri_range range) -{ - uri_range_ensure_size(extra, 1); - extra->uri_ranges.v[extra->uri_ranges.count++] = range; -} -#endif -static void -uri_range_delete(struct row_data *extra, size_t idx) -{ - xassert(idx < extra->uri_ranges.count); - grid_row_uri_range_destroy(&extra->uri_ranges.v[idx]); - - const size_t move_count = extra->uri_ranges.count - idx - 1; - memmove(&extra->uri_ranges.v[idx], - &extra->uri_ranges.v[idx + 1], - move_count * sizeof(extra->uri_ranges.v[0])); - extra->uri_ranges.count--; -} - void grid_row_uri_range_put(struct row *row, int col, const char *uri, uint64_t id) { @@ -1064,8 +1079,8 @@ grid_row_uri_range_put(struct row *row, int col, const char *uri, uint64_t id) } out: - verify_no_overlapping_uris(row); - verify_uris_are_sorted(row); + verify_no_overlapping_uris(extra); + verify_uris_are_sorted(extra); } UNITTEST @@ -1133,28 +1148,6 @@ UNITTEST #undef verify_range } -void -grid_row_uri_range_add(struct row *row, struct row_uri_range range) -{ - ensure_row_has_extra_data(row); - struct row_data *extra = row->extra; - - for (ssize_t i = (ssize_t)extra->uri_ranges.count - 1; i >= 0; i--) { - const struct row_uri_range *r = &extra->uri_ranges.v[i]; - - if (r->end < range.start) { - uri_range_insert(extra, i + 1, range); - goto out; - } - } - - uri_range_insert(extra, 0, range); - -out: - verify_no_overlapping_uris(row); - verify_uris_are_sorted(row); -} - void grid_row_uri_range_erase(struct row *row, int start, int end) { @@ -1212,51 +1205,45 @@ UNITTEST struct row_data row_data = {.uri_ranges = {0}}; struct row row = {.extra = &row_data}; - grid_row_uri_range_add(&row, (struct row_uri_range){1, 10}); - xassert(row_data.uri_ranges.count == 1); - xassert(row_data.uri_ranges.v[0].start == 1); - xassert(row_data.uri_ranges.v[0].end == 10); - verify_no_overlapping_uris(&row); - verify_uris_are_sorted(&row); - - grid_row_uri_range_add(&row, (struct row_uri_range){11, 20}); + uri_range_append(&row_data, (struct row_uri_range){1, 10}); + uri_range_append(&row_data, (struct row_uri_range){11, 20}); xassert(row_data.uri_ranges.count == 2); xassert(row_data.uri_ranges.v[1].start == 11); xassert(row_data.uri_ranges.v[1].end == 20); - verify_no_overlapping_uris(&row); - verify_uris_are_sorted(&row); + verify_no_overlapping_uris(&row_data); + verify_uris_are_sorted(&row_data); /* Erase both URis */ grid_row_uri_range_erase(&row, 1, 20); xassert(row_data.uri_ranges.count == 0); - verify_no_overlapping_uris(&row); - verify_uris_are_sorted(&row); + verify_no_overlapping_uris(&row_data); + verify_uris_are_sorted(&row_data); /* Two URIs, then erase second half of the first, first half of the second */ - grid_row_uri_range_add(&row, (struct row_uri_range){1, 10}); - grid_row_uri_range_add(&row, (struct row_uri_range){11, 20}); + uri_range_append(&row_data, (struct row_uri_range){1, 10}); + uri_range_append(&row_data, (struct row_uri_range){11, 20}); grid_row_uri_range_erase(&row, 5, 15); xassert(row_data.uri_ranges.count == 2); xassert(row_data.uri_ranges.v[0].start == 1); xassert(row_data.uri_ranges.v[0].end == 4); xassert(row_data.uri_ranges.v[1].start == 16); xassert(row_data.uri_ranges.v[1].end == 20); - verify_no_overlapping_uris(&row); - verify_uris_are_sorted(&row); + verify_no_overlapping_uris(&row_data); + verify_uris_are_sorted(&row_data); row_data.uri_ranges.count = 0; /* One URI, erase middle part of it */ - grid_row_uri_range_add(&row, (struct row_uri_range){1, 10}); + uri_range_append(&row_data, (struct row_uri_range){1, 10}); grid_row_uri_range_erase(&row, 5, 6); xassert(row_data.uri_ranges.count == 2); xassert(row_data.uri_ranges.v[0].start == 1); xassert(row_data.uri_ranges.v[0].end == 4); xassert(row_data.uri_ranges.v[1].start == 7); xassert(row_data.uri_ranges.v[1].end == 10); - verify_no_overlapping_uris(&row); - verify_uris_are_sorted(&row); + verify_no_overlapping_uris(&row_data); + verify_uris_are_sorted(&row_data); free(row_data.uri_ranges.v); } -- cgit v1.3 From be203aeae1280ad7cac3ec9e287d1dd97528f390 Mon Sep 17 00:00:00 2001 From: Daniel Eklöf Date: Fri, 26 Nov 2021 20:27:55 +0100 Subject: grid: bug: OSC-8 URIs were incorrectly skipped while resizing the alt screen --- CHANGELOG.md | 2 ++ grid.c | 2 +- 2 files changed, 3 insertions(+), 1 deletion(-) (limited to 'grid.c') diff --git a/CHANGELOG.md b/CHANGELOG.md index c185dd72..9b928d68 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -51,6 +51,8 @@ * OSC-8 URIs in the last column * OSC-8 URIs sometimes being applied to too many, and seemingly unrelated cells (https://codeberg.org/dnkl/foot/issues/816). +* OSC-8 URIs incorrectly being dropped when resizing the terminal + window with the alternate screen active. ### Security diff --git a/grid.c b/grid.c index a68f1ee4..92675145 100644 --- a/grid.c +++ b/grid.c @@ -337,7 +337,7 @@ grid_resize_without_reflow( const struct row_uri_range *old_range = &old_row->extra->uri_ranges.v[i]; - if (old_range->start >= new_rows) { + if (old_range->start >= new_cols) { /* The whole range is truncated */ continue; } -- cgit v1.3 From 41565a0d0ef4486b8b0a223fc8cc28180022cb52 Mon Sep 17 00:00:00 2001 From: Daniel Eklöf Date: Fri, 26 Nov 2021 20:36:59 +0100 Subject: grid: resize without reflow: only verify URI ranges in debug builds --- grid.c | 2 ++ 1 file changed, 2 insertions(+) (limited to 'grid.c') diff --git a/grid.c b/grid.c index 92675145..dd6011c1 100644 --- a/grid.c +++ b/grid.c @@ -362,6 +362,7 @@ grid_resize_without_reflow( new_row->dirty = true; } +#if defined(_DEBUG) for (size_t r = 0; r < new_rows; r++) { const struct row *row = new_grid[r]; @@ -373,6 +374,7 @@ grid_resize_without_reflow( verify_no_overlapping_uris(row->extra); verify_uris_are_sorted(row->extra); } +#endif /* Free old grid */ for (int r = 0; r < grid->num_rows; r++) -- cgit v1.3 From 76992713161b589407060c2fc7a42e7ffb192844 Mon Sep 17 00:00:00 2001 From: Daniel Eklöf Date: Fri, 26 Nov 2021 20:57:08 +0100 Subject: grid: reflow: no need to keep a uri-range-idx variable MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit The URI ranges are now an array, which means we can get the next URI range by incrementing the pointer. Instead of checking if range is not NULL, check that it isn’t the range terminator (which is NULL when we don’t have any ranges, and the first address *after* the last range otherwise). --- grid.c | 24 ++++++++++-------------- 1 file changed, 10 insertions(+), 14 deletions(-) (limited to 'grid.c') diff --git a/grid.c b/grid.c index dd6011c1..e168353f 100644 --- a/grid.c +++ b/grid.c @@ -684,19 +684,20 @@ grid_resize_and_reflow( tp = NULL; /* Does this row have any URIs? */ - struct row_uri_range *range; + struct row_uri_range *range, *range_terminator; struct row_data *extra = old_row->extra; - size_t uri_range_idx = 0; if (extra != NULL && extra->uri_ranges.count > 0) { - range = &extra->uri_ranges.v[uri_range_idx]; + range = &extra->uri_ranges.v[0]; + range_terminator = &extra->uri_ranges.v[extra->uri_ranges.count]; - /* Make sure the *last* URI range's end point is included in the copy */ + /* Make sure the *last* URI range's end point is included + * in the copy */ const struct row_uri_range *last_on_row = &extra->uri_ranges.v[extra->uri_ranges.count - 1]; col_count = max(col_count, last_on_row->end + 1); } else - range = NULL; + range = range_terminator = NULL; for (int start = 0, left = col_count; left > 0;) { int end; @@ -710,7 +711,7 @@ grid_resize_and_reflow( * If there are no more tracking points, or URI ranges, * the end-coordinate will be at the end of the row, */ - if (range != NULL) { + if (range != range_terminator) { int uri_col = (range->start >= start ? range->start : range->end) + 1; if (tp != NULL) { @@ -835,20 +836,15 @@ grid_resize_and_reflow( } if (uri_break) { + xassert(range != NULL); + if (range->start == end - 1) reflow_uri_range_start(range, new_row, new_col_idx - 1); if (range->end == end - 1) { reflow_uri_range_end(range, new_row, new_col_idx - 1); - - xassert(&extra->uri_ranges.v[uri_range_idx] == range); grid_row_uri_range_destroy(range); - - uri_range_idx++; - - range = uri_range_idx < extra->uri_ranges.count - ? &old_row->extra->uri_ranges.v[uri_range_idx] - : NULL; + range++; } } -- cgit v1.3 From 5c7e881cd49d7814c7f791f5e3457aca2b5f72d3 Mon Sep 17 00:00:00 2001 From: Daniel Eklöf Date: Sat, 27 Nov 2021 16:03:07 +0100 Subject: grid: uri_range_ensure_size(): add the requested amount of entries --- grid.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'grid.c') diff --git a/grid.c b/grid.c index e168353f..609822e3 100644 --- a/grid.c +++ b/grid.c @@ -72,7 +72,7 @@ static void uri_range_ensure_size(struct row_data *extra, size_t count_to_add) { if (extra->uri_ranges.count + count_to_add > extra->uri_ranges.size) { - extra->uri_ranges.size += count_to_add + 4; + extra->uri_ranges.size += count_to_add + count_to_add; extra->uri_ranges.v = xrealloc( extra->uri_ranges.v, extra->uri_ranges.size * sizeof(extra->uri_ranges.v[0])); -- cgit v1.3 From 5c6c2de0517fbe93b748d3315b7b52ca682bac24 Mon Sep 17 00:00:00 2001 From: Daniel Eklöf Date: Sat, 27 Nov 2021 16:07:50 +0100 Subject: grid: snapshot: use uri range utility functions --- grid.c | 33 ++++++++++++++------------------- 1 file changed, 14 insertions(+), 19 deletions(-) (limited to 'grid.c') diff --git a/grid.c b/grid.c index 609822e3..110a1ce4 100644 --- a/grid.c +++ b/grid.c @@ -149,29 +149,24 @@ grid_snapshot(const struct grid *grid) for (int c = 0; c < grid->num_cols; c++) clone_row->cells[c] = row->cells[c]; - if (row->extra != NULL) { - const struct row_data *extra = row->extra; - struct row_data *new_extra = xmalloc(sizeof(*new_extra)); - struct row_uri_range *ranges = - xmalloc(extra->uri_ranges.count * sizeof(ranges[0])); + const struct row_data *extra = row->extra; - for (size_t i = 0; i < extra->uri_ranges.count; i++) { - const struct row_uri_range *range = &extra->uri_ranges.v[i]; + if (extra != NULL) { + ensure_row_has_extra_data(clone_row); + uri_range_ensure_size(clone_row->extra, extra->uri_ranges.count); - ranges[i] = (struct row_uri_range){ - .start = range->start, - .end = range->end, - .id = range->id, - .uri = xstrdup(range->uri), - }; + struct row_data *clone_extra = clone_row->extra; + for (size_t i = 0; i < extra->uri_ranges.count; i++) { + const struct row_uri_range *range = &extra->uri_ranges.v[i]; + uri_range_append( + clone_extra, + (struct row_uri_range){ + .start = range->start, + .end = range->end, + .id = range->id, + .uri = xstrdup(range->uri)}); } - - new_extra->uri_ranges.v = ranges; - new_extra->uri_ranges.size = extra->uri_ranges.count; - new_extra->uri_ranges.count = extra->uri_ranges.count; - - clone_row->extra = new_extra; } else clone_row->extra = NULL; } -- cgit v1.3 From dfeca4e13497f9a4295cb4c23e53e7639d614e45 Mon Sep 17 00:00:00 2001 From: Daniel Eklöf Date: Sat, 27 Nov 2021 16:24:26 +0100 Subject: grid: uri_range_{append,insert}: pass range attributes as separate parameters --- grid.c | 118 ++++++++++++++++++++++++++++++----------------------------------- 1 file changed, 54 insertions(+), 64 deletions(-) (limited to 'grid.c') diff --git a/grid.c b/grid.c index 110a1ce4..fd1e5b16 100644 --- a/grid.c +++ b/grid.c @@ -82,7 +82,8 @@ uri_range_ensure_size(struct row_data *extra, size_t count_to_add) } static void -uri_range_insert(struct row_data *extra, size_t idx, struct row_uri_range range) +uri_range_insert(struct row_data *extra, size_t idx, int start, int end, + uint64_t id, const char *uri) { uri_range_ensure_size(extra, 1); @@ -93,15 +94,33 @@ uri_range_insert(struct row_data *extra, size_t idx, struct row_uri_range range) &extra->uri_ranges.v[idx], move_count * sizeof(extra->uri_ranges.v[0])); - extra->uri_ranges.v[idx] = range; extra->uri_ranges.count++; + extra->uri_ranges.v[idx] = (struct row_uri_range){ + .start = start, + .end = end, + .id = id, + .uri = xstrdup(uri), + }; } static void -uri_range_append(struct row_data *extra, struct row_uri_range range) +uri_range_append_no_strdup(struct row_data *extra, int start, int end, + uint64_t id, char *uri) { uri_range_ensure_size(extra, 1); - extra->uri_ranges.v[extra->uri_ranges.count++] = range; + extra->uri_ranges.v[extra->uri_ranges.count++] = (struct row_uri_range){ + .start = start, + .end = end, + .id = id, + .uri = uri, + }; +} + +static void +uri_range_append(struct row_data *extra, int start, int end, uint64_t id, + const char *uri) +{ + uri_range_append_no_strdup(extra, start, end, id, xstrdup(uri)); } static void @@ -152,20 +171,16 @@ grid_snapshot(const struct grid *grid) const struct row_data *extra = row->extra; if (extra != NULL) { - ensure_row_has_extra_data(clone_row); - uri_range_ensure_size(clone_row->extra, extra->uri_ranges.count); + struct row_data *clone_extra = xcalloc(1, sizeof(*clone_extra)); + clone_row->extra = clone_extra; - struct row_data *clone_extra = clone_row->extra; + uri_range_ensure_size(clone_extra, extra->uri_ranges.count); for (size_t i = 0; i < extra->uri_ranges.count; i++) { const struct row_uri_range *range = &extra->uri_ranges.v[i]; uri_range_append( clone_extra, - (struct row_uri_range){ - .start = range->start, - .end = range->end, - .id = range->id, - .uri = xstrdup(range->uri)}); + range->start, range->end, range->id, range->uri); } } else clone_row->extra = NULL; @@ -337,14 +352,11 @@ grid_resize_without_reflow( continue; } - struct row_uri_range range = { - .start = old_range->start, - .end = min(old_range->end, new_cols - 1), - .id = old_range->id, - .uri = xstrdup(old_range->uri), - }; ensure_row_has_extra_data(new_row); - uri_range_append(new_row->extra, range); + uri_range_append( + new_row->extra, + old_range->start, min(old_range->end, new_cols - 1), + old_range->id, xstrdup(old_range->uri)); } } @@ -418,15 +430,10 @@ static void reflow_uri_range_start(struct row_uri_range *range, struct row *new_row, int new_col_idx) { - struct row_uri_range new_range = { - .start = new_col_idx, - .end = -1, - .id = range->id, - .uri = range->uri, - }; - range->uri = NULL; ensure_row_has_extra_data(new_row); - uri_range_append(new_row->extra, new_range); + uri_range_append_no_strdup + (new_row->extra, new_col_idx, -1, range->id, range->uri); + range->uri = NULL; } static void @@ -489,14 +496,8 @@ _line_wrap(struct grid *old_grid, struct row **new_grid, struct row *row, range->end = col_count - 1; /* Open a new range on the new/current row */ - struct row_uri_range new_range = { - .start = 0, - .end = -1, - .id = range->id, - .uri = xstrdup(range->uri), - }; ensure_row_has_extra_data(new_row); - uri_range_append(new_row->extra, new_range); + uri_range_append(new_row->extra, 0, -1, range->id, range->uri); } } @@ -1022,15 +1023,7 @@ grid_row_uri_range_put(struct row *row, int col, const char *uri, uint64_t id) xassert(r->start < col); xassert(r->end > col); - struct row_uri_range new_tail = { - .start = col + 1, - .end = r->end, - .id = r->id, - .uri = xstrdup(r->uri), - }; - xassert(new_tail.start <= new_tail.end); - - uri_range_insert(extra, i + 1, new_tail); + uri_range_insert(extra, i + 1, col + 1, r->end, r->id, r->uri); r->end = col - 1; xassert(r->start <= r->end); @@ -1042,21 +1035,19 @@ grid_row_uri_range_put(struct row *row, int col, const char *uri, uint64_t id) } } - struct row_uri_range new_range = { - .start = col, - .end = col, - .id = id, - .uri = xstrdup(uri), - }; - xassert(insert_idx >= 0); xassert(insert_idx <= extra->uri_ranges.count); if (replace) { grid_row_uri_range_destroy(&extra->uri_ranges.v[insert_idx]); - extra->uri_ranges.v[insert_idx] = new_range; + extra->uri_ranges.v[insert_idx] = (struct row_uri_range){ + .start = col, + .end = col, + .id = id, + .uri = xstrdup(uri), + }; } else - uri_range_insert(extra, insert_idx, new_range); + uri_range_insert(extra, insert_idx, col, col, id, uri); if (run_merge_pass) { for (size_t i = 1; i < extra->uri_ranges.count; i++) { @@ -1167,13 +1158,8 @@ grid_row_uri_range_erase(struct row *row, int start, int end) else if (start > old->start && end < old->end) { /* Erase range erases a part in the middle of the URI */ - struct row_uri_range old_tail = { - .start = end + 1, - .end = old->end, - .id = old->id, - .uri = old->uri != NULL ? xstrdup(old->uri) : NULL, - }; - uri_range_insert(extra, i + 1, old_tail); + uri_range_insert( + extra, i + 1, end + 1, old->end, old->id, old->uri); old->end = start - 1; return; /* There can be no more URIs affected by the erase range */ } @@ -1198,8 +1184,8 @@ UNITTEST struct row_data row_data = {.uri_ranges = {0}}; struct row row = {.extra = &row_data}; - uri_range_append(&row_data, (struct row_uri_range){1, 10}); - uri_range_append(&row_data, (struct row_uri_range){11, 20}); + uri_range_append(&row_data, 1, 10, 0, "dummy"); + uri_range_append(&row_data, 11, 20, 0, "dummy"); xassert(row_data.uri_ranges.count == 2); xassert(row_data.uri_ranges.v[1].start == 11); xassert(row_data.uri_ranges.v[1].end == 20); @@ -1214,8 +1200,8 @@ UNITTEST /* Two URIs, then erase second half of the first, first half of the second */ - uri_range_append(&row_data, (struct row_uri_range){1, 10}); - uri_range_append(&row_data, (struct row_uri_range){11, 20}); + uri_range_append(&row_data, 1, 10, 0, "dummy"); + uri_range_append(&row_data, 11, 20, 0, "dummy"); grid_row_uri_range_erase(&row, 5, 15); xassert(row_data.uri_ranges.count == 2); xassert(row_data.uri_ranges.v[0].start == 1); @@ -1225,10 +1211,12 @@ UNITTEST verify_no_overlapping_uris(&row_data); verify_uris_are_sorted(&row_data); + grid_row_uri_range_destroy(&row_data.uri_ranges.v[0]); + grid_row_uri_range_destroy(&row_data.uri_ranges.v[1]); row_data.uri_ranges.count = 0; /* One URI, erase middle part of it */ - uri_range_append(&row_data, (struct row_uri_range){1, 10}); + uri_range_append(&row_data, 1, 10, 0, "dummy"); grid_row_uri_range_erase(&row, 5, 6); xassert(row_data.uri_ranges.count == 2); xassert(row_data.uri_ranges.v[0].start == 1); @@ -1238,5 +1226,7 @@ UNITTEST verify_no_overlapping_uris(&row_data); verify_uris_are_sorted(&row_data); + for (size_t i = 0; i < row_data.uri_ranges.count; i++) + grid_row_uri_range_destroy(&row_data.uri_ranges.v[i]); free(row_data.uri_ranges.v); } -- cgit v1.3 From 5ce6c89df638bb7bff5552997f671092cd32a858 Mon Sep 17 00:00:00 2001 From: Daniel Eklöf Date: Sat, 27 Nov 2021 16:31:33 +0100 Subject: grid: resize without reflowing: use URI range utility functions --- grid.c | 23 +++++++++++++---------- 1 file changed, 13 insertions(+), 10 deletions(-) (limited to 'grid.c') diff --git a/grid.c b/grid.c index fd1e5b16..de51f90b 100644 --- a/grid.c +++ b/grid.c @@ -340,23 +340,26 @@ grid_resize_without_reflow( } /* Copy URI ranges, truncating them if necessary */ - if (old_row->extra == NULL) + const struct row_data *old_extra = old_row->extra; + if (old_extra == NULL) continue; - for (size_t i = 0; i < old_row->extra->uri_ranges.count; i++) { - const struct row_uri_range *old_range = - &old_row->extra->uri_ranges.v[i]; + ensure_row_has_extra_data(new_row); + struct row_data *new_extra = new_row->extra; - if (old_range->start >= new_cols) { + uri_range_ensure_size(new_extra, old_extra->uri_ranges.count); + + for (size_t i = 0; i < old_extra->uri_ranges.count; i++) { + const struct row_uri_range *range = &old_extra->uri_ranges.v[i]; + + if (range->start >= new_cols) { /* The whole range is truncated */ continue; } - ensure_row_has_extra_data(new_row); - uri_range_append( - new_row->extra, - old_range->start, min(old_range->end, new_cols - 1), - old_range->id, xstrdup(old_range->uri)); + const int start = range->start; + const int end = min(range->end, new_cols - 1); + uri_range_append(new_extra, start, end, range->id, range->uri); } } -- cgit v1.3 From 747da83c765d8df4c369d3a9bf82ea87ce9f1284 Mon Sep 17 00:00:00 2001 From: Daniel Eklöf Date: Sat, 27 Nov 2021 18:15:59 +0100 Subject: grid: remove useless assertion MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit grid.c:1041:24: warning: comparison of unsigned expression in ‘>= 0’ is always true [-Wtype-limits] --- grid.c | 1 - 1 file changed, 1 deletion(-) (limited to 'grid.c') diff --git a/grid.c b/grid.c index de51f90b..c0e10b23 100644 --- a/grid.c +++ b/grid.c @@ -1038,7 +1038,6 @@ grid_row_uri_range_put(struct row *row, int col, const char *uri, uint64_t id) } } - xassert(insert_idx >= 0); xassert(insert_idx <= extra->uri_ranges.count); if (replace) { -- cgit v1.3 From 66b8c92c30667327ce7b5de3cbc068be67b3719a Mon Sep 17 00:00:00 2001 From: Daniel Eklöf Date: Sun, 28 Nov 2021 10:56:32 +0100 Subject: grid: uri_range_erase: walk the ranges backwards This way, ranges are deleted last-to-first, thus avoiding memmoving multiple ranges over and over again when erasing e.g. a full line. --- grid.c | 9 ++++----- 1 file changed, 4 insertions(+), 5 deletions(-) (limited to 'grid.c') diff --git a/grid.c b/grid.c index c0e10b23..bfb07d16 100644 --- a/grid.c +++ b/grid.c @@ -1143,19 +1143,18 @@ grid_row_uri_range_erase(struct row *row, int start, int end) struct row_data *extra = row->extra; /* Split up, or remove, URI ranges affected by the erase */ - for (ssize_t i = 0; i < extra->uri_ranges.count; i++) { + for (ssize_t i = (ssize_t)extra->uri_ranges.count - 1; i >= 0; i--) { struct row_uri_range *old = &extra->uri_ranges.v[i]; if (old->end < start) - continue; + return; if (old->start > end) - return; + continue; if (start <= old->start && end >= old->end) { /* Erase range covers URI completely - remove it */ uri_range_delete(extra, i); - i--; } else if (start > old->start && end < old->end) { @@ -1170,13 +1169,13 @@ grid_row_uri_range_erase(struct row *row, int start, int end) /* Erase range erases the head of the URI */ xassert(start <= old->start); old->start = end + 1; - return; /* There can be no more overlapping URIs */ } else if (start <= old->end && end >= old->end) { /* Erase range erases the tail of the URI */ xassert(end >= old->end); old->end = start - 1; + return; /* There can be no more overlapping URIs */ } } } -- cgit v1.3 From 2fe2dfa847a2fdc3563d53a1a1a81e1853868c4f Mon Sep 17 00:00:00 2001 From: Daniel Eklöf Date: Sun, 28 Nov 2021 11:05:00 +0100 Subject: grid: uri_range_erase(): unittest: try erasing a row without any URIs --- grid.c | 4 ++++ 1 file changed, 4 insertions(+) (limited to 'grid.c') diff --git a/grid.c b/grid.c index bfb07d16..d6ddafad 100644 --- a/grid.c +++ b/grid.c @@ -1185,6 +1185,10 @@ UNITTEST struct row_data row_data = {.uri_ranges = {0}}; struct row row = {.extra = &row_data}; + /* Try erasing a row without any URIs */ + grid_row_uri_range_erase(&row, 0, 200); + xassert(row_data.uri_ranges.count == 0); + uri_range_append(&row_data, 1, 10, 0, "dummy"); uri_range_append(&row_data, 11, 20, 0, "dummy"); xassert(row_data.uri_ranges.count == 2); -- cgit v1.3