Scrollback buffer

[o-sdn-o]

From August 2021 I am rewriting the implementation of the scrollback buffer.
The following points are key in this work:

• Get scrollback height using new viewport_width after resize in constant O(1) time (for vertical scrolling)
• Get scrollback width using new viewport_width after resize in constant O(1) time (for horizontal scrolling non-wrapped lines)
• Get viewport absolute position
• Get viewport relative position

Notes

• Alternate Screen Buffer (DECSET 1049 ALTBUF)

To provide superluminal text output the alternate screen buffer mode should be implemented as a separate class with individual internal mechanics (implemented since d8c2c63).

The following aspects are key:

• ALTBUF mode doesn't require re-layout on resize: excess areas are simply cut off at the edge, and added ones are zeroed.
• No need to keep lines pushed up outside the viewport during output.
• All output lines are left-justified with auto-wrap (fixed style for all printed lines).
• Internally, the buffer in this mode is represented as a bitmap, and applications write directly to it without any intermediaries.

All further considerations do not apply to this mode.

• Scroll Region Feature (DECSTBM)

When the DECSTBM (scrolling region) mode is activated, the viewport is divided into three regions:

• Top margin
• Scrolling region
• Bottom margin

Scrolling region is the reduced area of the visible scrollback part.
The top and bottom margins are static areas of the viewport, in which all text manipulations are performed in the same way as in ALTBUF mode (internally, these areas are represented as a cell bitmap).

When the window is resized, the static areas are moved to maintain the coordinates of the position of the scroll region within the window. In this case, the fields can go beyond the window, this ensures the safety of their content with a sequential decrease and increase in the size of the window. A striking example of the advantages of this approach is resize during Debian APT apt execution - a minimum of garbage is generated during resizing when progress bar is present:

All lines scrolled up are saved in the scrollback buffer. If the user doesn't want this behavior, he should use ALTBUF mode.
The entire scrollback buffer can be scrolled with the mouse and all static areas remain frozen:

---

Built-in terminal can be configured to use an "unlimited" scrollback buffer (MAX_INT32 - 1 lines in the ring buffer).

Scrollback buffer setup:
CSI 24 : n : m p

• n — Initial buffer size in lines; 0 — grow step is used for initial size; default (if omitted) is 20.000
• m — Grow step for unlimited buffer; default (if omitted) is 0 — for fixed size buffer

I decided to abandon idea #61, because in some cases the text output is displayed incorrectly.
Now I'm doing some kind of full scrollback reflow on window resize, so that the result looks exactly as if it was originally outputted at such window size.

Line-by-line reflowing on insanely large scrollbacks requires infinite CPU resources to access the entire scrollback buffer, so full recalculation is unacceptable.

The idea of ​​calculating in constant O(1) time new parameters of the scrollback buffer during resizing is possible using an array of statistics of the lengths of text lines . Such an array is inexpensive to maintain in real time (std::unordered_map<int32_t length, int32_t count>[line_types_count=4] stat).

Note that we wrap text lines at the cell abstraction level, not at the word or grapheme level. I'm pretty sure grapheme- or word based wrapping is the application layer, not the terminal layer. See the core problem for all terminals #72 (comment) and #117 (comment).

Scrollback height

Line types

• left side aligned: height is always = 1
• right side aligned: height is always = 1 (required for RTL text support)
• centered: height is always = 1
• auto-wrapped any type of above: height = (line_length + viewport_width - 1) / viewport_width

Statistics of the number of lines for each length for each kind of line

• L(N) = stat[ left ][ N ]
• R(N) = stat[ right ][ N ]
• C(N) = stat[ centered ][ N ]
• W(N) = stat[ autowrapped ][ N ]

So
scrollback_height(viewport_width) = Sum_of(

• L(N) * 1
• R(N) * 1
• C(N) * 1
• W(N) * (N + viewport_width - 1) / viewport_width)
  )

The overhangs of the lines to the left and to the right outside the viewport (left_oversize and right_oversize for horizontal scrolling) are calculated using the maximums of the line lengths of the non-wrapped types.

centered_oversize(viewport_width) = (stat[centered].max_lenth() - viewport_width) / 2
    left_oversize(viewport_width) = max(centered_oversize, stat[right].max_lenth() - viewport_width)
   right_oversize(viewport_width) = max(centered_oversize, stat[left ].max_lenth() - viewport_width)

It is worth focusing on the following case:

• Moving the cursor to the top of the filled viewport followed by downsizing will push some of the lines down outside the viewport and form something like a future scrollback below the viewport bottom line. These lines are scrollable, but placed outside the viewport writing area until the cursor reaches them on its own in future (or after upsizing).

bottom_oversize(viewport_width) = max(0, scrollback_height(viewport_width)
                                         - cursor.y
                                         - viewport_height)

where cursor.y is the vertical position of the cursor in the scrollback buffer.

Example in bash:

$ ls /; echo -e "\e[4H"; cat
type something and resize the terminal window in multiple directions

We are shading lines that do not fit in the viewport at the bottom. We don't discard these lines, as it do VTE, rxvt-unicode, and many others. Also we don't lose the cursor position, as, for example, it happens in kitty or WT. Thus, no matter how you resize the terminal, it retains its original state.

Windows.Terminal.Dev.2021-09-07.18-37-29.1.mp4

Viewport positioning

...