Bug 141146 – Simple line layout: use std::upper_bound in splitFragmentToFitLine()

• Status: RESOLVED
• Resolution: FIXED
• Component: Layout and Rendering

[zalan]

instead of having yet another binary search implementation.

[zalan]

Created attachment 245854 [details]
Patch

[zalan]

Created attachment 245876 [details]
Patch

[WebKit Commit Bot]

Attachment 245876 [details] did not pass style-queue:


ERROR: Source/WebCore/rendering/SimpleLineLayout.cpp:303:  difference_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WebCore/rendering/SimpleLineLayout.cpp:304:  value_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WebCore/rendering/SimpleLineLayout.cpp:307:  iterator_category is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
Total errors found: 3 in 4 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Antti Koivisto]

Comment on attachment 245876 [details]
Patch

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

> Source/WebCore/rendering/SimpleLineLayout.cpp:302
> +    typedef std::pair<unsigned, unsigned> WidthRange;

The code would read bit better if this was struct { unsigned begin, unsigned end; }.
Specifically with pair it is unclear if the second field is length or end.

> Source/WebCore/rendering/SimpleLineLayout.cpp:307
> +    typedef ptrdiff_t difference_type;
> +    typedef WidthRange value_type;
> +    typedef WidthRange* pointer;
> +    typedef WidthRange& reference;
> +    typedef std::forward_iterator_tag iterator_category;

These are all needed?

