aboutsummaryrefslogtreecommitdiff
path: root/grid.c (follow)
Commit message (Collapse)AuthorAgeLines
* composed: store compose chains in a binary search treeDaniel Eklöf2021-06-24-3/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The previous implementation stored compose chains in a dynamically allocated array. Adding a chain was easy: resize the array and append the new chain at the end. Looking up a compose chain given a compose chain key/index was also easy: just index into the array. However, searching for a pre-existing chain given a codepoint sequence was very slow. Since the array wasn’t sorted, we typically had to scan through the entire array, just to realize that there is no pre-existing chain, and that we need to add a new one. Since this happens for *each* codepoint in a grapheme cluster, things quickly became really slow. Things were ok:ish as long as the compose chain struct was small, as that made it possible to hold all the chains in the cache. Once the number of chains reached a certain point, or when we were forced to bump maximum number of allowed codepoints in a chain, we started thrashing the cache and things got much much worse. So what can we do? We can’t sort the array, because a) that would invalidate all existing chain keys in the grid (and iterating the entire scrollback and updating compose keys is *not* an option). b) inserting a chain becomes slow as we need to first find _where_ to insert it, and then memmove() the rest of the array. This patch uses a binary search tree to store the chains instead of a simple array. The tree is sorted on a “key”, which is the XOR of all codepoints, truncated to the CELL_COMB_CHARS_HI-CELL_COMB_CHARS_LO range. The grid now stores CELL_COMB_CHARS_LO+key, instead of CELL_COMB_CHARS_LO+index. Since the key is truncated, collisions may occur. This is handled by incrementing the key by 1. Lookup is of course slower than before, O(log n) instead of O(1). Insertion is slightly slower as well: technically it’s O(log n) instead of O(1). However, we also need to take into account the re-allocating the array will occasionally force a full copy of the array when it cannot simply be growed. But finding a pre-existing chain is now *much* faster: O(log n) instead of O(n). In most cases, the first lookup will either succeed (return a true match), or fail (return NULL). However, since key collisions are possible, it may also return false matches. This means we need to verify the contents of the chain before deciding to use it instead of inserting a new chain. But remember that this comparison was being done for each and every chain in the previous implementation. With lookups being much faster, and in particular, no longer requiring us to check the chain contents for every singlec chain, we can now use a dynamically allocated ‘chars’ array in the chain. This was previously a hardcoded array of 10 chars. Using a dynamic allocated array means looking in the array is slower, since we now need two loads: one to load the pointer, and a second to load _from_ the pointer. As a result, the base size of a compose chain (i.e. an “empty” chain) has now been reduced from 48 bytes to 32. A chain with two codepoints is 40 bytes. This means we have up to 4 codepoints while still using less, or the same amount, of memory as before. Furthermore, the Unicode random test (i.e. write random “unicode” chars) is now **faster** than current master (i.e. before text-shaping support was added), **with** test-shaping enabled. With text-shaping disabled, we’re _even_ faster.
* grid: reflow: ‘amount’ has already been added to ‘from’Daniel Eklöf2021-06-02-1/+1
|
* grid: reflow: URI range start: take over ownership of URI stringDaniel Eklöf2021-06-02-1/+2
| | | | | Instead of strdup:ing the URI, take over ownership. This is ok since the old URI range will be free:d anyway.
* grid: reflow: debug loggingDaniel Eklöf2021-06-02-12/+18
|
* grid: reflow: when determining row end coord, check *last* URI rangeDaniel Eklöf2021-06-02-1/+5
|
* grid: reflow: when determining row end coord, check *last* tracking pointDaniel Eklöf2021-06-02-2/+10
|
* grid: reflow: check the *entire* row for non-empty cellsDaniel Eklöf2021-06-02-1/+1
|
* grid: reflow: avoid unnecessary if-statements before chunking a rowDaniel Eklöf2021-06-02-8/+13
|
* grid: disable reflow timing by defaultDaniel Eklöf2021-06-02-1/+1
|
* grid: reflow: commentsDaniel Eklöf2021-06-02-1/+22
|
* grid: no need to keep the tp_col/uri_col variables aroundDaniel Eklöf2021-06-02-6/+3
|
* grid: fix col max calculation when row contains URI rangesDaniel Eklöf2021-06-02-1/+1
|
* grid: set tp/uri break flags explicitly when we know them to be trueDaniel Eklöf2021-06-02-6/+12
|
* grid: reflow: slightly simplified logic for end-coordinate calculationDaniel Eklöf2021-06-02-10/+8
|
* grid: reflow: rename _range -> rangeDaniel Eklöf2021-06-02-16/+16
|
* grid: reflow: remove dead codeDaniel Eklöf2021-06-02-135/+0
|
* grid: reflow: memcpy() chunks of cells, instead of single cell-by-cellDaniel Eklöf2021-06-02-1/+159
| | | | | | | | | | | | | | | | | | | | Instead of walking the old grid cell-by-cell, and checking for tracking points, OSC-8 URIs etc on each cell, memcpy() sequences of cells. For each row, find the end column, by scanning backward, looking for the first non-empty cell. Chunk the row based on tracking point coordinates. If there aren’t any tracking coordinates, or OSC-8 URIs on the current row, the entire row is copied in one go. The chunk of cells is copied to the new grid. We may have to split it up into multiple copies, since not all cells may fit on the current “new” row. Care must also be taken to not line break in the middle of a multi-column character.
* grid: don’t cut multi-column chars in half when resizing the alt screenDaniel Eklöf2021-06-02-1/+5
| | | | | | | | When we resize the alt screen, we don’t reflow the text, we simply truncate all the lines. When doing this, make sure we don’t truncate in the middle of a multi-column character.
* grid: reflow: uri-ranges: avoid looping URI ranges when reflowingDaniel Eklöf2021-05-23-54/+57
| | | | | | | | | | | | | | | | | | | | Since we know the following: * URI ranges are sorted * URI coordinates are unique * URI ranges don’t cross rows We can optimize URI range reflowing by: * Checking if the *first* URI range’s start coordinate is on the current column. If so, keep a pointer to it. * Use this pointer as source when instantiating the reflowed URI range * If we already have a non-NULL range pointer, check its end coordinate instead. * If it matches, close the *last* URI range we inserted on the new row, and free/remove the range from the old row. * When line breaking, we only need to check if the *last* URI range is unclosed.
* grid: row_add_uri_range: ensure the URIs are sortedDaniel Eklöf2021-05-22-1/+7
|
* grid: disable timing of resize operationsDaniel Eklöf2021-05-17-1/+1
|
* grid: reflow: free old rows as soon as we’re done with themDaniel Eklöf2021-05-17-3/+8
| | | | | | This reduces the memory cost of reflowing text, as we no longer needs to hold both the old and the new grid, in their entirety, in memory at the same time.
* grid: reflow: don’t initialize newly allocated rowsDaniel Eklöf2021-05-17-3/+9
| | | | | | | | | | | | | We’re going to write to it immediately anyway. In most cases, *all* newly allocated, and zero-initialized, cells are overwritten. So let’s skip the zero-initialization of the new cells. There are two cases where we need to explicitly clear cells now: * When inserting a hard line break - erase the remaining cells * When done, the *last* row may not have been completely written - erase the remaining cells
* grid: reflow: qsort_r() is not portableDaniel Eklöf2021-05-15-11/+15
| | | | Replace with qsort() + global variable. Not thread safe!
* grid: include <stdlib.h>, for qsort_r()Daniel Eklöf2021-05-15-0/+1
|
* grid: reflow: always run qsort_r(), handle rows == 0 in tp_cmp() insteadDaniel Eklöf2021-05-15-7/+5
|
* grid: take scrollback start into account when sorting the tracking points arrayDaniel Eklöf2021-05-15-9/+29
| | | | | | | | | | The row numbers in the tracking points are in absolute numbers. However, when we walk the old grid, we do so starting in the beginning of the scrollback history. We must ensure the tracking points are sorted such that the *first* one we see is the “oldest” one. I.e. the one furthest back in the scrollback history.
* grid: fix 32-bit compilationDaniel Eklöf2021-05-15-2/+4
|
* grid: reflow: tag tracking point if-statements with likely/unlikelyDaniel Eklöf2021-05-15-5/+5
|
* grid: reflow: use a sorted array for tracking pointsDaniel Eklöf2021-05-15-27/+66
| | | | | | | | | | | Instead of iterating a linked list of tracking points, for *each and every* cell in the old grid, use a sorted array. This allows us to step through the array of tracking points as we walk the old grid; each time we match a tracking point, we move to the next one. This means we only have to check a single tracking point for each cell.
* grid: reflow: no need to check for combining charactersDaniel Eklöf2021-05-14-21/+10
| | | | Since we no longer call wcwidth(), we don’t need the base character.
* grid: don’t depend on wcwidth()Daniel Eklöf2021-05-14-41/+45
| | | | | | | | | | | | | | | | Calling wcwidth() on every character in the entire scrollback history is slow. We already have the character width encoded in the grid; it’s in the CELL_SPACERs following a multi-column character. Thus, when we see a non-SPACER character, that isn’t in the last column, peek the next character. If it’s a SPACER, get the current characters width from it. The only thing we need the width for, is to be able to print padding SPACERS in the right margin, if the there isn’t enough space on the current row for the current character.
* term: rename CELL_MULT_COL_SPACER -> CELL_SPACER, and change its definitionDaniel Eklöf2021-05-14-5/+5
| | | | | | | | | | | | | | | | | | | | | Instead of using CELL_SPACER for *all* cells that previously used CELL_MULT_COL_SPACER, include the remaining number of spacers following, and including, itself. This is encoded by adding to the CELL_SPACER value. So, a double width character will now store the character itself in the first cell (just like before), and CELL_SPACER+1 in the second cell. A three-cell character would store the character itself, then CELL_SPACER+2, and finally CELL_SPACER+1. In other words, the last spacer is always CELL_SPACER+1. CELL_SPACER+0 is used when padding at the right margin. I.e. when writing e.g. a double width character in the last column, we insert a CELL_SPACER+0 pad character, and then write the double width character in the first column on the next row.
* grid: add compile-time define to enable timing of the reflow operationDaniel Eklöf2021-05-14-0/+17
|
* grid: snapshot: don’t mark all cells as dirty - copy state from source gridDaniel Eklöf2021-02-26-3/+1
|
* csi: remove extra ‘;’Daniel Eklöf2021-02-26-1/+1
|
* grid: snapshot: copy scroll damageDaniel Eklöf2021-02-26-0/+3
|
* grid: grid_free(): free scroll damage listDaniel Eklöf2021-02-26-0/+1
|
* grid: add grid_snapshot()Daniel Eklöf2021-02-26-0/+82
| | | | This function deep copies a grid into a newly *allocated* grid struct.
* grid: add grid_free()Daniel Eklöf2021-02-26-0/+14
|
* grid: reflow_uri_ranges(): URI end point is *inclusive*Daniel Eklöf2021-02-25-1/+1
| | | | | | | | | Which means, when we match URI start and end points against the current column index, we must *not* use ‘if...else if’, but two ‘if... if’. Fixes an assertion when resizing a window with an URI range of just one cell.
* grid: refactor: break out allocation of ‘extra’ member to separate functionDaniel Eklöf2021-02-21-2/+7
|
* grid: refactor: use grid_row_add_uri_range()Daniel Eklöf2021-02-21-12/+3
|
* grid: add new function grid_row_add_uri_range()Daniel Eklöf2021-02-21-0/+9
|
* grid: resize_without_reflow: allocate ‘extra’ on-demand on ‘new’ rowsDaniel Eklöf2021-02-21-1/+2
| | | | | Even if we have URI ranges on the old row, all those ranges may lay outside the new grid’s range.
* grid: grid_resize_without_reflow: transfer URI rangesDaniel Eklöf2021-02-21-1/+21
|
* grid: reflow: translate URI rangesDaniel Eklöf2021-02-21-22/+137
| | | | | | | | | | URI ranges are per row. Translate by detecting URI range start/end coordinates, and opening and closing a corresponding URI range on the new grid. We need to take care when line-wrapping the new grid; here we need to manually close the still-open URI ranges (on the new grid), and re-opening them on the next row.
* grid: grid_row_free(): use grid_row_reset_extra()Daniel Eklöf2021-02-21-7/+1
|
* grid: enable rows to have ‘extra’ data associated with themDaniel Eklöf2021-02-21-0/+9
| | | | | | | | | | | This patch adds an ‘extra’ member to the row struct. It is a pointer to a struct containing extra data to be associated with this row. Initially, this struct contains a list of URL ranges. These define (OSC-8) URLs on this row. The ‘extra’ data is allocated on-demand. I.e. the pointer is NULL by default; it is *not* allocated by grid_row_alloc().
* debug: rename assert() to xassert(), to avoid clashing with <assert.h>Craig Barnes2021-01-16-10/+10
|
* Print stack trace on assert() failure or when calling fatal_error()Craig Barnes2021-01-16-1/+1
| | | | | | Note: this uses the __sanitizer_print_stack_trace() function from the AddressSanitizer runtime, so it only works when AddressSanitizer is in use.
* grid: resize_without_reflow: don’t call min() on every loop iterationDaniel Eklöf2020-11-25-1/+1
|
* resize: don’t reflow text on alt screenDaniel Eklöf2020-11-25-9/+122
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Alt screen applications normally reflow/readjust themselves on a window resize. When we do it too, the result is graphical glitches/flashes since our re-flowed text is rendered in one frame, and the application re-flowed text soon thereafter. We can’t avoid rendering some kind of re-flowed frame, since we don’t know when, or even if, the application will update itself. To avoid glitches, we need to render, as closely as possible, what the application itself will render shortly. This is actually pretty simple; we just need to copy the visible content over from the old grid to the new grid. We don’t bother with text re-flow, but simply truncate long lines. To simplify things, we simply cancel any active selection (since often times, it will be corrupted anyway when the application redraws itself). Since we’re not reflowing text, there’s no need to translate e.g. the cursor position - we just keep the current position (but bounded to the new dimensions). Fun thing: ‘less’ gets corrupted if we don’t leave the cursor at the (new) bottom row. To handle this, we check if the cursor (before resize) is at the bottom row, and if so, we move it to the new bottom row. Closes #221
* sixel: implement reflowDaniel Eklöf2020-10-09-54/+1
| | | | | | | Move sixel reflow from grid_reflow() to sixel_reflow(). This lets us use internal sixel functions to update the sixels. Note that grid_reflow() still needs to remap the sixelss coordinates.
* grid: reflow: re-insert sixels *after* new grid offset has been setDaniel Eklöf2020-10-09-40/+51
| | | | | | Also make sure to destroy sixels that are too big to fit in the scrollback. Fixes issues with the sixel list not being sorted correctly.
* grid: reflow: fix release build; ‘idx’ is only used in an assert()Daniel Eklöf2020-09-29-1/+2
|
* grid: reflow: handle viewport being too far down when enlarging the windowDaniel Eklöf2020-09-29-2/+17
| | | | | | If the viewport is close to the bottom, but not *at* the bottom, and we’re enlarging the window, the translated viewport will be too far down.
* grid: reflow: retain scrollback positionDaniel Eklöf2020-09-29-1/+10
| | | | Closes #142
* grid: reflow: make sure cursor is within the visible screen areaDaniel Eklöf2020-09-10-6/+4
| | | | | | | | Even though we translate the cursor position from the old grid coordinates to the new, the cursor may _still_ end up outside the visible area. Make sure it doesn’t.
* grid: reflow: calculate width of composed characters correctlyDaniel Eklöf2020-09-06-4/+20
| | | | | Before this patch, reflow called `wcwidth()` on our magic values for composed characters.
* Convert most dynamic allocations to use functions from xmalloc.hCraig Barnes2020-08-08-4/+5
|
* grid: reflow: don't insert <width> spacer cells for *every* empty cellDaniel Eklöf2020-08-04-7/+8
| | | | Only do it for the last, non-empty cell.
* grid: reflow: use macro print_spacer() to insert multi-column character spacersDaniel Eklöf2020-07-14-8/+11
|
* grid: reflow: handle multi column character spacersDaniel Eklöf2020-07-14-2/+22
| | | | | | | | | Ignore *old* cells containing spacers. Pad new grid with spacers if a multi-column character doesn't fit at the end of a line. Insert spacers after a multi-column character.
* grid: reflow: always emit *all* cells of a multi-column characterDaniel Eklöf2020-07-14-1/+7
|
* grid: reflow: use width=1 for invalid charactersDaniel Eklöf2020-07-14-1/+1
|
* grid: reflow: force line-wrap if a multi-column character does not fit on current lineDaniel Eklöf2020-07-14-14/+1
|
* reflow: ensure sixels are correctly sorted when re-insertedDaniel Eklöf2020-06-29-32/+62
| | | | | And make sure to remove re-inserted sixels that has wrapped around the scrollback (this may happen when the window size decreases).
* grid: reflow: delete sixels that end up crossing the scrollback wrap aroundDaniel Eklöf2020-06-27-5/+6
| | | | | | | | Our sixel handling code requires sixels to *not* cross the scrollback wrap around. Until we've fixes the reflow code that split up such sixels (much like we do when we generate a sixel), simply delete it.
* grid: add TODO, and an assert, that sixels must not cross wrap-aroundDaniel Eklöf2020-06-27-0/+4
|
* grid: swap_row: remove unused parameter 'initialize'Daniel Eklöf2020-05-16-1/+1
|
* unicode-combining: store seen combining chains "globally" in the term structDaniel Eklöf2020-05-03-22/+1
| | | | | | | | | | | | | | | | | | | | Instead of storing combining data per cell, realize that most combinations are re-occurring and that there's lots of available space left in the unicode range, and store seen base+combining combinations chains in a per-terminal array. When we encounter a combining character, we first try to pre-compose, like before. If that fails, we then search for the current base+combining combo in the list of previously seen combinations. If not found there either, we allocate a new combo and add it to the list. Regardless, the result is an index into this array. We store this index, offsetted by COMB_CHARS_LO=0x40000000ul in the cell. When rendering, we need to check if the cell character is a plain character, or if it's a composed character (identified by checking if the cell character is >= COMB_CHARS_LO). Then we render the grapheme pretty much like before.
* unicode-combine: remove utf8proc dependencyDaniel Eklöf2020-05-02-4/+4
| | | | | | | | | | | | We only used utf8proc to try to pre-compose a glyph from a base and combining character. We can do this ourselves by using a pre-compiled table of valid pre-compositions. This table isn't _that_ big, and binary searching it is fast. That is, for a very small amount of code, and not too much extra RO data, we can get rid of the utf8proc dependency.
* unicode-combining: completely remove unicode combining characters when feature is disabledDaniel Eklöf2020-05-01-0/+8
|
* grid: reflow: copy combining charactersDaniel Eklöf2020-05-01-0/+9
|
* grid: add per-cell combining charactersDaniel Eklöf2020-05-01-1/+5
| | | | | | | | | | The data is *not* added to the cell struct, since that one is too performance critical. Instead, the data is added as a separate array in the row struct. This allows our performance critical code paths that e.g. clear cells to perform as before.
* util.h: new header file defining commonly used macrosDaniel Eklöf2020-05-01-2/+1
|
* grid: reflow: make tracking_points array 'const'Daniel Eklöf2020-04-17-1/+1
| | | | | The elements aren't, and cannot be, const. But the array itself can, and should be.
* grid: reflow: caller may now pass a list of coordinates that should be translatedDaniel Eklöf2020-04-17-1/+6
|
* grid: reflow: generalize cursor coordinate translationDaniel Eklöf2020-04-17-26/+41
| | | | | | | | | | | Define a list of "tracking points" - coordinates that should be translated while reflowing. Add the cursor coordinates to this list. When a coordinate have been translated, it is removed from the list. This means we don't have to create a copy of the 'cursor' coordinate struct.
* grid: reflow: remove commented out codeDaniel Eklöf2020-04-17-2/+0
|
* grid: reflow: turn line-wrapping code into a macroDaniel Eklöf2020-04-17-24/+19
|
* grid: reflow: don't randomly insert hard linebreaksDaniel Eklöf2020-04-17-0/+2
| | | | | Not sure why I added this code; maybe to workaround issues caused by the fact that the cursor position wasn't properly translated.
* grid: grid_reflow() now translates cursor coordinatesDaniel Eklöf2020-04-16-7/+51
|
* sixel: improve handling of images when reflowing the gridsDaniel Eklöf2020-03-13-0/+35
| | | | | | | | | | | Update the sixels' 'row' attribute when re-flowing a grid, to ensure it is rendered at the correct place. This should work in most cases, but will break when the cell size has changed (e.g. font size increase/decrease, or a DPI change). This patch also moves the sixel image list from the terminal struct into the grid struct. The sixels are per-grid after all.
* grid: grid_reflow(): may be called with old_rows/cols == new_rows/colsDaniel Eklöf2020-02-25-1/+1
| | | | TODO: avoid calling grid_reflow() in this case.
* render/grid: move grid reflow code to grid.cDaniel Eklöf2020-02-15-1/+145
|
* term: convert cell 'linefeed' attribute to a row 'linebreak' propertyDaniel Eklöf2020-02-14-0/+1
| | | | | | | | | | | | | | | | To do text reflow, we only need to know if a line has been explicitly linebreaked or not. If not, that means it wrapped, and that we should *not* insert a linebreak when reflowing text. When reflowing text, when reaching the end of a row in the old grid, only insert a linebreak in the new grid if the old row had been explicitly linebreaked. Furthermore, when reflowing text and wrapping a row in the new grid, mark the previous row as linebreaked if either the last cell was (the last column in the last row) empty, or the current cell (the first column in the new row) is empty. If both are non-empty, then we assume a linewrap.
* grid: remove commented out codeDaniel Eklöf2019-08-23-6/+1
|
* scrolling: optimize row access by assuming number of rows is a power of 2Daniel Eklöf2019-08-22-14/+23
| | | | | | | | | | | | | | | | | | | With this assumption, we can replace 'a % b' with 'a & (b - 1)'. In terms of instructions, this means a fast 'and' instead of a slow 'div'. Further optimize scrolling by: * not double-initializing empty rows. Previously, grid_row_alloc() called calloc(), which was then followed by a memset() when scrolling. This is of course unnecessary. * Don't loop the entire set of visible rows (this was done to ensure all visible rows had been allocated, and to prefetch the cell contents). This isn't necessary; only newly pulled in rows can be NULL. For now, don't prefetch at all.
* render: add a 'clean' bit to each cell; only render cells that aren't cleanDaniel Eklöf2019-07-30-0/+2
| | | | | | | | | | | This patch takes a bit from the foreground color value in a cell (todo: split up foreground/background into bitfields with a separate field for 'foreground/background' has been set), and only re-renders cells that aren't marked as clean. Note: we use a 'clean' bit rather than a 'dirty' bit to make it easy to erase cells - we can (keep doing) do that by simply memsetting a cell range to 0.
* grid: swap rows doesn't mark rows as dirtyDaniel Eklöf2019-07-23-3/+0
|
* grid: swap_row: drop requirement that row indices be positiveDaniel Eklöf2019-07-10-2/+3
|
* grid: don't pre-allocate the entire grid (with all scrollback lines)Daniel Eklöf2019-07-10-0/+19
| | | | | | | | | | The row array may now contain NULL pointers. This means the corresponding row hasn't yet been allocated and initialized. On a resize, we explicitly allocate the visible rows. Uninitialized rows are then allocated the first time they are referenced.
* grid: don't implement grid_swap_row() in the header fileDaniel Eklöf2019-07-10-78/+13
|
* wip: grid is now represented as a grid, not a linear arrayDaniel Eklöf2019-07-08-1/+2
| | | | | | | | | | | | The grid is now represented with an array of row *pointers*. Each row contains an array of cells (the row's columns). The main point of having row pointers is we can now move rows around almost for free. This is useful when scrolling with scroll margins for example, where we previously had to copy the lines in the margins. Now it's just a matter of swapping two pointers.
* grid: add a fast path to grid_memmove()Daniel Eklöf2019-07-07-0/+13
| | | | | Recognize the case where both the destination and source can be fully accessed, and to a plain memmove() in this case.
* grid: grid_memset() -> grid_memclear()Daniel Eklöf2019-07-07-2/+2
|
* logging: disable debug logging by defaultDaniel Eklöf2019-07-03-1/+1
|
* scrolling: initial reverse scrolling support - no scroll regionsDaniel Eklöf2019-07-03-10/+13
|