*** Bug 318066 has been marked as a duplicate of this bug. ***

When we fixed this in vte, an option in g-t is appropriate.

Implementing it in vte is a bit hard, but possible.  My only concern is performance with very long scroll history that should be rewrapped.

Yeah, I suspected it wouldn't be easy.  I'll buy a beer at GUADEC for whoever implements this. :)

*** Bug 68490 has been marked as a duplicate of this bug. ***

*** Bug 498856 has been marked as a duplicate of this bug. ***

*** Bug 560919 has been marked as a duplicate of this bug. ***

*** Bug 590134 has been marked as a duplicate of this bug. ***

I confirm this is really annoying. Could someone please have a look at it?

Any progress on that one?

Not much, but we're one step closer...

This is the coolest feature of Mac Terminal, and ever since I saw it there, I can hardly live without it. I soooo much wish vte had this feature too :)

Note that this is not only supported by the default Terminal.app, but also the third-party opensource iTerm (iterm.sf.net) has this feature. That one could be used as an aid how to implement this. (E.g. it's not clear to me whether it's better to store physical lines in memory (and wrap for displaying only) or to store visual lines (and re-wrap the whole memory structure).)

Some advantages that this feature would bring:

- When you widen the terminal, the extra space immediately gets used so you see more vertical history.

- When you narrow the terminal, you don't hide some data that might be important.

- In either cases, you could still use double/triple click to highlight whatever was output by the application (e.g. a long URL) - currently you cannot select it after a horizontal resize.

- You get out of the nasty habit of re-executing the same command after a resize just to see its output wrapped as desired or to be able to copy-paste from it.

Behdad, a couple of years ago you said your concern was re-wrapping a long scrollback history. Now I'm just wondering: probably the history wouldn't need to be re-wrapped immediately, we could do it lazily only when the user actually scrolls back in the buffer. I don't know anything about the current internal data structures of vte, but I guess for every line we could store the current (not-yet-rewrapped) width, plus a boolean whether that line overflowed, and by comparing these to the current window size we could re-wrap the lines on demand.

(However, in order to show the scrollbar correctly, we would still need to calculate the number of visual lines above/below the desired viewpoint, but that's pretty simple, we'd just need to loop over all the per-line "width" and "overflow" fields and do some simple math, we wouldn't have to move data around in the memory.)

I'd say: let's go for the "re-wrap everything at once" approach first, but if that turns out to be slow, we don't need to worry because we see a way to make it faster.

Another, completely independent note: special tricks will be required for the re-wrapping of double-wide CJK characters, let's not forget about that.

Thanks Egmont.

Actually implementing that feature is not that hard with the new vte buffer.  We store the actual text data in a continuous stream now.  Just need to keep the row-data in a new structure that would allow fast traversal given a terminal width.  I think I have ideas about that.

(In reply to comment #11)
> This is the coolest feature of Mac Terminal, and ever since I saw it there, I
> can hardly live without it.

Just want to echo Egmont's comment that this is THE killer feature of Terminal.app.  Adding the capability to g-t would be awesome.

Any news about this one?

Created attachment 254134 [details] [review]
First demo

First demo. Cuts down a few lines at the bottom, sometimes crashes, but otherwise it's promising :)

Created attachment 254135 [details] [review]
Second demo

A tiny little bit better than the previous one.

The biggest culprit is still vertical positioning of stuff: the bottommost actual used line, the viewport, the scrollbar, the cursor... Even figuring out the desired behavior is nontrivial, let alone implementing it :)

Crashes are also caused by failed assertions about vertical positioning.

Created attachment 254140 [details] [review]
Third demo

Again a bit better. The main problem remains.

Created attachment 254141 [details] [review]
Fourth version - the first that works quite well!

I figured out the basics of the vertical alignment, so here's the first version of the patch that actually works quite well! :)  Please give it a try!

Some notes:

CJK and combining accents should work correctly.

Tabs near a soft wrap are handled in a quite bizarre way anyways, and they don't re-wrap exactly to as if they were printed at the new width.

If the character printed at soft wrap has a background color, the whole next line will have that background. This does not re-wrap exactly how this would look if this was printed at the new width.

If you make your terminal narrower than your actual bash prompt, the prompt will look weird. This is the same in other terminals supporting rewrap (urxvt, iterm2) because it's bash that keeps redisplaying the prompt. It's not a bug in vte rewrap code and there's nothing we could do about it.

Sometimes after a resize followed by a keypress there's a sudden jump. This means there's still some work to be done with vertical positioning.

If the viewport is scrolled back when you resize the window, it would be nice to try to keep approximately the same lines displayed.

Speed is okay for me at a 10.000 line scrollback buffer, but gets quite slow at 100.000 lines. Probably it's a really bad idea to combine this feature with infinite scrollback buffer. An idea for speed improvement: if a row enclosed within hard linebreaks is narrower than both the old and new widths, we can keep and reuse its whole VteRowData rather than creating a new one and copying each character separately.

I might leak memory, I haven't paid attention yet.

Please test it, any comments are welcome! :)

Created attachment 254188 [details] [review]
Version 5

Even better version. Fixes: If scrolled back, keeps the visible content on screen as much as possible (aligns scroll position to the middle visible line). Actual visual position of the scrollbar also fixed.

Still has glitches with resizing the normal screen in presence of an alternate screen. (Probably the vertical position is the culprit again.)

I spent quite some time exploiting the speedup idea I mentioned, but this would require way too heavy refactoring (as most of the data is not stored in VteRowData), so I gave up on this.

Behdad, could you please help me clarify the meaning of 'insert_delta'?  I'm really not sure what this variable holds.  My best guess so far is that it's what 'scroll_delta' would be if the viewport was scrolled all the way to the bottom - but I'm not sure.

(In reply to comment #21)
> Behdad, could you please help me clarify the meaning of 'insert_delta'?  I'm
> really not sure what this variable holds.  My best guess so far is that it's
> what 'scroll_delta' would be if the viewport was scrolled all the way to the
> bottom - but I'm not sure.

It's where "cursor" is.  Ie. where new data arriving from the pty will end up.

Are you really sure?  I think that's what cursor_current.row is for.  insert_delta seems to be the same as scroll_delta most of the time, no matter where the cursor is.  My best guess is still what I guessed previously, althogh clearly this doesn't match the name of the variable.  I'm wondering if this variable has some clear semantics at all...  Maybe someone changed it at some point?

I'm not sure at all.  It's been years since I last looked at that code.

I think you are right.  It's the delta when scroll follows insert.

Thanks. Not an intuitive name but now it makes sense :)

