From fa2d9f86996467ba33cc381f810ea966a4323381 Mon Sep 17 00:00:00 2001 From: Daniel Eklöf Date: Thu, 28 Jul 2022 18:45:25 +0200 Subject: selection: rework how we update a selection MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Before this patch, each selection update would result in grid covered by the selection being walked *three* times. First to “premark” the area that *will* be selected after the update, then again to unmark the previous selection (excluding the cells that were premarked - but the cells are still iterated), and then one more time to finalize the selection state in the grid. Furthermore, each time a frame is rendered, the entire selection were iterated again, to ensure all the cells have their ‘selected’ bit set. This quickly gets *very* slow. This patch takes a completely different approach. Instead of looking at the selection as a range of cells to iterate, we view it as an area, or region. Thus, on each update, we have to regions: the region representing the previous selection, and the region representing the to-be selection. By diffing these two regions, we get two new regions: one that represents the cells that were selected, but aren’t any more, and one that represents the cells that previously were not selected, but now will be. We implement the regions using pixman regions. By subtracting the current selection from the previous selection, we get the region representing the cells that are no longer selected, and that should be unmarked. By subtracting the previous selection from the current, we get the region representing the cells that was added to the selection in this update, and that should be marked. selection_dirty_cells() is rewritten in a similar manner. We create pixman regions for the selection, and the current scrollback view. The intersection represents the (selected) cells that are visible. These need to iterated and marked as being selected. Closes #1114 --- selection.c | 296 ++++++++++++++++++++++++++++++++++++++---------------------- 1 file changed, 190 insertions(+), 106 deletions(-) (limited to 'selection.c') diff --git a/selection.c b/selection.c index 54faf49b..8c3a8357 100644 --- a/selection.c +++ b/selection.c @@ -9,6 +9,8 @@ #include #include +#include + #define LOG_MODULE "selection" #define LOG_ENABLE_DBG 0 #include "log.h" @@ -609,111 +611,150 @@ selection_start(struct terminal *term, int col, int row, } -/* Context used while (un)marking selected cells, to be able to - * exclude empty cells */ -struct mark_context { - const struct row *last_row; - int empty_count; - uint8_t **keep_selection; -}; - -static bool -unmark_selected(struct terminal *term, struct row *row, struct cell *cell, - int row_no, int col, void *data) +static pixman_region32_t +pixman_region_for_coords_normal(const struct terminal *term, + const struct coord *start, + const struct coord *end) { - if (!cell->attrs.selected) - return true; + pixman_region32_t region; + pixman_region32_init(®ion); + + const int rel_start_row = + grid_row_abs_to_sb(term->grid, term->rows, start->row); + const int rel_end_row = + grid_row_abs_to_sb(term->grid, term->rows, end->row); - struct mark_context *ctx = data; - const uint8_t *keep_selection = - ctx->keep_selection != NULL ? ctx->keep_selection[row_no] : NULL; + if (rel_start_row < rel_end_row) { + /* First partial row (start ->)*/ + pixman_region32_union_rect( + ®ion, ®ion, + start->col, rel_start_row, + term->cols - start->col, 1); + + /* Full rows between start and end */ + if (rel_start_row + 1 < rel_end_row) { + pixman_region32_union_rect( + ®ion, ®ion, + 0, rel_start_row + 1, + term->cols, rel_end_row - rel_start_row - 1); + } - if (keep_selection != NULL) { - unsigned idx = (unsigned)col / 8; - unsigned ofs = (unsigned)col % 8; + /* Last partial row (-> end) */ + pixman_region32_union_rect( + ®ion, ®ion, + 0, rel_end_row, + end->col + 1, 1); - if (keep_selection[idx] & (1 << ofs)) { - /* We’re updating the selection, and this cell is still - * going to be selected */ - return true; + } else if (rel_start_row > rel_end_row) { + /* First partial row (end ->) */ + pixman_region32_union_rect( + ®ion, ®ion, + end->col, rel_end_row, + term->cols - end->col, 1); + + /* Full rows between end and start */ + if (rel_end_row + 1 < rel_start_row) { + pixman_region32_union_rect( + ®ion, ®ion, + 0, rel_end_row + 1, + term->cols, rel_start_row - rel_end_row - 1); } + + /* Last partial row (-> start) */ + pixman_region32_union_rect( + ®ion, ®ion, + 0, rel_start_row, + start->col + 1, 1); + } else { + const int start_col = min(start->col, end->col); + const int end_col = max(start->col, end->col); + + pixman_region32_union_rect( + ®ion, ®ion, + start_col, rel_start_row, + end_col + 1 - start_col, 1); } - row->dirty = true; - cell->attrs.selected = false; - cell->attrs.clean = false; - return true; + return region; } -static bool -premark_selected(struct terminal *term, struct row *row, struct cell *cell, - int row_no, int col, void *data) +static pixman_region32_t +pixman_region_for_coords_block(const struct terminal *term, + const struct coord *start, const struct coord *end) { - struct mark_context *ctx = data; - xassert(ctx != NULL); + pixman_region32_t region; + pixman_region32_init(®ion); - if (ctx->last_row != row) { - ctx->last_row = row; - ctx->empty_count = 0; - } + const int rel_start_row = + grid_row_abs_to_sb(term->grid, term->rows, start->row); + const int rel_end_row = + grid_row_abs_to_sb(term->grid, term->rows, end->row); - if (cell->wc == 0 && term->selection.kind != SELECTION_BLOCK) { - ctx->empty_count++; - return true; - } + pixman_region32_union_rect( + ®ion, ®ion, + min(start->col, end->col), min(rel_start_row, rel_end_row), + abs(start->col - end->col) + 1, abs(rel_start_row - rel_end_row) + 1); - uint8_t *keep_selection = ctx->keep_selection[row_no]; - if (keep_selection == NULL) { - keep_selection = xcalloc((term->grid->num_cols + 7) / 8, sizeof(keep_selection[0])); - ctx->keep_selection[row_no] = keep_selection; - } + return region; +} - /* Tell unmark to leave this be */ - for (int i = 0; i < ctx->empty_count + 1; i++) { - unsigned idx = (unsigned)(col - i) / 8; - unsigned ofs = (unsigned)(col - i) % 8; - keep_selection[idx] |= 1 << ofs; +/* Returns a pixman region representing the selection between ‘start’ + * and ‘end’ (given the current selection kind), in *scrollback + * relative coordinates* */ +static pixman_region32_t +pixman_region_for_coords(const struct terminal *term, + const struct coord *start, const struct coord *end) +{ + switch (term->selection.kind) { + default: return pixman_region_for_coords_normal(term, start, end); + case SELECTION_BLOCK: return pixman_region_for_coords_block(term, start, end); } - - ctx->empty_count = 0; - return true; } -static bool -mark_selected(struct terminal *term, struct row *row, struct cell *cell, - int row_no, int col, void *data) +static void +mark_selected_region(struct terminal *term, pixman_box32_t *boxes, + size_t count, bool selected, bool dirty_cells) { - struct mark_context *ctx = data; - xassert(ctx != NULL); + for (size_t i = 0; i < count; i++) { + const pixman_box32_t *box = &boxes[i]; - if (ctx->last_row != row) { - ctx->last_row = row; - ctx->empty_count = 0; - } + LOG_DBG("%s selection in region: %dx%d - %dx%d", + selected ? "marking" : "unmarking", + box->x1, box->y1, + box->x2, box->y2); - if (cell->wc == 0 && term->selection.kind != SELECTION_BLOCK) { - ctx->empty_count++; - return true; - } + int abs_row_start = grid_row_sb_to_abs( + term->grid, term->rows, box->y1); - for (int i = 0; i < ctx->empty_count + 1; i++) { - struct cell *c = &row->cells[col - i]; - if (!c->attrs.selected) { - row->dirty = true; - c->attrs.selected = true; - c->attrs.clean = false; - } - } + for (int r = abs_row_start, rel_r = box->y1; + rel_r < box->y2; + r = (r + 1) & (term->grid->num_rows - 1), rel_r++) + { + struct row *row = term->grid->rows[r]; + xassert(row != NULL); - ctx->empty_count = 0; - return true; -} + if (dirty_cells) + row->dirty = true; -static void -reset_modify_context(struct mark_context *ctx) -{ - ctx->last_row = NULL; - ctx->empty_count = 0; + for (int c = box->x1, empty_count = 0; c < box->x2; c++) { + if (selected && row->cells[c].wc == 0) { + empty_count++; + continue; + } + + for (int j = 0; j < empty_count + 1; j++) { + xassert(c - j >= 0); + struct cell *cell = &row->cells[c - j]; + + if (dirty_cells) + cell->attrs.clean = false; + cell->attrs.selected = selected; + } + + empty_count = 0; + } + } + } } static void @@ -723,33 +764,46 @@ selection_modify(struct terminal *term, struct coord start, struct coord end) xassert(start.row != -1 && start.col != -1); xassert(end.row != -1 && end.col != -1); - uint8_t **keep_selection = - xcalloc(term->grid->num_rows, sizeof(keep_selection[0])); + pixman_region32_t previous_selection; + if (term->selection.coords.end.row >= 0) { + previous_selection = pixman_region_for_coords( + term, + &term->selection.coords.start, + &term->selection.coords.end); + } else + pixman_region32_init(&previous_selection); - struct mark_context ctx = {.keep_selection = keep_selection}; + pixman_region32_t current_selection = pixman_region_for_coords( + term, &start, &end); - /* Premark all cells that *will* be selected */ - foreach_selected(term, start, end, &premark_selected, &ctx); - reset_modify_context(&ctx); + pixman_region32_t no_longer_selected; + pixman_region32_init(&no_longer_selected); + pixman_region32_subtract( + &no_longer_selected, &previous_selection, ¤t_selection); - if (term->selection.coords.end.row >= 0) { - /* Unmark previous selection, ignoring cells that are part of - * the new selection */ - foreach_selected(term, term->selection.coords.start, term->selection.coords.end, - &unmark_selected, &ctx); - reset_modify_context(&ctx); - } + pixman_region32_t newly_selected; + pixman_region32_init(&newly_selected); + pixman_region32_subtract( + &newly_selected, ¤t_selection, &previous_selection); + + /* Clear selection in cells no longer selected */ + int n_rects = -1; + pixman_box32_t *boxes = NULL; + + boxes = pixman_region32_rectangles(&no_longer_selected, &n_rects); + mark_selected_region(term, boxes, n_rects, false, true); + + boxes = pixman_region32_rectangles(&newly_selected, &n_rects); + mark_selected_region(term, boxes, n_rects, true, true); + + pixman_region32_fini(&newly_selected); + pixman_region32_fini(&no_longer_selected); + pixman_region32_fini(¤t_selection); + pixman_region32_fini(&previous_selection); term->selection.coords.start = start; term->selection.coords.end = end; - - /* Mark new selection */ - foreach_selected(term, start, end, &mark_selected, &ctx); render_refresh(term); - - for (size_t i = 0; i < term->grid->num_rows; i++) - free(keep_selection[i]); - free(keep_selection); } static void @@ -990,9 +1044,26 @@ selection_dirty_cells(struct terminal *term) if (term->selection.coords.start.row < 0 || term->selection.coords.end.row < 0) return; - foreach_selected( - term, term->selection.coords.start, term->selection.coords.end, &mark_selected, - &(struct mark_context){0}); + pixman_region32_t selection = pixman_region_for_coords( + term, &term->selection.coords.start, &term->selection.coords.end); + + pixman_region32_t view = pixman_region_for_coords( + term, + &(struct coord){0, term->grid->view}, + &(struct coord){term->cols - 1, term->grid->view + term->rows - 1}); + + pixman_region32_t visible_and_selected; + pixman_region32_init(&visible_and_selected); + pixman_region32_intersect(&visible_and_selected, &selection, &view); + + int n_rects = -1; + pixman_box32_t *boxes = + pixman_region32_rectangles(&visible_and_selected, &n_rects); + mark_selected_region(term, boxes, n_rects, true, false); + + pixman_region32_fini(&visible_and_selected); + pixman_region32_fini(&view); + pixman_region32_fini(&selection); } static void @@ -1270,6 +1341,19 @@ selection_finalize(struct seat *seat, struct terminal *term, uint32_t serial) } } +static bool +unmark_selected(struct terminal *term, struct row *row, struct cell *cell, + int row_no, int col, void *data) +{ + if (!cell->attrs.selected) + return true; + + row->dirty = true; + cell->attrs.selected = false; + cell->attrs.clean = false; + return true; +} + void selection_cancel(struct terminal *term) { @@ -1282,7 +1366,7 @@ selection_cancel(struct terminal *term) if (term->selection.coords.start.row >= 0 && term->selection.coords.end.row >= 0) { foreach_selected( term, term->selection.coords.start, term->selection.coords.end, - &unmark_selected, &(struct mark_context){0}); + &unmark_selected, NULL); render_refresh(term); } -- cgit v1.3