Bug 75220 – Find indicators overlap when a match spans multiple text boxes

• Status: RESOLVED
• Resolution: FIXED
• Component: WebKit2

Find indicators overlap when a match spans multiple text boxes

Created attachment 120522 [details]
If find indicators for individual text boxes would overlap, use a single find indicator encompassing all text boxes

[Darin Adler]

Comment on attachment 120522 [details]
If find indicators for individual text boxes would overlap, use a single find indicator encompassing all text boxes

View in context: https://bugs.webkit.org/attachment.cgi?id=120522&action=review

> Source/WebCore/ChangeLog:8
> +        * WebCore.exp.in: Exported new unionRect(const Vector<FloatRect>&) and exisitng

Typo: exisitng

> Source/WebCore/platform/graphics/FloatRect.h:243
> +FloatRect unionRect(const Vector<FloatRect>&);

Wish there was a generic way to make this take any collection with begin/end instead of just a Vector specifically.

> Source/WebKit2/UIProcess/FindIndicator.cpp:90
> +static bool findIndicatorsForTextRectsOverlap(const Vector<WebCore::FloatRect>& textRects)

No need for WebCore:: prefix here.

> Source/WebKit2/UIProcess/FindIndicator.cpp:108
> +        for (size_t j = indicatorRects.size(); j; ) {
> +            --j;
> +            if (indicatorRect.intersects(indicatorRects[j]))
> +                return true;
> +        }

Is there any way to mitigate the n^2 nature of this algorithm?

(In reply to comment #2)
> (From update of attachment 120522 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=120522&action=review
> 
> > Source/WebCore/ChangeLog:8
> > +        * WebCore.exp.in: Exported new unionRect(const Vector<FloatRect>&) and exisitng
> 
> Typo: exisitng

Fixed.

> > Source/WebKit2/UIProcess/FindIndicator.cpp:90
> > +static bool findIndicatorsForTextRectsOverlap(const Vector<WebCore::FloatRect>& textRects)
> 
> No need for WebCore:: prefix here.

Fixed.

> 
> > Source/WebKit2/UIProcess/FindIndicator.cpp:108
> > +        for (size_t j = indicatorRects.size(); j; ) {
> > +            --j;
> > +            if (indicatorRect.intersects(indicatorRects[j]))
> > +                return true;
> > +        }
> 
> Is there any way to mitigate the n^2 nature of this algorithm?

Sadly, I don’t know the answer.

Thanks for the review!

Landed in <http://trac.webkit.org/r103677>.

[Alexey Proskuryakov]

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

<rdar://problem/11215218>