From 61b43620fcd2720cb893902e189a60be2bec1b99 Mon Sep 17 00:00:00 2001 From: Daniel Eklöf Date: Mon, 10 Feb 2020 20:35:24 +0100 Subject: render: initial support for text reflow The algorithm is as follows: Start at the beginning of the scrollback. That is, at the oldest emitted lines. This is done by taking the current offset, and adding the number of (old) screen rows, and then iterating until we find the first allocated line. Next, we iterate the entire old grid. At the beginning, we allocate a line for the new grid, and setup a global pointer for that line, and the current cell index. For each line in the old grid, iterate its cells. Copy the the cells over to the new line. Whenever the new line reaches its maximum number of columns, we line break it by increasing the current row index and allocating a new row (if necessary - we may be overwriting old scrollback if the new grid is smaller than the old grid). Whenever we reach the end of a line of the old grid, we insert a line break in the new grid's line too **if** the last cell in the old line was empty. If it was **not** empty, we **don't** line break the new line. Furthermore, empty cells in general need special consideration. A line ending with a string of empty cells doesn't have to be copied the new line. And more importantly, should **not** increase the new line's cell index (which may cause line breaks, which is incorrect). However, if a string of empty cells is followed by non empty cells, we need to copy all the preceding empty cells to the line too. When the entire scrollback history has been reflowed, we need to figure out the new grid's offset. This is done by trying to put the **last** emitted line at the bottom of the screen. I.e. the new offset is typically "last_line_idx - term->rows". However, we need to handle empty lines. So, after subtracting the number of screen rows, we _increase_ the offset until we see a non-empty line. This ensures we handle grid's that doesn't fill an entire screen. Finally, we need to re-position the cursor. This is done by trying to place the cursor **at** (_not_ after) the last emitted line. We keep the current cursor column as is (but possibly truncated, if the grid's width decreased). --- render.c | 179 ++++++++++++++++++++++++++++++++++++++++++++++++++------------- 1 file changed, 142 insertions(+), 37 deletions(-) (limited to 'render.c') diff --git a/render.c b/render.c index 7fa7dd86..f3eb76ef 100644 --- a/render.c +++ b/render.c @@ -970,28 +970,106 @@ render_search_box(struct terminal *term) wl_surface_commit(term->window->search_surface); } -static void -reflow(struct row **new_grid, int new_cols, int new_rows, - struct row *const *old_grid, int old_cols, int old_rows) +static int +reflow(struct terminal *term, struct row **new_grid, int new_cols, int new_rows, + struct row *const *old_grid, int old_cols, int old_rows, int offset) { - /* TODO: actually reflow */ - for (int r = 0; r < min(new_rows, old_rows); r++) { - size_t copy_cols = min(new_cols, old_cols); - size_t clear_cols = new_cols - copy_cols; + int new_col_idx = 0; + int new_row_idx = 0; + + struct row *new_row = new_grid[new_row_idx]; + if (new_row == NULL) { + new_row = grid_row_alloc(new_cols, true); + new_row->dirty = true; + new_grid[new_row_idx] = new_row; + } + + /* Start at the beginning of the old grid's scrollback. That is, + * at the output that is *oldest* */ + offset += term->rows; - if (old_grid[r] == NULL) + /* + * Walk the old grid + */ + for (int r = 0; r < old_rows; r++) { + + /* Unallocated (empty) rows we can simply skip */ + const struct row *old_row = old_grid[(offset + r) & (old_rows - 1)]; + if (old_row == NULL) continue; - if (new_grid[r] == NULL) - new_grid[r] = grid_row_alloc(new_cols, false); + /* + * Keep track of empty cells. If the old line ends with a + * string of empty cells, we don't need to, nor do we want to, + * add those to the new line. However, if there are non-empty + * cells *after* the string of empty cells, we need to emit + * the empty cells too. And that may trigger linebreaks + */ + int empty_count = 0; + + /* Walk current line of the old grid */ + for (int c = 0; c < old_cols; c++) { + const struct cell *old_cell = &old_row->cells[c]; + + if (old_cell->wc == 0) { + empty_count++; + continue; + } + + assert(old_cell->wc != 0); + + /* Non-empty cell. Emit preceeding string of empty cells, + * and possibly line break for current cell */ + + for (int i = 0; i < empty_count + 1; i++) { + if (new_col_idx >= new_cols) { + new_col_idx = 0; + new_row_idx = (new_row_idx + 1) & (new_rows - 1); + + new_row = new_grid[new_row_idx]; + if (new_row == NULL) { + new_row = grid_row_alloc(new_cols, true); + new_row->dirty = true; + new_grid[new_row_idx] = new_row; + } + } + + new_row->cells[new_col_idx].attrs.clean = 1; + new_row->cells[new_col_idx++] = (struct cell){0}; + } + + empty_count = 0; + new_col_idx--; - struct cell *new_cells = new_grid[r]->cells; - const struct cell *old_cells = old_grid[r]->cells; + assert(new_row != NULL); + assert(new_col_idx >= 0); + assert(new_col_idx < new_cols); - new_grid[r]->dirty = old_grid[r]->dirty; - memcpy(new_cells, old_cells, copy_cols * sizeof(new_cells[0])); - memset(&new_cells[copy_cols], 0, clear_cols * sizeof(new_cells[0])); + /* Copy current cell */ + new_row->cells[new_col_idx].attrs.clean = 1; + new_row->cells[new_col_idx++] = *old_cell; + } + + /* + * If last cell of the old grid's line if empty, then we + * insert a linebreak in the new grid's line too. Unless, the + * *entire* old line was empty. + */ + + if (empty_count < old_cols && old_row->cells[old_cols - 1].wc == 0) { + new_col_idx = 0; + new_row_idx = (new_row_idx + 1) & (new_rows - 1); + + new_row = new_grid[new_row_idx]; + if (new_row == NULL) { + new_row = grid_row_alloc(new_cols, true); + new_row->dirty = true; + new_grid[new_row_idx] = new_row; + } + } } + + return new_row_idx; } /* Move to terminal.c? */ @@ -1045,31 +1123,52 @@ maybe_resize(struct terminal *term, int width, int height, bool force) term->x_margin = (term->width - new_cols * term->cell_width) / 2; term->y_margin = (term->height - new_rows * term->cell_height) / 2; - term->normal.offset %= new_normal_grid_rows; - term->normal.view %= new_normal_grid_rows; - - term->alt.offset %= new_alt_grid_rows; - term->alt.view %= new_alt_grid_rows; - - /* Allocate new 'normal' grid */ + /* Allocate new 'normal' and 'alt' grids */ struct row **normal = calloc(new_normal_grid_rows, sizeof(normal[0])); - for (int r = 0; r < new_rows; r++) { - size_t real_r = (term->normal.view + r) & (new_normal_grid_rows - 1); - normal[real_r] = grid_row_alloc(new_cols, true); - } - - /* Allocate new 'alt' grid */ struct row **alt = calloc(new_alt_grid_rows, sizeof(alt[0])); - for (int r = 0; r < new_rows; r++) { - int real_r = (term->alt.view + r) & (new_alt_grid_rows - 1); - alt[real_r] = grid_row_alloc(new_cols, true); - } /* Reflow content */ - reflow(normal, new_cols, new_normal_grid_rows, - term->normal.rows, old_cols, old_normal_grid_rows); - reflow(alt, new_cols, new_alt_grid_rows, - term->alt.rows, old_cols, old_alt_grid_rows); + int last_normal_row = reflow( + term, normal, new_cols, new_normal_grid_rows, + term->normal.rows, old_cols, old_normal_grid_rows, term->normal.offset); + int last_alt_row = reflow( + term, alt, new_cols, new_alt_grid_rows, + term->alt.rows, old_cols, old_alt_grid_rows, term->alt.offset); + + /* Re-set current row pointers */ + term->normal.cur_row = normal[last_normal_row]; + term->alt.cur_row = alt[last_alt_row]; + + /* Reset offset such that the last copied row ends up at the + * bottom of the screen */ + term->normal.offset = last_normal_row - new_rows; + term->alt.offset = last_alt_row - new_rows; + + /* Can't have negative offsets, so wrap 'em */ + while (term->normal.offset < 0) + term->normal.offset += new_normal_grid_rows; + while (term->alt.offset < 0) + term->alt.offset += new_alt_grid_rows; + + /* Make sure offset doesn't point to empty line */ + while (normal[term->normal.offset] == NULL) + term->normal.offset = (term->normal.offset + 1) & (new_normal_grid_rows - 1); + while (alt[term->alt.offset] == NULL) + term->alt.offset = (term->alt.offset + 1) & (new_alt_grid_rows - 1); + + term->normal.view = term->normal.offset; + term->alt.view = term->alt.offset; + + /* Make sure all visible lines have been allocated */ + for (int r = 0; r < new_rows; r++) { + int idx = (term->normal.offset + r) & (new_normal_grid_rows - 1); + if (normal[idx] == NULL) + normal[idx] = grid_row_alloc(new_cols, true); + + idx = (term->alt.offset + r) & (new_alt_grid_rows - 1); + if (alt[idx] == NULL) + alt[idx] = grid_row_alloc(new_cols, true); + } /* Free old 'normal' grid */ for (int r = 0; r < term->normal.num_rows; r++) @@ -1117,9 +1216,15 @@ maybe_resize(struct terminal *term, int width, int height, bool force) if (term->scroll_region.end >= old_rows) term->scroll_region.end = term->rows; + /* Position cursor at the last copied row */ + /* TODO: can we do better? */ + int cursor_row = term->grid == &term->normal + ? last_normal_row - term->normal.offset - 1 + : last_alt_row - term->alt.offset - 1; + term_cursor_to( term, - min(term->cursor.point.row, term->rows - 1), + min(max(cursor_row, 0), term->rows - 1), min(term->cursor.point.col, term->cols - 1)); term->render.last_cursor.cell = NULL; -- cgit v1.3 From 80e8f912701b7b6365aafee5c849d827352a0a11 Mon Sep 17 00:00:00 2001 From: Daniel Eklöf Date: Mon, 10 Feb 2020 20:46:02 +0100 Subject: render: reflow: no need to clear cells We set initialize=true when allocating a new row. This initializes the cell to 0, with clean=1. --- render.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'render.c') diff --git a/render.c b/render.c index f3eb76ef..de81adc7 100644 --- a/render.c +++ b/render.c @@ -1034,8 +1034,7 @@ reflow(struct terminal *term, struct row **new_grid, int new_cols, int new_rows, } } - new_row->cells[new_col_idx].attrs.clean = 1; - new_row->cells[new_col_idx++] = (struct cell){0}; + new_col_idx++; } empty_count = 0; -- cgit v1.3 From 4a169f5643a5fae6ab2df39adeb32a3222d2811c Mon Sep 17 00:00:00 2001 From: Daniel Eklöf Date: Mon, 10 Feb 2020 21:52:14 +0100 Subject: vt: tag cells that were form-feed:ed, to allow correct text reflow To handle text reflow correctly when a line has a printable character in the last column, but was still line breaked, we need to track the fact that the slave inserted a line break here. Otherwise, when the window width is increased, we'll end up pulling up the next line, when we really should have inserted a line break. --- render.c | 5 ++++- terminal.c | 8 ++++++++ terminal.h | 4 +++- vt.c | 4 ++-- 4 files changed, 17 insertions(+), 4 deletions(-) (limited to 'render.c') diff --git a/render.c b/render.c index de81adc7..2fb4d6cf 100644 --- a/render.c +++ b/render.c @@ -1055,7 +1055,10 @@ reflow(struct terminal *term, struct row **new_grid, int new_cols, int new_rows, * *entire* old line was empty. */ - if (empty_count < old_cols && old_row->cells[old_cols - 1].wc == 0) { + if (empty_count < old_cols && + (old_row->cells[old_cols - 1].wc == 0 || + old_row->cells[old_cols - 1].attrs.linefeed)) + { new_col_idx = 0; new_row_idx = (new_row_idx + 1) & (new_rows - 1); diff --git a/terminal.c b/terminal.c index a07b1912..5c9f0b8b 100644 --- a/terminal.c +++ b/terminal.c @@ -1494,6 +1494,14 @@ term_scroll_reverse(struct terminal *term, int rows) term_scroll_reverse_partial(term, term->scroll_region, rows); } +void +term_formfeed(struct terminal *term) +{ + if (term->cursor.point.col > 0) + term->grid->cur_row->cells[term->cursor.point.col - 1].attrs.linefeed = 1; + term_cursor_left(term, term->cursor.point.col); +} + void term_linefeed(struct terminal *term) { diff --git a/terminal.h b/terminal.h index b4ce1212..449a1329 100644 --- a/terminal.h +++ b/terminal.h @@ -42,7 +42,8 @@ struct attributes { uint32_t have_fg:1; uint32_t have_bg:1; uint32_t selected:2; - uint32_t reserved:3; + uint32_t linefeed:1; + uint32_t reserved:2; uint32_t bg:24; }; static_assert(sizeof(struct attributes) == 8, "bad size"); @@ -403,6 +404,7 @@ void term_scroll_partial( void term_scroll_reverse_partial( struct terminal *term, struct scroll_region region, int rows); +void term_formfeed(struct terminal *term); void term_linefeed(struct terminal *term); void term_reverse_index(struct terminal *term); diff --git a/vt.c b/vt.c index 06445e4c..3cdd5b24 100644 --- a/vt.c +++ b/vt.c @@ -128,7 +128,7 @@ action_execute(struct terminal *term, uint8_t c) case '\r': /* FF - form feed */ - term_cursor_left(term, term->cursor.point.col); + term_formfeed(term); break; case '\b': @@ -361,8 +361,8 @@ action_esc_dispatch(struct terminal *term, uint8_t final) break; case 'E': + term_formfeed(term); term_linefeed(term); - term_cursor_left(term, term->cursor.point.col); break; case 'H': -- cgit v1.3 From 8d262e71c1afb0c94899e60f63c9a05dff439747 Mon Sep 17 00:00:00 2001 From: Daniel Eklöf Date: Mon, 10 Feb 2020 22:36:17 +0100 Subject: render: reflow: initial line is always unallocated --- render.c | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) (limited to 'render.c') diff --git a/render.c b/render.c index 2fb4d6cf..864881a3 100644 --- a/render.c +++ b/render.c @@ -978,11 +978,11 @@ reflow(struct terminal *term, struct row **new_grid, int new_cols, int new_rows, int new_row_idx = 0; struct row *new_row = new_grid[new_row_idx]; - if (new_row == NULL) { - new_row = grid_row_alloc(new_cols, true); - new_row->dirty = true; - new_grid[new_row_idx] = new_row; - } + + assert(new_row == NULL); + new_row = grid_row_alloc(new_cols, true); + new_row->dirty = true; + new_grid[new_row_idx] = new_row; /* Start at the beginning of the old grid's scrollback. That is, * at the output that is *oldest* */ -- cgit v1.3 From 3ad2ee768181bbcb01d9e42ed7dca14b551e9020 Mon Sep 17 00:00:00 2001 From: Daniel Eklöf Date: Mon, 10 Feb 2020 22:36:39 +0100 Subject: render: resize: fix cursor positioning at grid wrap around When current view is at a grid wrap around (last emitted row index is < grid offset), the cursor row ended up being negative which we then mapped to the top line. This is wrong. When we're at a wrap around, re-adjust cursor by adding the grid's row count. --- render.c | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-) (limited to 'render.c') diff --git a/render.c b/render.c index 864881a3..9149dc2c 100644 --- a/render.c +++ b/render.c @@ -1221,8 +1221,12 @@ maybe_resize(struct terminal *term, int width, int height, bool force) /* Position cursor at the last copied row */ /* TODO: can we do better? */ int cursor_row = term->grid == &term->normal - ? last_normal_row - term->normal.offset - 1 - : last_alt_row - term->alt.offset - 1; + ? last_normal_row - term->normal.offset + : last_alt_row - term->alt.offset; + + while (cursor_row < 0) + cursor_row += term->grid->num_rows; + cursor_row--; term_cursor_to( term, -- cgit v1.3 From 88e2ab21b3ac2e352b0496df4403cc8a5f029a8b Mon Sep 17 00:00:00 2001 From: Daniel Eklöf Date: Mon, 10 Feb 2020 22:38:30 +0100 Subject: render: reflow: clear new line if already allocated --- render.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'render.c') diff --git a/render.c b/render.c index 9149dc2c..9218527e 100644 --- a/render.c +++ b/render.c @@ -1031,7 +1031,8 @@ reflow(struct terminal *term, struct row **new_grid, int new_cols, int new_rows, new_row = grid_row_alloc(new_cols, true); new_row->dirty = true; new_grid[new_row_idx] = new_row; - } + } else + memset(new_row->cells, 0, new_cols * sizeof(new_row->cells[0])); } new_col_idx++; -- cgit v1.3 From e56523f326a8c883b582d9cf5e25b0f48f9783dd Mon Sep 17 00:00:00 2001 From: Daniel Eklöf Date: Mon, 10 Feb 2020 22:40:16 +0100 Subject: render: resize: calculated cursor row *should* never be beyond the screen bottom --- render.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'render.c') diff --git a/render.c b/render.c index 9218527e..4aac652a 100644 --- a/render.c +++ b/render.c @@ -1229,9 +1229,10 @@ maybe_resize(struct terminal *term, int width, int height, bool force) cursor_row += term->grid->num_rows; cursor_row--; + assert(cursor_row < term->rows); term_cursor_to( term, - min(max(cursor_row, 0), term->rows - 1), + max(cursor_row, 0), min(term->cursor.point.col, term->cols - 1)); term->render.last_cursor.cell = NULL; -- cgit v1.3