Search refactor proposal

[nojvek]

So I've been thinking about this over sleep 😴. There are a number of search related issues:

1. multiple finds on same line Finding multiple instances on the same line #1763
2. search as you type Search addon: Support "find as you type" #1660 - PR Fix #1660: Search as you type #1826
3. return number of results i.e 1 of 24 (how vscode editor search behaves) Search addon: Return the number of results of a search #1659
4. show all search ranges and introduce new selection type Search addon: Introduce a new selection type so that multiple ranges can be highlighted at once #1653

#1826 introduces the concept of a lineCache with a ttl, that the search creates when findNext/findPrevious are called. Even with 10,000 lines in buffer, it's quite fast to scan the entire buffer for search results.

I propose we refactor search to fix multiple issues and yet make it elegant.

implement a getRangesForSearchTerm(term:string, searchOptions: ISearchOptions): IRange[]

for the same search term, findNext/findPrevious goes to the adjacent IRange and highlights the selection.

if the term is not the same as last one, then we call getRangesForSearchTerm(..) and move the highlight to the adjacent range depending on whether search was incremental or not.

VSCode / other clients can also use the IRange results to show scrollbar decorations of where search matched.

[Tyriar]

Sounds good to me, at least as an internal API initially until we figure out if we should surface the ranges outside 😃

VSCode / other clients can also use the IRange results to show scrollbar decorations of where search matched.

We can't really do this as the scroll bars in vscode and xterm.js have different implementations and can't really be shared (easily at least). Also ranges are invalidated when the lines shift, but we could get around this by using markers (Terminal.addMarker) to keep track of the ranges. @mofux suggested in #1380 (comment) that we support decorations which could let us do something like that though (basically markers with some visuals).

[jerch]

About the line cache: Should we do this at a higher level, maybe in the buffer? To me it seems translateBufferLineToString is a bottleneck when several consumers (linkifier, search addon, some other buffer reader) are listening to buffer changes, see #1775 (comment)
Note that #1775 speeds this a little bit up, still with more than one consumer it will be called several times for the same buffer lines (already thought about some indicator at line level to track changes).

This kinda affects the current discussion about the search plugin and the linkify stuff over here #1825.

[Tyriar]

@jerch I'm worried about the extra memory it would consume if we did this for the whole buffer. Is it only the viewport that we access often? Perhaps we could just cache those lines while they exist?

[jerch]

@yeah true, memory consumption would be quite high.

I think there are different needs regarding whole buffer vs. just the viewport buffer access:

• the linkifier is imho fine with restriction to the viewport (with some overscan)
• search plugin is meant to search through the whole buffered data, still it could do this sequentially with viewport jumps (not sure about the need to search at once through all buffer data)
• vscode has this lineFeed consumer, it basically reads the data whenever a line is seen as complete
• there might be other use cases

What currently makes translateBufferLineToString so expensive is the cell looping and concat into a line string. And on top of that, it is triggered several times for multiple consumers. A first wild idea would be to cache a string representation on a line once it got requested by translateBufferLineToString and keep it until the line data gets invalidated/changed. We would need 2 more bytes memory on average per cell for this, means a terminal with 100 rows x 1000 lines needs 200 kB additional memory plus 1k pointer space (arraybuffer is currently at ~1.5 MB for that size). This is just a first rough idea, not sure if we should do that, it also would reintroduce tons of GC events and makes the typed array buffer partly questionable.

Edit: I think the question here is whether we should optimize the buffer for translateBufferLineToString access as well, there are buffer layouts possible where we could get this cheaper, e.g. hold the content data in a string per line from the beginning and put only attrs and cell index offsets in the array buffer. Note that I am still not done with the final buffer layout (due to the BufferLine class it is quite easy to test different approaches).

[Tyriar]

Forked that discussion to #1836

[NHDaly]

Hi! :)

I was playing around with hooking up find-and-replace for the Julia Console in the Atom package Juno (JunoLab/Juno.jl#212). These changes would also make that a lot easier!

No pressure to decide one way or the other, I just wanted to add another datapoint.

--

The Atom find-and-replace api is similar to what you've described in the top comment: there's a search function (findAndMarkAllInRangeSync) which finds all the results, "marks" them, and returns the marks so you can iterate through them. Then findNext just gets the next result and highlights them one at a time.

Returning the IRange -- or at least the count of matches -- would make integrating with that API really simple! :)

[Tyriar]

We can consider this while doing #1653, merging