Created attachment 254592 [details] [review]
Version 6

Getting way better.

Rewraps the normal screen if alternate screen is present. (The cursor's location is sometimes broken when switching back, I'm yet to figure it out.)

Tons of code cleanup, comments, debug stuff etc.

Decoupled re-wrapping the ring from figuring out the insert/scroll positions, so that the first one can be re-written one day in ring.c without touching the rest.

I believe the current scrollbar positioning is totally fine.

The behavior (how the scrollbar is positioned etc.) is now exactly the same, regardless whether the width changed or the height only (re-wrapping was necessary or not).

This required a small behavior change which was strange anyway. If the scrollbar was somewhere middle-ish and you changed the height back and forth, the terminal would swallow lines from the top but add new ones at the bottom, causing the scroll position to slowly drift. The new policy, which IMO makes much more sense, especially with re-wrapping, is to align to the bottom as much as possible, and add/remove lines at the top.

Also I no longer do the hassle of adjusting the insert/scroll positions on the alternate screen if that's the visible one, I'm not sure if this causes any trouble, hopefully it doesn't since alternate screen doesn't have scrolling at all.

I believe there are still problems with multiple consecutive resize events in a very short time, but this seems to be a generic vte problem.

Please go ahead and test with your favorite applications :)

Thanks!  Few comments:

1. Please avoid gcc'ism (named struct initializers?),

2. Can the ring code go into the ring.c?

In general, it's great that you did this, because it takes care of the tricky bits.  My original plan was this: to change the ring into a datastructure that can be queried at any given width without having to change at all.  That's for example, why the UTF-8 text and attributes streams are written in a straight line, such that can reuse them for differing widths without modification.

That said, with your patch going in, I can then focus on implementing such a ring without worrying about the widget side of things.

Thanks!  If you clean this up a bit further and express that you are confident in it to go in, I'll make that happen.

Sure, coding style and such will be the last step once everything works perfectly. I'd say there'll be probably 2-3 more versions before I declare it ready :)

Is it okay to do a sudden switch to this behavior? Or should we have a runtime flag that enables/disables this on the run, and then expose in g-t's settings? Partially because some people might prefer the old behavior, partially because some might find the new behavior too slow (especially with large scrollbacks), and partially because the new behavior is not well tested yet, maybe it even crashes on some really tricky cases...

Lets see how stable we can make it then before deciding.

About moving the ring code to ring.c: The rewrap function uses VteVisualPosition defined in vte-private.h, so I'd need to include it from there, causing a dependency loop rather than a clean hierarchy. What would be your preferred solution? We can probably live with this loop and some pre-declarations (but it's ugly), or move the declaration of VteVisualPosition somewhere else (but where?), or use a different kind of data structure for this function?

One way or another, whatever works.  Moving VteVisualPosition into the ring header perhaps.

Created attachment 254618 [details] [review]
Version 7

Fixes:
- Handling cursor_saved fixed, now the cursor is positioned correctly when returning from alternate screen.
- Scrolling changed a tiny little bit: bottom row also fully stays, even when becomes wrapped.
- Code changes as requested, now warning-free and hopefully gcc'ism-free.

TODOs:
- There's a new assertion but I'm not 100% confident about it, maybe there's a sequence of events that cause cursor_saved to go out of the ring's area. Perhaps we should be more defensive there.
- Low hanging speedup idea: Shouldn't immediately resize the normal screen if the alternate screen is visible, only resize when switching back to normal screen.
- Stresstest, check for memleak etc...

Created attachment 254620 [details] [review]
Version 7b

With this rewrap stuff, I can no longer trigger bug #707572 so I restored that assertion. Apart from that, cosmetic changes only (code formatting and such).

Now I disappear for at least 2 days :)

Created attachment 254785 [details] [review]
Experiment: don't rewrap normal screen when alternate is present

This is an experiment to be applied on top of version 7b.

When the alternate screen is present, don't rewrap the normal screen on each resize, only rewrap it once when returning to normal screen.

I'm really not sure if this is a good thing. Let's consider a really large scrollback buffer (e.g. 100'000 lines filled up) where rewrapping takes almost 1 second on my average laptop. Run an alternate screen application, such as mc.

Without this optimization, resizing mc takes almost a second each time, which is a lot of time, but it happens when the user requests such action anyways, and typically reaches out to the mouse. This 1 second is not such a large time compared to the time it takes to perform such actions by the users, and it's not much of a surprise that resizing a window takes some time.

On contrary, with this optimization, you can resize mc instantaniously, but the surprise comes when you try to quit it. Press F10 followed by Enter, and nothing happens for 1 second, making you wonder whether you really hit Enter, or why mc is so slow quitting. This time-consuming operation happens when you'd not expect it and when you'd rather immediately start typing to the shell, leaving you with a wtf feeling not having a clue what is happening. I found this a pretty annoying experience.

So, it was a nice experiment, but I'm going to continue without it.

I think we should work on making the resize much faster.  I'll try to give it a look over the weekend.  In the mean time, are you working against master?

I agree that a significant speedup would be nice, thanks in advance for working on it! I'm also going to take a look at the ring code, but it looked quite complicated to me at first glimpse, I have to understand the whole concept first... or just throw it away and reimplement :)

I'm working against latest tarball (0.34.7) which is pretty much the same as master. The patch also applies and works in master.

The ring code is quite simple when you understand it.  I wouldn't suggest reimplementing it just yet.  I spent a lot of time to come up with the current stream design.  It needs more work, but I think the design is good for now.

Basically, this is how the ring code works: for the last few lines (ie. ring->writeable and later) it keeps a straight VteRowData.  For anything before that (ie. scrollback history), it keeps a compact form in three streams: utf-8 text, run-length encoded cell attributes, and row records.  A row record simply points to the start of the row in the text and attributes streams.  I designed this specifically having in mind the need to rewrap lines at some point.

Now, all rewrapping is, is to change the row records.  The attributes and utf8 streams are left intact.  That should be, like, 100 times faster than what you are doing now since we don't have to thaw/freeze lines.  thaw/freeze are operations that convert the compact history rows into VteRowData which is what the rest of the codebase uses.

I understand :)  It really should be quite easy and super fast on the frozen rows.

