Finding backwards sometimes displays incorrect match index

NEW
Unassigned

Status

()

Toolkit
Find Toolbar
P5
normal
3 years ago
2 years ago

People

(Reporter: kats, Unassigned)

Tracking

Trunk
Points:
---

Firefox Tracking Flags

(firefox40 affected)

Details

Attachments

(1 attachment)

Created attachment 8607507 [details]
File to find on

1. Load attached page
2. Cmd+g to bring up find bar, and type "***" (without quotes) as the search string
3. Cmd+shift+g repeatedly to find backwards.

Expected:
The find index (e.g. the 37 in "37 of 43 matches") in the find bar steadily decrements until it wraps around.

Actual:
The find index decrements to 37, and then upon doing a backwards find again it goes up to 43 and stays at 43 until you wrap the document.
(I saw this on an Aurora build of https://hg.mozilla.org/releases/mozilla-aurora/rev/b03c5f1a77a1 on OS X, but I doubt it's platform-specific...)
status-firefox40: --- → affected
status-firefox41: affected → ---
Luís, want to investigate? I can reproduce trivially - it works until 37 out of 43, and after that it gets stuck at 43 of 43. Presumably has something to do with the overlapping matches in the "**********" string? Still, curious little bug, wondered if you'd be interested. :-)
Component: General → Find Toolbar
Flags: needinfo?(quicksaver)
Product: Firefox → Toolkit
That's definitely because it's finding different ranges when going backwards than Finder._countMatchesInWindow() [1] finds because that only counts forwards. I don't think that's a problem with Finder._countMatchesInWindow, but rather with nsTypeAheadFind [2] assuming every match it finds is "valid" (which technically it is because... well, it's a match).

Adding a findBackwards flag to countMatchesInWindow could work, although I don't know if that's desirable as it may cause inconsistencies; total matches "changing" when going forwards to backwards and vice versa.

However a solution that goes through nsTypeAheadFind (such as skipping a group of characters in order to match the same ranges as when going forward) is out of my abilities as that's C++. So I can only help depending on what route you find to be better.

[1] http://mxr.mozilla.org/mozilla-central/source/toolkit/modules/Finder.jsm#349
[2] http://mxr.mozilla.org/mozilla-central/source/toolkit/components/typeaheadfind/nsTypeAheadFind.cpp
Flags: needinfo?(quicksaver)
FWIW I'd vote for fixing nsTypeAheadFind (whatever that would entail) for consistency when finding forwards and backwards, as the matches backwards also don't match the highlights if you press the Highlight All button.
OK. From that description it's not quite clear to me what it would take to fix nsTypeAheadFind. I don't think there's a straightforward way to figure out which characters to "ignore" when going backwards, based on matches made when you go forward, unless we just reuse the same list of matches when matching forwards. I'll try having a look sometime next week.
Flags: needinfo?(gijskruitbosch+bugs)
(In reply to :Gijs Kruitbosch from comment #5)
> I don't think there's a straightforward way to figure
> out which characters to "ignore" when going backwards, based on matches made
> when you go forward, unless we just reuse the same list of matches when
> matching forwards. I'll try having a look sometime next week.

That's what I meant with "it's still a valid match technically", I should have been more explicit. nsTypeAheadFind's search is live, that is every time you find the next/previous match, it starts wherever the cursor is at the page, and goes backwards and forwards a character to look for a match. There is no list of matches here. :(

There's also no list for the counter, it counts them live as well each time it updates, and only counts forward because that's how nsFind works as well.

The closest thing there is to a list is when highlighting all matches, you could request an array of ranges from the selection controller. But that would mean always searching the entire document without limit all the time just to make sure all the matches are the same... And that becomes resource intensive very fast. And error prone because page contents change easily as well, nulling that list.

Adding to all that, you have to consider that the cursor position also changes. It's easy to click anywhere in the middle of all of those "****" to get different matches than the counter/highlights expect even when going forward, because that's where nsTypeAheadFind will start.

Not saying all this to sound discouraging, but when I voted to fix nsTypeAheadFind, I meant of course "if possible". :)
(In reply to Luís Miguel [:quicksaver] from comment #3)
> Adding a findBackwards flag to countMatchesInWindow could work, although I
> don't know if that's desirable as it may cause inconsistencies; total
> matches "changing" when going forwards to backwards and vice versa.

This seems the most sane to me.

> However a solution that goes through nsTypeAheadFind (such as skipping a
> group of characters in order to match the same ranges as when going forward)

Well, that's a hard problem, I think...

I *think* that the only case where this bug happens is where some string S consists entirely of X identical characters, and the document has a string S' that contains Y such characters, where X is not a divisor of Y. So for example, in a document with:

aaaaaa
(6 'a's)

searching for 'a' is fine, as is searching for 'aa' or 'aaa', but searching for 'aaaa' will get you this buggy behaviour. If the document had:

aaaaaaa
(7 'a's)

searching for 'a' and 'aaaaaaa' (1 or 7 'a's) would be fine, and anything inbetween that would be buggy.

In order to compensate for this, you would need to specialcase such strings that are entirely made up of identical characters, then "keep matching" to see how long the sequence S' in the document was, and adjust accordingly (or not at all).

This does also mean this is a bit of an edgecase, so I'm not sure how much we should invest in it...

(In reply to Luís Miguel [:quicksaver] from comment #6)
> Adding to all that, you have to consider that the cursor position also
> changes. It's easy to click anywhere in the middle of all of those "****" to
> get different matches than the counter/highlights expect even when going
> forward, because that's where nsTypeAheadFind will start.

This is confusing to me... won't the result counting use the same cursor position as the 'find next' logic? If not, then we're screwed here, yeah...
Flags: needinfo?(gijskruitbosch+bugs) → needinfo?(quicksaver)
(In reply to :Gijs Kruitbosch from comment #7)
> (In reply to Luís Miguel [:quicksaver] from comment #3)
> > Adding a findBackwards flag to countMatchesInWindow could work, although I
> > don't know if that's desirable as it may cause inconsistencies; total
> > matches "changing" when going forwards to backwards and vice versa.
> 
> This seems the most sane to me.

I don't fully agree. With Highlight All checked, the matches won't match the highlights either. I think it'll be worse UX to visually see the current match not "match" what was already there and see the counter still going down "correctly". As a user I would think "Well, which is it then?". But it's not like it's perfect now so...

(In reply to :Gijs Kruitbosch from comment #7)
> This does also mean this is a bit of an edgecase, so I'm not sure how much
> we should invest in it...

Agreed, this is not something you'll run into everyday at least.

> (In reply to Luís Miguel [:quicksaver] from comment #6)
> > Adding to all that, you have to consider that the cursor position also
> > changes. It's easy to click anywhere in the middle of all of those "****" to
> > get different matches than the counter/highlights expect even when going
> > forward, because that's where nsTypeAheadFind will start.
> 
> This is confusing to me... won't the result counting use the same cursor
> position as the 'find next' logic? If not, then we're screwed here, yeah...

Short answer, we're kinda screwed yeah. It's just as you mentioned in your "aaa"s example, but can happen not only from the edges of the string but from the middle as well.

Both the highlights and the counter start from the very top of the document and go to the bottom in one go, both Finder._highlightIterator and Finder._countMatchesInWindow use Finder._findIterator [1], which uses nsFind and that has no reverse gear:
- the counter does this on every find next/previous iteration and on each match it checks if it's the same match as the currently selected text (current match from find next/previous);
- the highlights are placed only when the find query changes or when you directly press the highlight all button (that's why I mentioned it's the closest thing you have to a list).

In the example document, open the findbar, type in "***" as before. Now with your mouse click between the very first and second * in the document, to place the cursor there. F3 will give you the same bug going forward because nsTypeAheadFind (find next/previous) started from where you clicked. 

nsTypeAheadFind is live like that, it starts wherever the cursor is (from wherever you click f.i.), goes char by char until it finds a match, and moves the cursor to the beginning/end of the found match to start from there if the user wants to find further.

[1] http://mxr.mozilla.org/mozilla-central/source/toolkit/modules/Finder.jsm#389

FYI, it's not necessarily only strings with the same characters but rather repeating patterns. For instance, in a string containing "ababababab" (5x "ab"), if you look for "abab" (2x "ab") you'll run into the same thing.
Flags: needinfo?(quicksaver)
(In reply to Luís Miguel [:quicksaver] from comment #8)
> With Highlight All checked, the matches won't match the
> highlights either.

...

> Short answer, we're kinda screwed yeah. It's just as you mentioned in your
> "aaa"s example, but can happen not only from the edges of the string but
> from the middle as well.

...

> FYI, it's not necessarily only strings with the same characters but rather
> repeating patterns. For instance, in a string containing "ababababab" (5x
> "ab"), if you look for "abab" (2x "ab") you'll run into the same thing.

Ugh. Everything is horrible.

OK, well, target: Future / would take patches, not going to spend time on this myself right now. :-(
Priority: -- → P5
You need to log in before you can comment on or make changes to this bug.