Reimplement TextBuffer::Reflow by lhecker · Pull Request #15701 · microsoft/terminal

lhecker · 2023-07-12T21:13:48Z

Subjectively speaking, this commit makes 3 improvements:

Most importantly, it now would work with arbitrary Unicode text.
(No more IsGlyphFullWidth or DBCS handling during reflow.)
Due to the simpler implementation it hopefully makes review of
future changes and maintenance simpler. (~3x less LOC.)
It improves perf. by 1-2 orders of magnitude.
(At 120x9001 with a full buffer I get 60ms -> 2ms.)

Unfortunately, I'm not confident that the new code replicates the old
code exactly, because I failed to understand it. During development
I simply tried to match its behavior with what I think reflow should do.

Closes #797
Closes #3088
Closes #4968
Closes #6546
Closes #6901
Closes #15964
Closes MSFT:19446208

Related to #5800 and #8000

Validation Steps Performed

Unit tests ✅
Feature tests ✅
Reflow with a scrollback ✅
Reflowing the cursor cell causes a forced line-wrap ✅
(Even at the end of the buffer. ✅)
color 8f and reflowing retains the background color ✅
Enter alt buffer, Resize window, Exit alt buffer ✅

lhecker · 2023-08-15T14:01:38Z

I fixed all the bugs that were obvious enough that I could find them. It'd be super helpful if anyone else could give this PR/branch a look. But it might be easiest to just put it into our test builds.

lhecker · 2023-08-15T14:02:43Z

src/buffer/out/Row.cpp

+    };
+    CopyTextFrom(state);
+
+    TransferAttributes(source.Attributes(), _columnCount);


This change ensures that we take the line rendition into account when determining the capacity of the row in CopyTextFrom.

lhecker · 2023-08-15T14:03:12Z