> Source/WebCore/rendering/SimpleLineLayout.cpp:387
> +    auto it = std::upper_bound(begin(fragmentToSplit), end(fragmentToSplit), availableWidth, [&](float availableWidth, const FragmentWidthIterator::WidthRange& range) {

I think we don't like implicit capture. You should capture just the stuff you use, [&flowContentsIterator].

> Source/WebCore/rendering/SimpleLineLayout.cpp:388
> +        // FIXME: use x position instead of 0.

This comment is bit unclear. Is it a bug are unsupported feature?

[Darin Adler]

Comment on attachment 245876 [details]
Patch

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

>> Source/WebCore/rendering/SimpleLineLayout.cpp:307
>> +    typedef std::forward_iterator_tag iterator_category;
> 
> These are all needed?

The modern way to do this is to derive from std::iterator<>. We could get all of these defined just by specifying std::forward_iterator_tag and giving the type. It would make all the other typedefs for us.

> Source/WebCore/rendering/SimpleLineLayout.cpp:324
> +        this->operator++();

I normally prefer to write:

    ++*this;

Not sure which way is clearer.

> Source/WebCore/rendering/SimpleLineLayoutFlowContentsIterator.h:126
> +    if (splitPosition == end()) {
> +        newFragment.m_start = end();
> +        newFragment.m_width = 0;
> +        newFragment.m_isCollapsed = false;
> +        newFragment.m_isBreakable = false;
> +        return newFragment;
> +    }
> +
> +    if (splitPosition == start()) {
> +        m_end = start();
> +        m_width = 0;
> +        m_isCollapsed = false;
> +        m_isBreakable = false;
> +        return newFragment;
> +    }

Do we really need these? Can’t we write the code below to handle these cases efficiently?

> Source/WebCore/rendering/SimpleLineLayoutFlowContentsIterator.h:132
> +    bool single = start() + 1 == end();
> +    m_isBreakable = single ? false : m_isBreakable;
> +    m_isCollapsed = single ? false : m_isCollapsed;

How about writing these in a more straightforward style?

    if (start() + 1 == end()) {
        m_isBreakable = false;
        m_isCollapsed = false;
    }

> Source/WebCore/rendering/SimpleLineLayoutFlowContentsIterator.h:138
> +    newFragment.m_start = splitPosition;
> +    newFragment.m_width = flowContentsIterator.textWidth(newFragment.start(), newFragment.end(), 0);
> +    single = newFragment.start() + 1 == newFragment.end();
> +    newFragment.m_isBreakable = single ? false : newFragment.m_isBreakable;
> +    newFragment.m_isCollapsed = single ? false : newFragment.m_isCollapsed;

Since this code is identical to what’s above, how about a helper function to avoid repeating the code twice?

[Antti Koivisto]

Comment on attachment 245876 [details]
Patch

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

> Source/WebCore/rendering/SimpleLineLayoutFlowContentsIterator.h:142
>  inline UChar FlowContentsIterator::characterAt(unsigned position) const

You should rename FlowContentsIterator at some point. We currently have both FlowContentsIterator and FlowContents::Iterator which is confusing. This is more like TextFragmentIterator.

[zalan]

Created attachment 245887 [details]
Patch

[Antti Koivisto]

Comment on attachment 245887 [details]
Patch

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

> Source/WebCore/rendering/SimpleLineLayout.cpp:304
> +typedef struct {
> +    unsigned start { 0 };
> +    unsigned end { 0 };
> +} WidthRange;
> +class FragmentWidthIterator : public std::iterator<std::forward_iterator_tag, WidthRange> {

This could be just struct WidthRange {} instead of a typedef.

Missing empty line after.

> Source/WebCore/rendering/SimpleLineLayout.cpp:336
> +    FragmentWidthIterator& operator--()
> +    {
> +        --m_fragmentIndex;
> +        return *this;
> +    }
> +
> +    FragmentWidthIterator operator--(int)
> +    {
> +        FragmentWidthIterator result(*this);
> +        --*this;
> +        return result;
> +    }

This is marked as a forward iterator. Why does it have operator--?

[zalan]

Created attachment 245888 [details]
Patch

[zalan]

(In reply to comment #4)
> Comment on attachment 245876 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=245876&action=review
> 
> > Source/WebCore/rendering/SimpleLineLayout.cpp:302
> > +    typedef std::pair<unsigned, unsigned> WidthRange;
> 
> The code would read bit better if this was struct { unsigned begin, unsigned
> end; }.
> Specifically with pair it is unclear if the second field is length or end.
> 
Good point! Done.

> > Source/WebCore/rendering/SimpleLineLayout.cpp:307
> > +    typedef ptrdiff_t difference_type;
> > +    typedef WidthRange value_type;
> > +    typedef WidthRange* pointer;
> > +    typedef WidthRange& reference;
> > +    typedef std::forward_iterator_tag iterator_category;
> 
> These are all needed?
No. Fixed.

> 
> > Source/WebCore/rendering/SimpleLineLayout.cpp:387
> > +    auto it = std::upper_bound(begin(fragmentToSplit), end(fragmentToSplit), availableWidth, [&](float availableWidth, const FragmentWidthIterator::WidthRange& range) {
> 
> I think we don't like implicit capture. You should capture just the stuff
> you use, [&flowContentsIterator].
Done.

> 
> > Source/WebCore/rendering/SimpleLineLayout.cpp:388
> > +        // FIXME: use x position instead of 0.
> 
> This comment is bit unclear. Is it a bug are unsupported feature?
Done.

[zalan]

(In reply to comment #5)
> Comment on attachment 245876 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=245876&action=review
> 
> >> Source/WebCore/rendering/SimpleLineLayout.cpp:307
> >> +    typedef std::forward_iterator_tag iterator_category;
> > 
> > These are all needed?
> 
> The modern way to do this is to derive from std::iterator<>. We could get
> all of these defined just by specifying std::forward_iterator_tag and giving
> the type. It would make all the other typedefs for us.
Thanks. Fixed.

> 
> > Source/WebCore/rendering/SimpleLineLayout.cpp:324
> > +        this->operator++();
> 
> I normally prefer to write:
> 
>     ++*this;
> 
> Not sure which way is clearer.
Fixed.

> 
> > Source/WebCore/rendering/SimpleLineLayoutFlowContentsIterator.h:126
> > +    if (splitPosition == end()) {
> > +        newFragment.m_start = end();
> > +        newFragment.m_width = 0;
> > +        newFragment.m_isCollapsed = false;
> > +        newFragment.m_isBreakable = false;
> > +        return newFragment;
> > +    }
> > +
> > +    if (splitPosition == start()) {
> > +        m_end = start();
> > +        m_width = 0;
> > +        m_isCollapsed = false;
> > +        m_isBreakable = false;
> > +        return newFragment;
> > +    }
> 
> Do we really need these? Can’t we write the code below to handle these cases
> efficiently?
Removed.

> 
> > Source/WebCore/rendering/SimpleLineLayoutFlowContentsIterator.h:132
> > +    bool single = start() + 1 == end();
> > +    m_isBreakable = single ? false : m_isBreakable;
> > +    m_isCollapsed = single ? false : m_isCollapsed;
> 
> How about writing these in a more straightforward style?
> 
>     if (start() + 1 == end()) {
>         m_isBreakable = false;
>         m_isCollapsed = false;
>     }
> 
> > Source/WebCore/rendering/SimpleLineLayoutFlowContentsIterator.h:138
> > +    newFragment.m_start = splitPosition;
> > +    newFragment.m_width = flowContentsIterator.textWidth(newFragment.start(), newFragment.end(), 0);
> > +    single = newFragment.start() + 1 == newFragment.end();
> > +    newFragment.m_isBreakable = single ? false : newFragment.m_isBreakable;
> > +    newFragment.m_isCollapsed = single ? false : newFragment.m_isCollapsed;
> 
> Since this code is identical to what’s above, how about a helper function to
> avoid repeating the code twice?
Fixed.

[zalan]

(In reply to comment #8)
> Comment on attachment 245887 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=245887&action=review
> 
> > Source/WebCore/rendering/SimpleLineLayout.cpp:304
> > +typedef struct {
> > +    unsigned start { 0 };
> > +    unsigned end { 0 };
> > +} WidthRange;
> > +class FragmentWidthIterator : public std::iterator<std::forward_iterator_tag, WidthRange> {
> 
> This could be just struct WidthRange {} instead of a typedef.
> 
> Missing empty line after.
Done.

> 
> > Source/WebCore/rendering/SimpleLineLayout.cpp:336
> > +    FragmentWidthIterator& operator--()
> > +    {
> > +        --m_fragmentIndex;
> > +        return *this;
> > +    }
> > +
> > +    FragmentWidthIterator operator--(int)
> > +    {
> > +        FragmentWidthIterator result(*this);
> > +        --*this;
> > +        return result;
> > +    }
> 
> This is marked as a forward iterator. Why does it have operator--?
It's just leftover from my attempts with std::distance. Thanks for spotting this. Fixed.

[zalan]

Created attachment 245896 [details]
Patch

[zalan]

Created attachment 245900 [details]
Patch

[WebKit Commit Bot]

Comment on attachment 245900 [details]
Patch

Clearing flags on attachment: 245900

Committed r179510: <http://trac.webkit.org/changeset/179510>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.