In order to avoid two different rewrapping logics (with looking for the "markers" (cursor and scroll positions) it's not that simple), I guess the simplest is to freeze all the rows, rewrap, and then thaw the bottom ones - what do you think?

That should work.

It's gonna take some time for me, but I can already see the end of the tunnel.

For a long time I thought we could totally avoid reading the text stream (which is probably the performance bottleneck), that'd be a real killer. Unfortunately that's not always the case:

- In order to tell if a line break (as pointed by a VteRowRecord) is soft or hard, we need to check for a '\n' in text_stream. Probably it'd be worth it to store this bit in VteRowRecord.

- If a previous row no longer fits, you can easily compute how many characters will fit, but converting back to bytes requires calling g_utf8_offset_to_pointer() to find the byte offset of the soft break. As an optimization, this can be avoided if the cells are single wide and their number equals to the byte length of the string (i.e. plain ASCII stuff only). Or if text_stream contained UCS4 instead of UTF8, but that'd be a tradeoff for memory usage.

My thought process has been to design a data-structure that can tell how many lines a piece of text would take given any width.  If we have that, then we don't have to actually rewrite anything...

To get such a thing, imagine if we have a binary tree of sorts, and each node represents a range of text in the buffer, and the node knows how many lines of each possible width we have...  I'll think about it more, it's far from designed...

A huge problem here is TAB and CJK characters, they cause the number of lines to heavily depend not only on the width, but also on the starting column, which you need to consider if you don't split the text at newlines. Splitting only at hard newlines causes problems with very long lines. And splitting at all visual newlines is what vte does currently :)

In order to properly display the scrollbar, you'd need to compute the number of visual lines anyway, so you'd have to iterate through all these buffers and do some math. Recomputing the row_stream and sometimes taking a look at text_stream doesn't sound much worse to me. Also there's the problem that you have to tell where the cursor or the scroll_delta moved, this might be a bit tricky too.

Anyway, I'm also going to think about clever data structures, probably you have much better ideas, but at this point I'm not convinced that anything other than recomputing row_stream could result in a substantially faster and easier to write/maintain solution.

You definitely have good points.  I hadn't thought about tabs.  Not sure what the proper behavior is.  Perhaps we can test with OS X?

Re CJK, my thinking last time was that we shouldn't let that affect line breaks.  Ie, if we break in the middle of a double-width CJK char, that's fine, we render half of it on one line and the other half on the next line.  That needs special handling though, but makes the decision-making easier.

Created attachment 254844 [details]
Screenshot of splitting in half

We should ask people who can read CJK, but I'm pretty sure the answer will be a definitely no-go. Just take a look at the example screen shot and realize how hard it is to read that, e.g. compose the W from the two V's, or the r from the vertical and the horizontal line; let alone cyan and red colors from splitting a subpixel rendered stuff. And think how many CJK symbols are there, how hard might be to distinguish one from other, or how often it might matter which horizontal line is short (happens to end at the middle of cell) and which one continues and how your eyes would be unable to glue them together and tell which one continued... All terminals supporting CJK know to wrap the whole character to the next line, VTE does that too, and so does my rewrapping patch. Let's not give up this feature for a cooler algorithm.

Continuing comment 40: If we add the hard/soft wrap flag to VteRowFlag, then that stream along with attr_stream is enough to rewrap the text and compute text_offset for hard line wraps, while for soft line wraps you'd need to have text_offset on a special value (e.g. -1) meaning that you haven't computed it. This so far doesn't involve reading text_stream at all, and you'd still get the number of rows correct with correct CJK wrapping. It's only the text_offset for soft wraps that you will compute lazily on demand.

(In reply to comment #45)
> Continuing comment 40: If we add the hard/soft wrap flag to VteRowFlag, then
> that stream along with attr_stream is enough to rewrap the text and compute
> text_offset for hard line wraps, while for soft line wraps you'd need to have
> text_offset on a special value (e.g. -1) meaning that you haven't computed it.
> This so far doesn't involve reading text_stream at all, and you'd still get the
> number of rows correct with correct CJK wrapping. It's only the text_offset for
> soft wraps that you will compute lazily on demand.

That's great!

Version 7b has already crashed for me on
  g_assert(normal_screen->cursor_current.row != -1);
Probably related to the other issues with multiple resizes in a short time, dunno.

I put my thoughts in this document:
https://docs.google.com/document/d/1ZsVWBPUuM7V5FSbkESxowk5UBr1HsoWgW4e0HrF73Pk/edit#

In case of maximum performance. 
is it possible to make new behavior optionally?

So users can revert to the current vte behavior, if needed?

At its current state it's very easy: it's just one method call that needs to be made conditional. I can't yet see where the patch will evolve but I'd like to keep this way. Plus all the boring chrome around it needs to be created (interface, docs, g-t config option etc).

Whether we actually want to make it probably depends on how fast the patch will be and how confident we'll be about its functionality and stability. See comments 28-29.

I think the problem is that once you create this option it becomes cumbersome to deprecate/remove it, and having two possible behaviors makes maintainance harder in the long run.

(In reply to comment #48)
> I put my thoughts in this document:
> https://docs.google.com/document/d/1ZsVWBPUuM7V5FSbkESxowk5UBr1HsoWgW4e0HrF73Pk/edit#

I've made some comments there, also started to gather my random unorganized thoughts here:
https://docs.google.com/document/d/1Mil1CLZqLwEX9mA5-YqhacnjwJZ98s3IIVqaeLElcpk/edit?usp=sharing

I really doubt the magical data structure that you're looking for really exists. As for whether to store paragraphs rather than lines: the basic functionality of terminals is around lines, storing paragraphs would make life much harder all around vte (including taking care of extremely long paragraphs everywhere). If we keep storing lines, it's rewrapping only that is a bit cumbersome. Rewrapping is nice to have, but not the core functionality that we should build the terminal around.

So I'd personally vote for basically keeping vte as it is, let's just add this one feature that actually rewraps the whole scrollback buffer. Or, at least do it this way now (and make it into Gnome 3.12), and who knows, maybe completely redo it one day.

Created attachment 255891 [details] [review]
Version 11

Arbitrarily skipping some version numbers to denote a big change :)

It uses ring's internals, and recreates row_stream only rather than the whole ring. This makes it much faster - unfortunately much more compicated too.

The patch applies on top of vte-0.34.8 plus the patches from bug 708496 (two patches) and bug 708213 ("egmont's third patch"). However, it doesn't yet contain the functionality of the latter patch (the zsh prompt fix).

The patch is a draft, it obviously needs to be heavily cleaned up. But it works perfectly (or at least I hope so), and can probably help us decide if we want to continue this approach.

By far the biggest bottleneck of performance were the many small read()/write() calls. These should be cached so that we talk to the kernel much less often. The patch has dirty hacks for this, but proper caching in vtestream-file would be something VTE would benefit from, even without rewrapping. Maybe we should move this to a dependent bugreport.

Performance for me (average laptop, /tmp on hdd): rewrapping 1M lines of colored "ls -l" output (mostly ASCII) is around 0.2s wall clock time. I haven't measured heavily non-ASCII text yet, but there are a couple of further things we could do to speed them up. (The code has optimized branches for ASCII-only paragraphs).

(In reply to comment #45)
> Continuing comment 40: If we add the hard/soft wrap flag to VteRowFlag, then
> that stream along with attr_stream is enough to rewrap the text and compute
> text_offset for hard line wraps [...]

Unfortunately this is not true, I incorrectly thought attr_stream contained the number of characters for each run, but it contains the number of bytes. So my recent patch (v11) needs to read text_stream for every non-ascii paragraph. One possible idea to investigate could be if we can maintain this info in attr_stream.

(In reply to comment #51)
> (In reply to comment #48)
> > I put my thoughts in this document:
> > https://docs.google.com/document/d/1ZsVWBPUuM7V5FSbkESxowk5UBr1HsoWgW4e0HrF73Pk/edit#
> 
> I've made some comments there, also started to gather my random unorganized
> thoughts here:
> https://docs.google.com/document/d/1Mil1CLZqLwEX9mA5-YqhacnjwJZ98s3IIVqaeLElcpk/edit?usp=sharing
> 
> I really doubt the magical data structure that you're looking for really
> exists.

Agreed.  When I thought about it two years ago my assumption was to not special-case double-width, and I didn't have tabs in mind.  In that case, the n-lines for a single paragraph was a mathematical division and things could be worked out.  With the arbitrary shapes that we have now, I agree it can't be done efficiently.

> As for whether to store paragraphs rather than lines: the basic
> functionality of terminals is around lines, storing paragraphs would make life
> much harder all around vte (including taking care of extremely long paragraphs
> everywhere). If we keep storing lines, it's rewrapping only that is a bit
> cumbersome. Rewrapping is nice to have, but not the core functionality that we
> should build the terminal around.
>
> So I'd personally vote for basically keeping vte as it is, let's just add this
> one feature that actually rewraps the whole scrollback buffer. Or, at least do
> it this way now (and make it into Gnome 3.12), and who knows, maybe completely
> redo it one day.

Whenever you think your patch is ready I'll push it in.  I may go ahead and add a caching stream adaptor.

Thanks, sounds good :)

As for the caching stream adaptor: My patch really does depend on it (I mean its performance is terribly bad without it so it shouldn't be merged to master without caching). If you'd like to implement it, please go ahead and I'll wait for it before I finalize my patch. Or if you'd prefer me to do it, I'll do it in a different bug.

There are those two other bugs that I do depend on, could you please review and merge those patches? I can't tell if they'll require further changes, and there's not much point in finalizing the rewrapping patch until those dependant issues are resolved.

(In reply to comment #55)
> Or if you'd prefer me to do it, I'll do it in a different bug.

Note that what I would do is probably not what you have in your mind, I wouldn't write an "adaptor", just something inline that I already hacked up for reading (cleaned up of course), and a similar one for writing. If you have some time, I'd prefer if you did it because I think you have a special design in your mind that I would break.

Behdad:

Thanks for the commits you made yesterday. How about the following roadmap?

You do caching, I fix 415277. We test it for some time and then release 0.34.9.

In the mean time, I finalize rewrapping. We already have quite big changes for 0.34.9, I'd prefer to test and release them on their own, with no rewrapping yet.

Then we figure out if we want to let the user enable/disable rewrapping. If yes them I'm fine with pushing into 0.34.10 along with a g-t preference (if extending the API is allowed without bumping major number). If not, I think it's such a big change in behavior that we should delay it to 0.35/0.36 (that's vte-next, correct?).

I'm not sure about vte-next's roadmap, but I'd be glad if rewrapping could safely hit next Gnome, as well as next Ubuntu LTS in about half a year. We'll see if we can make it.

vte-next is nowhere near being ready.

I'm working on the caching, I think I finally have a design that could work.  I tried using stdio, but that didn't help.  Will try to have something tomorrow.

Stdio didn't occur to me but sounds like a good idea (apart from having to revert the pread/pwrite optimization). What was the problem? (Maybe we can discuss in email so we don't pollute this ticket.)

A note for future reference about the alternate screen:

IMO alternate screen should not rewrap on resize (btw this is how my current patches behave).

Alternate screen is typically used by full screen applications that handle resizes by themselves and redraw the screen. If we rewrap, you see vertical lines becoming diagonal for a short time (until the application catches up).

Also, with the current implementation (freezing all the rows, and scrollback stored in files) VTE would require to open many new file descriptors (bug 646098 comment 12) and we don't want that.

(In reply to comment #59)
> Stdio didn't occur to me but sounds like a good idea (apart from having to
> revert the pread/pwrite optimization). What was the problem?

For one, it doesn't have a reliable equivalent of ftruncate(), so you have to fflush/ftruncate() for that.  Next, it doesn't have pread/pwrite equivalents.  I addressed the pwrite part by opening in append mode (which is not quite equivalent in cases of write failures, but ignore that).  With that, I was seeing nice caching, except that all my fseek() calls were still hitting the kernel even when the subsequent read was cached...  Not sure if it's a stdio deficiency or it's necessary for some requirement.  At any rate, to fully drop all syscalls I have to track file position myself, which kinda defeats the purpose and complicates the code.

I actually ended up going the stdio-based approach.  It's enabled by default now.  Please check it out.

Cool, thanks :) Sounds a reasonable solution. row/attr streams are 16 bytes per record. Reading 4kB of them previously took 512 kernel calls (seek + read for each). pread/pwrite on their own without caching would divide by a factor of 2, whereas stdio on its own divides it by 256 and makes it probably 2 calls (one seek + read) which is no longer a bottleneck. Low-level IO + hand-written caching could result in a single syscall, but stdio is also good enough, and we save a lot on code complexity and win by using well tested and optimized standard stuff.

Created attachment 256049 [details] [review]
Version 12

Ported to current vte-0-34 head (b959b86). Still draft: works (except for the zsh prompt fix), but needs heavy cleanup.

Created attachment 256120 [details] [review]
Version 13

Ported the ZSH prompt bugfix (bug 708213).

It is terribly complicated.  I mean it's not the code, it's the specification: figuring out the desired behavior with all combinations of changing the height only or width only or both at the same time, lines rewrapping crazily, with short paragraphs above the cursor and long one below or the other way around or whatever... that's what is terrrrrrrrrrribly complicated.

I hope I managed to come up with something that's correct for all reasonable use cases.

Denis, if you're here, could you please test it thorougly? (Or anyone else, of course.)

Patch applies on top of current vte-0-34 (ed5adb6).

In case anyone wants to understand what I'm doing, drop3's comment is wrong:
s/wandered away from/got closer to/

Created attachment 256125 [details] [review]
Version 14

Apply on top of current vte-0-34 head (ed5adb6).

v12-v13 incorrectly computed scroll_delta due to a stupid patch merging mistake.

BTW, Egmont, I think you need to use _vte_stream_head() with index=2,1,0 to correctly call new_page() on the new stream you are building.

I haven't studied the new stdio code yet.

I'm not calling new_page() on the new stream I'm building. This is because paging in the new stream would go out of sync with paging on the other two streams in ways unforeseeable before rewrapping completes. And if I happen to start a new page shortly before I finish rewrapping, and then the normal code also starts a new page soon after, then the scrollback might become way too short. I was thinking about it for a while, but I think allowing a row_stream page that's temporarily larger than the standard paging size is the simplest solution.

I haven't worked on the code since the last version, but use it all the time. Very rarely I see incorrect scroll position, and when that happens, it happens in all the g-t tabs at once. I have no clue about it. Other than this, it seems to work nice.

Created attachment 256660 [details]
Doc

The design is quite complex, so I'd figure out I'd write a documentation that we'll can put under vte/doc/. I'm not confident relying on external data sources (such as my own files on GDrive that I might delete any time). Here's the initial version. Comments, ideas, TODOs, any kinds of fixes (grammatical, English, typos), whatever else are all welcome.

(In reply to comment #70)

> Very rarely I see incorrect scroll position, and when that happens

I found a bug in v14: runlength is incorrectly truncated to at most 4096 bytes (in the line containing "ditto"). This might explain the rare case of incorrect scroll position and such (I'm using the joe editor which doesn't seem to do any hard wrap at all, and when writing the doc (English text without syntax highlight) a screenful is easily more than 4k of continuous attr run).

I'll have a new version real soon with tons of cleanup, and hopefully that bug will be gone too.

Created attachment 256955 [details] [review]
Version 15

Lots of cleanup, hopefully getting quite close to the final version.

Crashes when stress-testing resizing back and forth between normal and extremely narrow (2-3 columns) sizes in vteapp. Somehow (I've no clue yet how) the streams get into a state where the row_record at ring->start position points to a text_offset which is already paged out in text_stream. This in turn causes a read in _vte_frozen_row_column_to_text_offset to silently fail and return with a uninitialized values, later causing the crash. I'll of course make it robust against read failures, but I'd like to understand the underlying issue first.

Behdad, could you please share your opinion here?

The crash is (indirectly) caused by a fundamentally wrong approach in computing the new (faked) value of last_page. In fact, the concept of last_page doesn't quite exist after rewrapping.

Before rewrapping, the text stream contained some rows on the current page, and some others on the previous page. We'd need to keep track of the paging point and compute the number of lines on the current page after rewrapping, and make sure that this page will not be turned away before it's filled up to max rows.

A couple of things make this hopelessly complicated to implement correctly.

One is that after rewrapping, the page turning boundary is not necessarily a line boundary (it could have been at a soft line wrap which is now the middle of a line).

Another thing is that we can (and do) walk backwards in the buffer by thawing rows. The behavior when crossing the previous page turn would be very hard to get correct, especially when a line is split across the pages. This part would require the new fake last_page to be rounded downwards, while the one that guarantees going ahead would require it to be rounded upwards.

An easy solution would be not to allow paging for the next pageful of lines, but that would allow a text_stream page to temporarily grow up to double size, which I wouldn't want to happen. I'd like to turn page as soon as possible, and this altogether with walking backwards is a nightmare.

There's the very complicated condition in _vte_ring_freeze_one_row() that we turn page at two possible points: at the previous page turn (if we're there again), or a pageful later. Very hard to understand, and would interfere in weird ways with any fake new value of last_page.

Truncating the stream to exactly the page boundary is very fragile, it requires nice cooperation between ring.c _vte_ring_freeze_one_row() and vtestream-file.h _vte_file_stream_truncate(): truncating does not throw away the current (emptied) page (though it could), and appending from this point does not create a new page (though it could). Paging is also a concept which on one hand sounds like something that should be private to vtestream-file.h, on the other hand requires heavy cooperation from ring.h

Summary: The current design works, but is IMO hard to understand, fragile, doesn't have a nice responsibility split between the two files, and I can't see how I could accomodate this new tricky requirement of rewrapping.

My suggestion:

Modify the stream API so that it doesn't contain paging anymore. Instead, it would have a new method to advance the tail of the FIFO. (We'd keep the two methods moving the head forward(append) / backward(truncate), and we'd guarantee head >= tail all the time.)

Paging would be a private business of vtestream, hence the code becomes cleaner and easier to verify. Whenever the tail is advanced and there's only a single page used at that time, the head would start the next page. This would pretty much lead to the current behavior under normal operation (including that we wouldn't start a new page at all with infinite scrolling).

In ring.c we win that we no longer need to know at all that vtestream does paging. We can drop the calls to new_page, and the last_page variable. What we'd need to do instead is whenever a line gets dropped from the top of the scrollback, we update the tail of all three streams.

Currently we have to turn page synchronously in all the streams, and this causes a lot of headache with rewrapping. With the new approach turning page would go independently for all three streams, so the new row_stream would automatically be okay without further hacks, there'd be no need to keep it sync with the others wrt paging.

The interface between vtestream-file and ring would be much nicer, and ring's paging code would simplify quite a bit. Plus, all the current headache with faking a last_page value after rewrapping would be whooooosh just gone.

Drawback: updating the tails of {attr,text}_stream would require to read the tail entry of row_stream. With the brand new awesome caching, I don't think it's a big deal.

Behdad, could you please comment on this proposal? Do you like it, if not then why, if yes then do you want to implement it or shall I? :)

Created attachment 257167 [details] [review]
Version 16 part 1/2

This is the refactoring I mentioned in the previous comment.

The refactoring itself is quite straightforward (actually a much smaller change than I anticipated), not much of code change, just an IMO cleaner design.

I've also changed the second argument in two _vte_ring_reset_streams() calls from 0 to ring->writable, as the former is really suspicious and I believe buggy (after all, it initializes the streams with offset[0] and offset[1] being 0, but the next write will happen at a much larger position (since ring->writable is non-zero). However, I didn't come up with a test care for it, it's just a blind code change. Please double check whether it's correct!

Created attachment 257168 [details] [review]
Version 16 part 2/2

The fully cleaned up patch. (Goes on top of part 1, which in turn goes on top of current vte-0-34 head).

I really do hope it works perfectly now. Let's call it RC1.

There's one remaining TODO noted in the patch: I'm yet to study what scrolling_restricted on the normal screen means, how to get there, which applications use it, and what's the desired behavior in that case.

Please start intensive testing, and begin reviewing the code and proofreading the doc, thanks! :)

Created attachment 257169 [details]
Version 16 documentation

And here's <vte>/doc/rewrap.txt which I accidentally forgot to include in the patch :)

Created attachment 257293 [details]
Version 16 documentation revised

fixed some typos spotted by ispell

Just a note: I'm currently travelling and in the middle of other work.  Will be back home in three weeks...  So, please don't let my lack of response discourage you!

Thx for the heads up. Right after your trip I will be away (and pretty much offline) for three weeks (Nov 6-23).

Hopefully I'll have your work reviewed by the time you're back then!

In the mean time, I think the vte feature I will focus on time-permitting is encrypting the buffer before writing to disk.  Been thinking about the design for a while and I think I know where I'm heading; almost.

Created attachment 257305 [details] [review]
Version 16 part 3/2 :D

A small additional fix for version 16. The cursor's column was invalid sometimes because an old row was stuck in the cache.

So far v16 seems to be rock solid (no crash and no misbehavior - apart from this minor one) under heavy usage with debug enabled.

There's one more issue.

In zsh, whenever you narrow the window there's an extra line inserted from the bottom of the terminal.

The reason is: zsh prompt prints \e[J in the current line to clear to EOL. This (or similar escapes like \e[0J or \e[K, as well as the appearance of a new row at the bottom with non-default background) causes VTE to call _vte_row_data_fill() which fills up the current row with '\0' characters, making the current row as wide as the terminal. This, when making the terminal narrower, rewraps to two lines.

This command:
echo -e '\e[42m\e[KX\e[CY\e[C\e[45m\e[K'
illustrates that the '\0' characters are not necessarily at the end of the line, and even the final such segment may contain attribute change. The above command prints "X Y " (4 characters) on green, followed by purple background. For copy-paste purposes it is considered an "X Y" (3 characters). In text_stream it is stored as "X@Y@@@@@@@@@…" (@ here stands for '\0', and they go up to $COLUMNS in length).

Solution ideas I have in my mind (they would all lead to different behavior when rewrapping a colored fill, but they would all fix the zsh issue):

1. The quick hack:

When filling with the default background, the rowdata should be shrunk instead. This would quickly fix the ZSH problem, although it's not really nice that the default background is treated differently than a colored one.

2. Ignore overflowing part at rewrapping:

When rewrapping, the final segment consisting of '\0' only would not be allowed to wrap to the next line, they'd form an overlong (wider than the terminal) line instead. (They'd behave like the current resize behavior of vte when you cut/restore content on the right.)

The first two share the philosophy that the meaning of these escapes is to fill the line with a background at the actual width as of the time when they are printed. The contents of text_stream also remember the width as of that time, even after rewrapping. The 3rd approach changes the philosophy so that the escapes mean to fill the whole line, whatever their actual width is. This also changes text_stream not to depend on the width when the data is printed.

3. Special treatment for the last fill run of identical background:

Treat the final run of '\0' characters of identical attributes differently. Don't store them in text_stream, but store their background color in attr_stream as the attribute of '\n' (which is currently unused). (For soft wrapped rows this value is out of interest because there can't be a trailing fill). Do the opposite when thawing the row unless it's the default background.

I'll keep thinking...

Created attachment 257391 [details] [review]
Version 16 part 4 - zsh fix

This is a quick fix for the aforementioned zsh issue, not strictly related to rewrapping per se.

Apparently the pattern that we don't fill the row if the attributes are the default is already being used at some points of the code, but not at the some others. Adding it to one more relevant place seems to address the zsh issue. I don't have an overview of the code and the general intent here, I'm not sure if maybe this if-condition should be added everywhere...? Behdad, I assume you have a better overview of what's going on here.

As for restricted scrolling (the only //-style comment in the patch, since it was intended to be a TODO for myself, not to be committed), probably the best is to apply bug 710484's tiny patch, and just remove this TODO.

Thank you for you work on this. This issue annoyed me for years. This is a lengthy thread so it was difficult for me to understand if there is a candidate patch already. If there is one I'll gladly test it.

Arokux: yes, there is a candidate patch. I'd be glad if you tested it and shared your experience!

Please download vte-0.34.9 tarball, or checkout git's 0-34 or 0-36 branches. Then apply "version 16", which consists of 4 parts, found in this bugreport.

After compiling, you can either run vteapp with the command ./src/vte2_90, or if you choose to install the library system-wide then make sure to quit all instances of gnome-terminal for the changes to take effect. Of you can set LD_LIBRARY_PATH, and make sure that launching gnome-terminal doesn't connect to an already running instance by following the instructions at https://wiki.gnome.org/Apps/Terminal/Debugging .

One of the "bugs" you'll likely notice is that the shell prompt is sometimes drawn incorrectly if the terminal is resized to be narrower than the prompt. This is because the shell also redisplays its prompt on each resize, which interacts with vte's rewrapping in weird ways. The same happens in any other terminals doing rewrapping too, and I'm not sure what we could do about it. Other than this, I do hope you'll find everything alright.

Created attachment 257885 [details] [review]
Version 16 part 5 - restricted scrolling fix

Pretty much like part 4, this one is for restricted scrolling, such as after an echo -e '\e[5;10r'. Rows would wrap as soon as you narrowed the window by 1 column. Filling with the default background should probably never happen. Probably a more generic solution (one of those outlined in comment 83) would be better than one-off fixes.

Created attachment 258497 [details]
the document from comment 48 as pdf for safekeeping and easier viewing

Created attachment 258843 [details]
the response document from comment 51 as pdf for safekeeping and easier viewing

No news is good news. Everything seems to be perfect :)

- I'm sure the refactoring from comment 74 (patch part 1) was the right thing to do. Please double check the last paragraph from comment 75 whether that's okay.

- The fixes from parts 4 and 5 would deserve a more generic solution instead, as outlined in comment 83. It's not critical or urgent, I think it's okay to have another bugreport open for that after these patches are applied.

- I was wondering if there's anything we could do against the ugly rewrapping of the shell prompt (caused by the shell itself redisplaying it). Maybe not rewrapping the last incomplete paragraph - but that could break if an application is continuously producing output. Maybe not rewrapping the last incomplete paragraph if the terminal is in raw mode (this makes it more likely that the shell prompt is displayed) - sounds terribly error prone. Probably the best is if vte does nothing, but we file feature requests against bash/zsh: a config option could tell them to assume the terminal rewraps the prompt.

- I really think the feature should be optional, especially because of the infinite scrollback feature which can make rewrapping take a few seconds or even much more. Making vte unresponsive for such a long time is not a nice thing. I think delegating the responsibility back to the users, letting them choose reasonable finite scrollback, or rewrapping, or accepting the slowdown at resize is kinda okay. Adding an API and a corresponding g-t pref checkbox is boring but trivial task, I can do it when I'm back.

(In reply to comment #91)
> - I really think the feature should be optional, especially because of the
> infinite scrollback feature which can make rewrapping take a few seconds or
> even much more. Making vte unresponsive for such a long time is not a nice
> thing. I think delegating the responsibility back to the users, letting them
> choose reasonable finite scrollback, or rewrapping, or accepting the slowdown
> at resize is kinda okay. Adding an API and a corresponding g-t pref checkbox is
> boring but trivial task, I can do it when I'm back.

Sorry is if this is a dumb question but would it be possible to make the buffer reflow a deferred or lazy task? Or it could be implemented as a background task as well with progressive results. I know this is probably a little more complex than having the reflow for the whole buffer at once but it would provide a very responsive interface as it would allow the usage of multiple cores too. Also the checkbox would be unnecessary in this case. I'm not sure if the MacOS terminal works the same way but I have never had performance issues with that.

It's not a dumb question at all. Unfortunately it wouldn't make it a "little more complex" as you said, it'd make it magnitudes more complex. Behdad and me have put quite a lot of thinking into it and we can't see how this could be done. For starters, probably the whole buffer storage would have to be reimplemented to something way more complicated (the current data structure is linear, we'd need something where you can change (insert/remove) anywhere in the middle). Then there's a problem with the scrollbar position which would have to be estimated, and then figure out what should happen as the user drags it and so we get to know it more accurately.

The current code is already quite complex, any lazyness would make it even more complicated, harder to write and harder to test, and more likely to contain hard-to-reproduce bugs.

I'm not sure about MacOS's default Terminal, or about iTerm - do they allow infinite scrollbar? I don't have access to a Mac, so I couldn't study any of them. With VTE, noticable slowdown (~0.2 seconds) starts at around 1M lines which is way higher than the default 5k or so. If the goal is to get rid of the config option, the algorithm would have to run in constant time, so even a scrollback buffer of 1G lines should resize "immediately".

The current bugreport has been here for 6.5 years. I've always wanted to implement it, and now I had to sit home a lot with a slightly broken leg so I figured out I'd do it. It took me a month and a half to finalize it, building on current Vte code as much as possible - imagine how much time it would have taken if I started to rewrite the ring, the storage and so on. I won't have time, nor motivation to further improve it, other than the necessary followup fixes if bugs are found. Given the current condition of how little engineering effort is put in Vte, probably the main developers won't have time for it either. That being said, I'm pretty sure that patches are welcome, but I think it's very unlikely anyone will work on it on the next 10+ years. But I encourage you to open a followup bug for this request, once my patches are submitted. Or to work on it :)

üdv:
egmont

What about tying it to a key combo? If that's allowed as a config option one could keep infinite scroll back and initiate a reflow when they want, knowing it could take a while

I can't tell if any users would bother manually pressing that keycombo - never rewrapping, or always rewrapping automatically sound much more reasonable to me. However, I don't use infinite scrollback (I can't really see the point in that), so I'd let those who use it decide it. It should be very easy to implement it (just trigger a resize to the same size with rewrapping enabled when that key is pressed), but please don't count on me to do it. But first let's wait to hear Behdad's opinion on this whole story, I'm not even sure he'll agree with my opinion about the checkbox.

Now that I think of it, I started to like Travis's idea. One checkbox: rewrap automatically or manually. If manual, a keycombo (maybe Shift+Ctrl+R) or a menu entry rewraps. (The menu entry could be disabled if there's nothing to rewrap.) If you never want to rewrap, you simply never activate that, and you're back to my proposal in comment 91. Yup, I actually like it :)

In light of the magnitude you indicated, the key code or the checkbox are either good options. I checked the MacOS terminal and it's cheating. :) With 1M lines, as long as you're at the end of the buffer, it works instantaneously. But moving the scrollbar will cause it to hiccup (~1s lag at this size). However, these buffer lengths are not realistic in my opinion and still, few sec lag on resize is not a huge deal. It's not like as if it happened on every scroll event.

üdv:
Andris, BUTE :)

What happens in MacOS terminal with 100M scrollback if you begin dragging the scrollbar crazily? Does it lag for a second a hundred times?

Have you tried iTerm2? :)

The problem with our current solution is that the time is linear to the buffer length. If rewrapping can take 1 sec (which is kinda still acceptable) then it can very easily take 10 seconds or 100 seconds which are definitely not okay.

For details about our brainstorms you might want to look at the two attached pdf files, as well as the doc of the current implementation (also attached here).

You say "these buffer lengths are not realistic". Personally I'd agree with you and limit the scrollback to at most 1M. However apparently there's a broad demand for infinite scrollback, and it's already implemented so removing would be a big regression for some users.

I agree that the currently proposed solution is not ideal and perhaps there is a decent way to solve the problem, but this is what we have now and probably we won't have the decent solution implemented for a long time :(

ex-BUTE here :)

MacOS terminal: Ok, it took several minutes to produce 10M lines. At this point reflow is completely asynchronous. I kept on seeing the same text for a while and then the new flow appeared after a few seconds. Scrolling was always continuous.

iTerm2: scrolling is a little choppy in any case for long buffer. After a first pause the reflow happens in about 1s for 5M lines. But it's practically useless for 10M (spins the i5 CPU at 15% for minutes). Very non-linear implementation both in time and space.

In theory this would be an easily parallelizable task. Though if the current implementation does not support it, then it would be too much work for very little gain. What you have done so far yield a significantly better UX already. Thanks for it!

(I know, you were my examiner at the computation theory grand exam. Good old days.)

Parallelizing wouldn't be a huge win, maybe a factor of 2-4 or so, who cares about that? :) The real win would be either finding the right data structures which allow us to rewrap on demand (whenever the relevant part needs to be shown), or to rewrap as a background task (that is: as soon as possible, but without blocking the main functionality until then). Both sound very complicated.

Thx for sharing Mac Term / iTerm behavior with us. 

(Oops, I'm sorry... too many people, too many that I don't remember :/ Good old days, yeah!)

I have committed the patches to vte-0-36 so we can get some testing done during gnome 3.11; we'll re-evaluate this before code freeze.

(In reply to comment #74)
> 
> Summary: The current design works, but is IMO hard to understand, fragile,
> doesn't have a nice responsibility split between the two files, and I can't see
> how I could accomodate this new tricky requirement of rewrapping.
> 
> My suggestion:
> 
> Modify the stream API so that it doesn't contain paging anymore. Instead, it
> would have a new method to advance the tail of the FIFO. (We'd keep the two
> methods moving the head forward(append) / backward(truncate), and we'd
> guarantee head >= tail all the time.)
> 
> Paging would be a private business of vtestream, hence the code becomes cleaner
> and easier to verify. Whenever the tail is advanced and there's only a single
> page used at that time, the head would start the next page. This would pretty
> much lead to the current behavior under normal operation (including that we
> wouldn't start a new page at all with infinite scrolling).
> 
> In ring.c we win that we no longer need to know at all that vtestream does
> paging. We can drop the calls to new_page, and the last_page variable. What
> we'd need to do instead is whenever a line gets dropped from the top of the
> scrollback, we update the tail of all three streams.
> 
> Currently we have to turn page synchronously in all the streams, and this
> causes a lot of headache with rewrapping. With the new approach turning page
> would go independently for all three streams, so the new row_stream would
> automatically be okay without further hacks, there'd be no need to keep it sync
> with the others wrt paging.
> 
> The interface between vtestream-file and ring would be much nicer, and ring's
> paging code would simplify quite a bit. Plus, all the current headache with
> faking a last_page value after rewrapping would be whooooosh just gone.
> 
> Drawback: updating the tails of {attr,text}_stream would require to read the
> tail entry of row_stream. With the brand new awesome caching, I don't think
> it's a big deal.
> 
> Behdad, could you please comment on this proposal? Do you like it, if not then
> why, if yes then do you want to implement it or shall I? :)

Ok, I finally got to review this after seeing ChPe commit it.  After thinking about it, a lot, I really like this!  Genius!  I'll think about it more, but I believe it's correct.  Thanks!

If you are thinking about adding a checkbox and have this feature optional I would prefer this new behavior to be the default at least. The old behavior is incredibly buggy and I remember it was the first bug I faced when trying Linux back in 2006. Even if it lags and freezes the main thread for a while I must say that it's still much better than the old buggy mess. Kudos for looking into this.

I'd prefer to hear back from the main developers stating their opinion, my personal preference would be to add a checkbox, but make the new behavior the default as you suggest.

I'm fine with that.

Created attachment 264293 [details] [review]
API calls to configure the feature in VTE, plus cmdline option for vteapp

Created attachment 264294 [details] [review]
Expose the config option in gnome-terminal

(FYI: I only tested the patch with g-t 3.10, compiling 3.11 would require me to upgrade Gtk+, I don't feel like doing that. I hope it works fine with 3.11 too.)

Please check these two patches for functional correctness as well as correct use of English in user-facing and developer-facing texts.

I'm also wondering whether maybe "reflow" sounds better to the end users than "rewrap", dunno... I'd keep the word "rewrap" everywhere internally since that's the terminology used by terminals at the end of the line, it's just about the UI string.

Haha, I've just found http://blogs.gnome.org/mclasen/2013/12/09/a-terminal-surprise/#comment-918 :-)  It's quite an offer, I might actually end up attending :D

(In reply to comment #109)
> Haha, I've just found
> http://blogs.gnome.org/mclasen/2013/12/09/a-terminal-surprise/#comment-918 :-) 
> It's quite an offer, I might actually end up attending :D

Humm.  You should attend, and you should submit a talk.  You attending is an excellent reason for me to attend!  We can have a little hackfest, perhaps get a couple other people to join in too.  Sounds like a plan to me!  All you need is to make sure you have time to attend.  We can make sure your travel is sponsored by the foundation if needed.  Lets seriously talk about it.

Actually I'm starting to think about it seriously :) But let's continue the discussion somewhere else (email, irc, whatever...).