src/buffer/out/Row.cpp

 til::CoordType ROW::NavigateToNext(til::CoordType column) const noexcept
 {
-    return _adjustForward(_clampedColumn(column + 1));
+    return _adjustForward(_clampedColumnInclusive(column + 1));


This will allow us to "navigate" the cursor into the past-the-end column.

lhecker · 2023-08-15T14:04:11Z

src/buffer/out/Row.cpp

        // _chars is a std::span for performance and because it refers to raw, shared memory.
 #pragma warning(suppress : 26481) // Don't use pointer arithmetic. Use span instead (bounds.1).
-        chars = { source._chars.data() + charsOffset, source._chars.size() - charsOffset };
+        chars = { source._chars.data() + beg, end - beg };


There's a h.charsConsumed == chars.size() check at the end of this function. That check only works if the chars.size() is correct, which this change now fixes. The string will now contain the exact amount of text we're allowed to copy.

lhecker · 2023-08-15T14:05:15Z

src/buffer/out/textBuffer.hpp

    void IncrementCircularBuffer(const TextAttribute& fillAttributes = {});

-    til::point GetLastNonSpaceCharacter(std::optional<const Microsoft::Console::Types::Viewport> viewOptional = std::nullopt) const;
+    til::point GetLastNonSpaceCharacter(const Microsoft::Console::Types::Viewport* viewOptional = nullptr) const;


While I like std::optional, we shouldn't optimally pass Viewport by value. Also, this pointer-style fits much better with Reflow() which has 2 optional parameters one of which is an explicit optional reference and why write

std::optional<std::reference_wrapper<PositionInformation>>

if you can also

PositionInformation*

lhecker · 2023-08-15T14:08:44Z

src/cascadia/TerminalCore/Terminal.cpp

-        // viewport, then update our _altBufferSize tracker we're using to help
-        // us out here.
        _altBufferSize = viewportSize;
+        _altBuffer->TriggerRedrawAll();


This was missing? I think that's a bug.

i'd believe it.

lhecker · 2023-08-15T14:09:18Z

src/cascadia/TerminalCore/Terminal.cpp

-        _altBuffer->GetCursor().StartDeferDrawing();
-        // we're capturing `this` here because when we exit, we want to EndDefer on the (newly created) active buffer.
-        auto endDefer = wil::scope_exit([this]() noexcept { _altBuffer->GetCursor().EndDeferDrawing(); });


There'll be no need for DeferDrawing anymore, since the reflow/resize functions don't use the cursor.

lhecker · 2023-08-15T14:14:01Z

src/cascadia/TerminalCore/Terminal.cpp

 {
-    return _inAltBuffer() ? ViewEndIndex() :
-                            std::max(0, ViewEndIndex() - _scrollOffset);
+    return _inAltBuffer() ? _altBufferSize.height - 1 : std::max(0, _mutableViewport.BottomInclusive() - _scrollOffset);


I'm not sure if I should revert these changes... I felt like the extra _inAltBuffer() check in the nested calls is redundant and inlining the code would make it clearer, but realistically this doesn't make any difference, right? Idk...

jeez, yeah, i don't get why these were the way they are. go for it.

lhecker · 2023-08-15T14:14:33Z

src/host/screenInfo.cpp

+    const auto lastNonSpaceRow = newTextBuffer->GetLastNonSpaceCharacter().y;
+    const auto estimatedBottom = cursorRow + cursorDistanceFromBottom;
+    const auto viewportBottom = _viewport.Height() - 1;
+    _virtualBottom = std::max({ lastNonSpaceRow, estimatedBottom, viewportBottom });


(Indentation changes only. -> Suppress whitespace changes.)

lhecker · 2023-08-15T14:14:57Z

src/buffer/out/textBuffer.cpp

+    const auto cursorRow = GetCursor().GetPosition().y;
+    const auto copyableRows = std::min<til::CoordType>(_height, newSize.height);
+    til::CoordType srcRow = 0;
+    til::CoordType dstRow = 0;


(Indentation changes only. -> Suppress whitespace changes.)

lhecker · 2023-08-15T14:15:26Z

src/buffer/out/textBuffer.cpp

-            newRow.SetLineRendition(row.GetLineRendition());
-        }
+    const auto oldCursorPos = oldCursor.GetPosition();
+    til::point newCursorPos;


This function may be easier to review without a diff.

src/cascadia/TerminalCore/Terminal.cpp

DHowett · 2023-08-24T22:37:17Z

src/cascadia/TerminalCore/Terminal.cpp

 {
-    return _inAltBuffer() ? ViewEndIndex() :
-                            std::max(0, ViewEndIndex() - _scrollOffset);
+    return _inAltBuffer() ? _altBufferSize.height - 1 : std::max(0, _mutableViewport.BottomInclusive() - _scrollOffset);


jeez, yeah, i don't get why these were the way they are. go for it.

src/host/screenInfo.cpp

src/buffer/out/textBuffer.cpp

DHowett · 2023-08-24T22:58:28Z

Unfortunately, I'm not confident that the new code replicates the old code exactly,

Well, it sure doesn't! All the reflow tests are failing :D

Some of them have been marked buggy, but I tried to capture as much existing behavior as i could when i wrote them.

lhecker · 2023-08-25T00:44:18Z

Well, it sure doesn't! All the reflow tests are failing :D

I thought that this means all is good:

I didn't consider that...

...they might just not work in VS.

…Buffer-reflow

lhecker · 2023-08-30T22:27:06Z

Found a bug: Entering the alt buffer, resizing the window and exiting the alt buffer deadlocks.

…Buffer-reflow

lhecker · 2023-09-05T13:29:05Z

src/host/screenInfo.cpp

-    if (gci.IsInVtIoMode())
-    {
-        gci.GetVtIo()->BeginResize();
-    }
-    auto endResize = wil::scope_exit([&] {
-        if (gci.IsInVtIoMode())
-        {
-            gci.GetVtIo()->EndResize();
-        }
-    });


While working on another PR I realized that this special behavior is only here for TextBuffer::Reflow, because that one used to use NewlineCursor which calls IncrementCircularBuffer which calls Renderer::TriggerFlush which calls VtEngine::InvalidateFlush which then set pForcePaint = false if BeginResize was called.

In short: This block prevents TextBuffer::Reflow from setting pForcePaint to true.

...and the new code doesn't call IncrementCircularBuffer anymore so that's moot.

zadjii-msft

(just trying to post a comment I think GH lost)

zadjii-msft · 2023-08-24T16:20:46Z

src/buffer/out/Row.cpp

+til::CoordType ROW::AdjustBackward(til::CoordType column) const noexcept
+{
+    return _adjustBackward(_clampedColumn(column));
+}
+
+til::CoordType ROW::AdjustForward(til::CoordType column) const noexcept
+{
+    return _adjustForward(_clampedColumnInclusive(column));
 }


These might warrant a comment as to why they're different than the Navigate* versions. If I'm reading this right:

the Navigate ones act like "move one cell forward/backward, then find the end/start of the glyph in that cell"

while the Adjust ones are just "find the end/start of the glyph in THIS cell"

correct?

Yep.

I've removed AdjustForward (it's unused) and renamed AdjustBackward to AdjustToGlyphStart and added a comment. That should hopefully make it easier to read the code.

zadjii-msft · 2023-08-24T16:22:05Z

src/buffer/out/Row.cpp


 til::CoordType ROW::MeasureRight() const noexcept
 {
+    if (_wrapForced)


zadjii-msft · 2023-09-18T20:05:53Z

src/buffer/out/textBuffer.cpp

+            if (oldY == oldCursorPos.y && oldCursorPos.x >= oldX)
            {
-                cNewCursorPos = newCursor.GetPosition();
-                fFoundCursorPos = true;
+                // In theory AdjustBackward ensures we don't put the cursor on a trailing wide glyph.
+                // In practice I don't think that this can possibly happen. Better safe than sorry.
+                newCursorPos = { newRow.AdjustBackward(oldCursorPos.x - oldX + newX), newY };
+                newYLimit = newY + newHeight;
            }


if the old cursor was on this row, and the old cursor was beyond this character,

the new cursor is on this row, adjusted for how many glyphs are in this new row

don't keep copying beyond this new row + the height of the new buffer

that feels weird? I don't think I understand the use of `newYLimit`` here

Just to be sure:

if the old cursor was on this row, and the old cursor was beyond ~~this character~~ the start of the text we've copied

...because this implies that we've probably just copied the text where the old cursor was on. I've written the if condition that way because it then matches the oldCursorPos.x - oldX. It allows you (kind of) to see how oldCursorPos.x >= oldX ensures that oldCursorPos.x - oldX doesn't go negative and how this results in the new cursor always being at some X position that is >= 0.

that feels weird? I don't think I understand the use of newYLimit here

Imagine that the terminal has no scrollback (= TextBuffer is as tall as the viewport). If we make the window significantly less taller (for instance 1/3rd), we need to ensure we don't continue copying so much text that it overwrites the row the cursor was on. In other words, newYLimit ensures that the row with the cursor remains visible.

I've added that as a comment to this line.

what if like,

the buffer starts 30 tall

the cursor is on line 5

we resize to 20 tall

Does that mean we'd only end up copying the first 25 rows? (newYLimit = 5 + 20)?

(this is the last question I have before I s/o)

Yes, exactly that. I did it for this test specifically:

terminal/src/buffer/out/ut_textbuffer/ReflowTests.cpp

Lines 294 to 315 in fc4a37e

TestBuffer{

{ 6, 5 },

{

{ L"ABCDEF", false },

{ L"$ ", false },

{ L"GHIJKL", false },

{ L"MNOPQR", false },

{ L"STUVWX", false },

},

{ 0, 1 } // cursor on $

},

TestBuffer{

{ 5, 5 }, // reduce width by 1

{

{ L"F$ ", false },

{ L"GHIJK", true }, // [BUG] We should see GHIJK\n L\n MNOPQ\n R\n

{ L"LMNOP", true }, // The wrapping here is irregular

{ L"QRSTU", true },

{ L"VWX ", false },

},

{ 1, 1 } // [BUG] cursor moves to 1,1 instead of sticking with the $

},

$ is the cursor. false in each line means that it has an explicit newline (true = force wrap).
It has a lot of comments about bugs in the old implementation, which is why the entire text past the cursor fits into the new buffer. In the new, fixed implementation the false = explicit newlines are correctly handled and so it doesn't fit anymore:

terminal/src/buffer/out/ut_textbuffer/ReflowTests.cpp

Lines 294 to 315 in 6374aec

TestBuffer{

{ 6, 5 },

{

{ L"ABCDEF", false },

{ L"$ ", false },

{ L"GHIJKL", false },

{ L"MNOPQR", false },

{ L"STUVWX", false },

},

{ 0, 1 }, // cursor on $

},

TestBuffer{

{ 5, 5 }, // reduce width by 1

{

{ L"$ ", false },

{ L"GHIJK", true },

{ L"L ", false },

{ L"MNOPQ", true },

{ L"R ", false },

},

{ 0, 0 },

},

Basically I had to make a choice over whether I:

continue copying until all text in the old buffer has been consumed.
If the new cursor position is now somewhere at a negative Y, we just put it at (0,0).

stop copying at some point to prevent the cursor from being lost.

I chose the latter. What do you think we should do?

continue copying until all text in the old buffer has been consumed.
If the new cursor position is now somewhere at a negative Y, we just put it at (0,0).

Probably that one, right? Like, the priority should be to keep the newest text, right?

(/cc @DHowett since this is currently a 1.19 candidate. I'm okay to say merge as is and iterate in the first hotfix since

we're out of time and I'm about to log out for the day

this is a RARE edge case

this is more goodness than badness)

This is an interesting case. I'm honestly not sure how to handle it -- we should look at how other terminals that do reflow handle it?

zadjii-msft · 2023-09-19T12:01:06Z

I think I'm inclined to s/o on this, though I really don't think I get the newYLimit thing.

Though, there are a TON of reflow roundtrip tests, so if those still pass, then I'm inclined to say this works.

…Buffer-reflow

DHowett · 2023-09-26T00:28:34Z

I'm okay to say merge as is and iterate in the first hotfix since

I am taking this as a sign-off for 1.19, plus fixes.

Mike, thanks for reviewing. Sorry if I override you and am incorrect. 😄

Subjectively speaking, this commit makes 3 improvements: * Most importantly, it now would work with arbitrary Unicode text. (No more `IsGlyphFullWidth` or DBCS handling during reflow.) * Due to the simpler implementation it hopefully makes review of future changes and maintenance simpler. (~3x less LOC.) * It improves perf. by 1-2 orders of magnitude. (At 120x9001 with a full buffer I get 60ms -> 2ms.) Unfortunately, I'm not confident that the new code replicates the old code exactly, because I failed to understand it. During development I simply tried to match its behavior with what I think reflow should do. Closes #797 Closes #3088 Closes #4968 Closes #6546 Closes #6901 Closes #15964 Closes MSFT:19446208 Related to #5800 and #8000 ## Validation Steps Performed * Unit tests ✅ * Feature tests ✅ * Reflow with a scrollback ✅ * Reflowing the cursor cell causes a forced line-wrap ✅ (Even at the end of the buffer. ✅) * `color 8f` and reflowing retains the background color ✅ * Enter alt buffer, Resize window, Exit alt buffer ✅ (cherry picked from commit 7474839) Service-Card-Id: 90642727 Service-Version: 1.19

#15541 changed `AdaptDispatch::_FillRect` which caused it to not affect the `ROW::_wrapForced` flag anymore. This change in behavior was not noticeable as `TextBuffer::GetLastNonSpaceCharacter` had a bug where rows of only whitespace text would always be treated as empty. This would then affect `AdaptDispatch::_EraseAll` to accidentally correctly guess the last row with text despite the `_FillRect` change. #15701 then fixed `GetLastNonSpaceCharacter` indirectly by fixing `ROW::MeasureRight` which now made the previous change apparent. `_EraseAll` would now guess the last row of text incorrectly, because it would find the rows that `_FillRect` cleared but still had `_wrapForced` set to `true`. This PR fixes the issue by replacing the `_FillRect` usage to clear rows with direct calls to `ROW::Reset()`. In the future this could be extended by also `MEM_DECOMMIT`ing the now unused underlying memory. Closes #16603 ## Validation Steps Performed * Enter WSL and resize the window to <40 columns * Execute ```sh cd /bin ls -la printf "\e[3J" ls -la printf "\e[3J" printf "\e[2J" ``` * Only one viewport-height-many lines of whitespace exist between the current prompt line and the previous scrollback contents ✅

#15541 changed `AdaptDispatch::_FillRect` which caused it to not affect the `ROW::_wrapForced` flag anymore. This change in behavior was not noticeable as `TextBuffer::GetLastNonSpaceCharacter` had a bug where rows of only whitespace text would always be treated as empty. This would then affect `AdaptDispatch::_EraseAll` to accidentally correctly guess the last row with text despite the `_FillRect` change. #15701 then fixed `GetLastNonSpaceCharacter` indirectly by fixing `ROW::MeasureRight` which now made the previous change apparent. `_EraseAll` would now guess the last row of text incorrectly, because it would find the rows that `_FillRect` cleared but still had `_wrapForced` set to `true`. This PR fixes the issue by replacing the `_FillRect` usage to clear rows with direct calls to `ROW::Reset()`. In the future this could be extended by also `MEM_DECOMMIT`ing the now unused underlying memory. Closes #16603 ## Validation Steps Performed * Enter WSL and resize the window to <40 columns * Execute ```sh cd /bin ls -la printf "\e[3J" ls -la printf "\e[3J" printf "\e[2J" ``` * Only one viewport-height-many lines of whitespace exist between the current prompt line and the previous scrollback contents ✅ (cherry picked from commit 5f71cf3) Service-Card-Id: 91707937 Service-Version: 1.19

STL iterators have a significant overhead. This improves performance of `GetLastNonSpaceColumn` by >100x (it's too large to measure), and reflow by ~15x in debug builds. This makes text reflow in debug builds today ~10x faster than it used to be in release builds before the large rewrites in #15701 and #13626.

lhecker mentioned this pull request Jul 12, 2023

Wrap double-height text properly #15681

Open

lhecker marked this pull request as draft July 14, 2023 17:02

lhecker force-pushed the dev/lhecker/8000-TextBuffer-reflow branch 2 times, most recently from 26548fb to a009e0d Compare August 15, 2023 12:57

This was referenced Aug 15, 2023

Cursor position is lost when resizing the window horizontally #10868

Closed

Cursor position is lost when resizing the window if not on the bottom line #10848

Closed

Reimplement TextBuffer::Reflow

3d463f1

lhecker force-pushed the dev/lhecker/8000-TextBuffer-reflow branch from a009e0d to 3d463f1 Compare August 15, 2023 14:00

lhecker marked this pull request as ready for review August 15, 2023 14:00

lhecker commented Aug 15, 2023

View reviewed changes

Fix AuditMode failures

f725a6a

zadjii-msft added the zBugBash-Consider label Aug 15, 2023

lhecker mentioned this pull request Aug 24, 2023

Rewrite COOKED_READ_DATA #15783

Merged

DHowett reviewed Aug 24, 2023

View reviewed changes

src/cascadia/TerminalCore/Terminal.cpp Outdated Show resolved Hide resolved

DHowett approved these changes Aug 24, 2023

View reviewed changes

lhecker added 4 commits August 25, 2023 14:08

Address feedback

0230743

Merge remote-tracking branch 'origin/main' into dev/lhecker/8000-Text…

73833f8

…Buffer-reflow

Fix 2 cursor related bugs and all TestReflowCases

6374aec

Cleaned up some small leftovers

349082a

lhecker added 2 commits September 5, 2023 15:16

Reflow doesn't call IncrementCircularBuffer anymore

a72e2cb

Merge remote-tracking branch 'origin/main' into dev/lhecker/8000-Text…

4139230

…Buffer-reflow

lhecker commented Sep 5, 2023

View reviewed changes

Fix OOB cursor coordinates when exiting alt buffer

1546a99

lhecker mentioned this pull request Sep 13, 2023

Resizing window lags when history buffer has lots of lines #15964

Closed

zadjii-msft reviewed Sep 18, 2023

View reviewed changes

lhecker added 2 commits September 19, 2023 16:29

Merge remote-tracking branch 'origin/main' into dev/lhecker/8000-Text…

f7f7099

…Buffer-reflow

Address feedback

80e453d

This comment has been minimized.

Sign in to view

lhecker added 3 commits September 19, 2023 16:52

Spel

a8ef491

Merge remote-tracking branch 'origin/main' into dev/lhecker/8000-Text…

5ad619d

…Buffer-reflow

Improve newYLimit comment

fd4e89b

DHowett added a commit that referenced this pull request Sep 22, 2023

PRE-MERGE #15701 Reimplement TextBuffer::Reflow

c7c56bb

Merge remote-tracking branch 'origin/main' into dev/lhecker/8000-Text…

971cd79

…Buffer-reflow

DHowett approved these changes Sep 25, 2023

View reviewed changes

DHowett merged commit 7474839 into main Sep 26, 2023

DHowett deleted the dev/lhecker/8000-TextBuffer-reflow branch September 26, 2023 00:28

This was referenced Sep 26, 2023

Double check how we reflow for a huge height delta #16033

Open

[1.19] Shell integration marks are totally in the wrong place #16034

Closed

j4james mentioned this pull request Jan 25, 2024

ED2 inserts loads of blank lines in scrollback #16603

Closed

lhecker mentioned this pull request Jan 27, 2024

Reset _wrapForced when erasing scrollback #16610

Merged

lhecker mentioned this pull request Mar 24, 2024

Implement grapheme clusters #16916

Merged

lhecker mentioned this pull request Jul 11, 2024

15x faster reflow in debug builds #17550

Merged

	TestBuffer{
	{ 6, 5 },
	{
	{ L"ABCDEF", false },
	{ L"$ ", false },
	{ L"GHIJKL", false },
	{ L"MNOPQR", false },
	{ L"STUVWX", false },
	},
	{ 0, 1 } // cursor on $
	},
	TestBuffer{
	{ 5, 5 }, // reduce width by 1
	{
	{ L"F$ ", false },
	{ L"GHIJK", true }, // [BUG] We should see GHIJK\n L\n MNOPQ\n R\n
	{ L"LMNOP", true }, // The wrapping here is irregular
	{ L"QRSTU", true },
	{ L"VWX ", false },
	},
	{ 1, 1 } // [BUG] cursor moves to 1,1 instead of sticking with the $
	},

Conversation

lhecker commented Jul 12, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Validation Steps Performed

Uh oh!

lhecker commented Aug 15, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

DHowett commented Aug 24, 2023

Uh oh!

lhecker commented Aug 25, 2023

Uh oh!

lhecker commented Aug 30, 2023

Uh oh!

Choose a reason for hiding this comment

Uh oh!

zadjii-msft left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

zadjii-msft commented Sep 19, 2023

Uh oh!

This comment has been minimized.

DHowett commented Sep 26, 2023

Uh oh!

Reviewers

Assignees

Labels

lhecker commented Jul 12, 2023 •

edited

Loading

lhecker commented Aug 15, 2023 •

edited

Loading