Bug 229926 – In-page search results overlay broken if the result spans more than two elements

• Component: Layout and Rendering
• Status: RESOLVED FIXED

[alan]

<rdar://82741616>

try this very simple case of "<span>left</span>middle<span>right</span>" we produce gaps between the selection rects (not always repro)

[alan]

Created attachment 437371 [details]
Patch

[Tim Horton]

Comment on attachment 437371 [details]
Patch

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

> Source/WebCore/platform/graphics/PathUtilities.cpp:263
> +    // FIXME: Replace it 2 dimensional sort.

Grammar it

[alan]

Created attachment 437374 [details]
[fast-cq]Patch

[EWS]

Committed r282052 (241352@main): <https://commits.webkit.org/241352@main>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 437374 [details].

[Darin Adler]

Comment on attachment 437374 [details]
[fast-cq]Patch

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

> Source/WebCore/platform/graphics/PathUtilities.cpp:269
> +    // FIXME: Replace it with 2 dimensional sort.
> +    std::sort(sortedRects.begin(), sortedRects.end(), [](FloatRect a, FloatRect b) {
> +        return a.x() < b.x();
> +    });
> +    std::sort(sortedRects.begin(), sortedRects.end(), [](FloatRect a, FloatRect b) {
> +        return a.y() < b.y();
> +    });

I’m not sure what a two-dimensional sort is exactly, but we easily do this with a single sort call so it’s more efficient than two sorts in a row. Here is one of the many ways to write that:

    std::sort(sortedRects.begin(), sortedRects.end(), [](FloatRect a, FloatRect b) {
        if (a.y() != b.y())
            return a.y() < b.y();
        if (a.x() != b.x())
            return a,x() < b.x();
        if (a.height() != b.height())
            return a.height() < b.height();
        return a.width() < b.width();
    });

In the example above I also sorted based on the size, because if there is any chance that there are two rectangles that have the same x/y, it’s better to not have any randomness in the result. Another way to avoid that is to use std::stable_sort, but I think this is better. The lambda is irritatingly long, maybe there is a more efficient way to write it, but it will be faster than two sorts, and more predictable than just sorting by x/y and not width/height.

I’m sure there are many other ways, and some with subtle differences like how they handle rectangles with NaN values in them. Maybe there’s a better idiom.

Also wondering if const FloatRect& is more efficient or less than Float for the lambda arguments. Maybe we can even use auto&?

[alan]

(In reply to Darin Adler from comment #5)
> Comment on attachment 437374 [details]
> [fast-cq]Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=437374&action=review
> 
> > Source/WebCore/platform/graphics/PathUtilities.cpp:269
> > +    // FIXME: Replace it with 2 dimensional sort.
> > +    std::sort(sortedRects.begin(), sortedRects.end(), [](FloatRect a, FloatRect b) {
> > +        return a.x() < b.x();
> > +    });
> > +    std::sort(sortedRects.begin(), sortedRects.end(), [](FloatRect a, FloatRect b) {
> > +        return a.y() < b.y();
> > +    });
> 
> I’m not sure what a two-dimensional sort is exactly, but we easily do this
> with a single sort call so it’s more efficient than two sorts in a row. Here
> is one of the many ways to write that:
> 
>     std::sort(sortedRects.begin(), sortedRects.end(), [](FloatRect a,
> FloatRect b) {
>         if (a.y() != b.y())
>             return a.y() < b.y();
>         if (a.x() != b.x())
>             return a,x() < b.x();
>         if (a.height() != b.height())
>             return a.height() < b.height();
>         return a.width() < b.width();
>     });
> 
> In the example above I also sorted based on the size, because if there is
> any chance that there are two rectangles that have the same x/y, it’s better
> to not have any randomness in the result. Another way to avoid that is to
This is so much better! Thanks!!!