Add support for VT paging operations

[j4james]

Summary of the Pull Request

This PR adds support for multiples pages in the VT architecture, along with new operations for moving between those pages: NP (Next Page), PP (Preceding Page), PPA (Page Position Absolute), PPR (Page Position Relative), and PPB (Page Position Back).

There's also a new mode, DECPCCM (Page Cursor Coupling Mode), which determines whether or not the active page is also the visible page, and a new query sequence, DECRQDE (Request Displayed Extent), which can be used to query the visible page.

References and Relevant Issues

When combined with DECCRA (Copy Rectangular Area), which can copy between pages, you can layer content on top of existing output, and still restore the original data afterwards. So this could serve as an alternative solution to #10810.

Detailed Description of the Pull Request / Additional comments

On the original DEC terminals that supported paging, you couldn't have both paging and scrollback at the same time - only the one or the other. But modern terminals typically allow both, so we support that too.

The way it works, the currently visible page will be attached to the scrollback, and any content that scrolls off the top will thus be saved. But the background pages will not have scrollback, so their content is lost if it scrolls off the top.

And when the screen is resized, only the visible page will be reflowed. Background pages are not affected by a resize until they become active. At that point they just receive the traditional style of resize, where the content is clipped or padded to match the new dimensions.

I'm not sure this is the best way to handle resizing, but we can always consider other approaches once people have had a chance to try it out.

Validation Steps Performed

I've added some unit tests covering the new operations, and also done a lot of manual testing.

PR Checklist

• [x] Closes #13892
• [x] Tests added/passed

[j4james]

I think this is ready for review now. I've been using it for a while, and it works nicely for my use cases, although I'm not sure how much benefit it will be for anyone else.

And I should warn you that it might have some impact on performance, but I'm hoping it isn't significant. I did a test run with the new benchmark tool, and the only tests that looked a lot worse were the 4Ki WriteConsole ones, but the times are in microseconds, so I'm not sure they're really as bad as they look.

[lhecker]

FWIW I'm still somewhat worried about putting the PageManager into the VT specific code. However, I don't think I could suggest an alternative. As we've talked about many times before, I would personally greatly prefer if there would not be 2 terminal API implementations, but rather just a single Terminal class. If such a single Terminal class existed, I think the pages should be stored there. I believe that this may long term simplify certain operations that we can't foresee yet.

[DHowett]

Yesterday I asked Leonard to explain this to me so I'd be able to review it for 1.21. I'm sorry we let you marinate for 3 months! I'm on this today, for release next week or so.

Thanks so much, James, for everything.

[j4james]

@DHowett Honestly I don't mind if you want to leave this for a while. I was hoping there might be a way to improve the performance based on Leonard's suggestion about page caching, but I've been putting off working on that because I was having too much fun actually using the new functionality (e.g. see VT-Rex).

That said, I also wouldn't mind if you chose to merge it as is, but I'm somewhat concerned this might be a feature that nobody else uses besides me, and so for everyone else it would just be an unwanted performance regression.

[lhecker]

I don't think you need to worry about the performance too much - The regression is rather small. I forgot how much it was, but it was like -5% or something. The recent cursor caching PR (if you've seen it) alone brought us +20%, and there's a hundred more places like that.

IMO the best thing we can do for perf. is to instead shrink our architecture. If we have less interfaces, less adapters, less classes, and so on, and more data driven design overall, we'll probably straight up double our VT performance without even touching the underlying algorithms. In ConPTY for instance, if we ignore VtEngine, the actual text and attribute insertion including width measurement only consumes around 20% of CPU time in the worst case.

---

BTW if anyone (or you) wants to work on perf., here's something that would probably net us another >10% uplift, with the potential to improve performance much more in the long run (= it's an unblocker for other optimizations): DelayEOLWrap() is currently a boolean flag and it and GetDelayedAtPosition() are somewhat costly. We could implement it this way for instance:

void Cursor::DelayEOLWrap() noexcept
{
    return _cPosition.x >= _parentBuffer._width;
}

That is, we represent a delayed cursor by putting it into a column past the right end of the buffer. We would need to modify GetPosition to be something like

til::point Cursor::GetPosition() const noexcept
{
    const auto width = _parentBuffer._width;
    return { std::min(_cPosition.x, width - 1), _cPosition.y };
}

One major VT perf. cost is that our parser simply isn't a traditional one: It should ideally be implemented as a state machine with lookup table. Something like Alacritty's parser: https://github.com/alacritty/vte/blob/master/src/table.rs This is because a major cost resides in StateMachine::_ActionParam and friends, as all those branches (including those abstracted away in the STL, etc.) are fairly costly overall (around 1/3rd of our total CPU cost).

AdaptDispatch::_DoLineFeed is also rather slow. I'm not entirely yet why, but maybe it could be "math'ified" a bit more?

---

P.S.: Another very difficult, but very impactful change would be calling AccessibilityNotifier functions only after StateMachine::ProcessString returns in DoWriteConsole. This would net us +100% perf in conhost (and later in WT if we ever get a conhost.lib). It can be done by accumulating a single til::point_span that covers the entire damaged region, and a total cumulative scroll offset. It's fine if the span covers too much area (for instance because of CUP sequences jumping around and changing things in multiple places), because such apps aren't even accessible now either.

However, I think the other changes above are more important right now as they simplify our architecture.

[j4james]

DelayEOLWrap() is currently a boolean flag and it and GetDelayedAtPosition() are somewhat costly.

Just on this point, I don't think the boolean flag is avoidable, because delayed wrapping is not actually limited to the final column of the display. With margins applied, you can have a delayed wrap occurring almost anywhere. And technically I think you can probably set the flag manually with DECCIR, without even being on the margin.

[j4james]

FYI, I've had a chance to experiment with the page caching, but I couldn't get it to make much of a difference in terms of performance. So what's here now is as good as it's going to get from me (at least in the short term). If you all are happy with it as it is, it would be nice to have it merged, but I don't mind if you decide against it.

[lhecker]

Ah that's fine then. We're about to fork off release-1.21 now and I think afterwards we can merge it (for version 1.22). I can't speak for them, but it may still take a little bit, because Dustin & Mike are quite busy right now with the release of not just this, but sudo, bug fixes, etc.

[DHowett]

Alright! Let's get this merge conflict unconflicted and we can land this thing. Thank you for your patience.

James, generally speaking even if you're the only person who would benefit from a particular aspect of VT compatibility I'd still love for us to have it. 🙂

[j4james]

@DHowett In case you haven't seen, the merge conflicts have been resolved now.

[alabuzhev]

this could serve as an alternative solution to #10810

Thanks, it looks promising. I couldn't make it work in the latest OpenConsole though, is it entirely unsupported there?

[j4james]

@alabuzhev If you're using the nightly/canary build it should be supported.

[alabuzhev]

@j4james my bad, I was using an outdated one. Thanks.