Bug 138821 – Make sure range based iteration of Vector<> still receives bounds checking

• Status: REOPENED
• Component: Web Template Framework

[Oliver Hunt]

Make sure range based iteration of Vector<> still receives bounds checking

[Oliver Hunt]

Created attachment 241762 [details]
Patch

[WebKit Commit Bot]

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


ERROR: Source/WTF/wtf/IndexedIterator.h:40:  difference_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:41:  value_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:44:  iterator_category is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
Total errors found: 3 in 27 files


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

[Oliver Hunt]

Created attachment 241862 [details]
Patch

[Oliver Hunt]

Created attachment 241869 [details]
Patch

[WebKit Commit Bot]

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


ERROR: Source/WTF/wtf/IndexedIterator.h:40:  difference_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:41:  value_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:44:  iterator_category is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
Total errors found: 3 in 27 files


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

[Chris Dumez]

Comment on attachment 241869 [details]
Patch

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

> Source/WTF/wtf/IndexedIterator.h:32
> +    if (!(check))\

Doesn't this impact performance?

[Oliver Hunt]

Comment on attachment 241869 [details]
Patch

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

>> Source/WTF/wtf/IndexedIterator.h:32
>> +    if (!(check))\
> 
> Doesn't this impact performance?

This has already passed all the performance tests (JSC, PLT, Speeddoohicky, ...)

[Oliver Hunt]

Created attachment 241906 [details]
Patch

[WebKit Commit Bot]

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


ERROR: Source/WTF/wtf/IndexedIterator.h:40:  difference_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:41:  value_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:44:  iterator_category is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
Total errors found: 3 in 28 files


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

[Oliver Hunt]

Created attachment 241954 [details]
trying to fix efl, gtk, and msvc

[WebKit Commit Bot]

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


ERROR: Source/WTF/wtf/IndexedIterator.h:40:  difference_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:41:  value_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:44:  iterator_category is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
Total errors found: 3 in 29 files


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

[Oliver Hunt]

Created attachment 241958 [details]
more efl fixes

[WebKit Commit Bot]

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


ERROR: Source/WTF/wtf/IndexedIterator.h:40:  difference_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:41:  value_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:44:  iterator_category is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
Total errors found: 3 in 29 files


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

[Oliver Hunt]

Created attachment 241959 [details]
Patch

[WebKit Commit Bot]

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


ERROR: Source/WTF/wtf/IndexedIterator.h:40:  difference_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:41:  value_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:44:  iterator_category is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
Total errors found: 3 in 29 files


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

[Oliver Hunt]

Performance is good, etc, etc

[Oliver Hunt]

Created attachment 241999 [details]
sigh, another attempt to fix GIFDecoder

[WebKit Commit Bot]

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


ERROR: Source/WTF/wtf/IndexedIterator.h:40:  difference_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:41:  value_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:44:  iterator_category is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
Total errors found: 3 in 29 files


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

[Mark Lam]

Comment on attachment 241999 [details]
sigh, another attempt to fix GIFDecoder

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

> Source/JavaScriptCore/profiler/ProfileNode.cpp:157
> +

Please remove.

> Source/WTF/WTF.xcodeproj/project.pbxproj:101
> +		A7DC2F041A09A22D0072F4E3 /* IndexedIterator.h in Headers */ = {isa = PBXBuildFile; fileRef = A7DC2F031A099DE30072F4E3 /* IndexedIterator.h */; };

You’ll need to add the new header to WTF.vcxproj and WTF.vcxproj.filters as well.

> Source/WTF/wtf/IndexedIterator.h:33
> +    if (!(check))\
> +        OverflowHandler::overflowed();\

nit: indentation is funny here.  Can you indent these 2 lines 1 more level so that it is not at the same level as the while(0) below?

> Source/WTF/wtf/IndexedIterator.h:111
> +        if (increment < 0) {
> +            INDEXED_ITERATOR_OVERFLOW(increment != std::numeric_limits<int32_t>::max());

if increment < 0, then it can never == std::numeric_limits<int32_t>::max().  Hence, this check will always pass.  The goal is so that when we do the negation below, we don’t overflow, right?  So, instead, I think you actually meant to check:
    INDEXED_ITERATOR_OVERFLOW(increment > std::numeric_limits<int32_t>::min());

> Source/WTF/wtf/IndexedIterator.h:123
> +            INDEXED_ITERATOR_OVERFLOW(decrement != std::numeric_limits<int32_t>::max());

Ditto.  I think you actually meant to check:
    INDEXED_ITERATOR_OVERFLOW(decrement > std::numeric_limits<int32_t>::min());

> Source/WTF/wtf/IndexedIterator.h:150
> +            INDEXED_ITERATOR_OVERFLOW(increment != std::numeric_limits<int32_t>::max());

Ditto.  Should be:
    INDEXED_ITERATOR_OVERFLOW(increment > std::numeric_limits<int32_t>::min());

> Source/WTF/wtf/IndexedIterator.h:162
> +            INDEXED_ITERATOR_OVERFLOW(decrement != std::numeric_limits<int32_t>::max());

Ditto.  Should be:
    INDEXED_ITERATOR_OVERFLOW(decrement > std::numeric_limits<int32_t>::min());

> Source/WTF/wtf/IndexedIterator.h:209
> +        return result += static_cast<size_t>(increment);

You’re casting a signed long long increment into an unsigned size_t.  Is this correct and safe?  I’m thinking of a 32-bit platform where size_t is smaller than long long.

> Source/WTF/wtf/IndexedIterator.h:215
> +        return result += static_cast<size_t>(decrement);

Ditto.  Signed long long to potentially smaller size_t conversion.

> Source/WTF/wtf/IndexedIterator.h:235
> +        return result += static_cast<size_t>(increment);

Here, we’re casting a signed long into an unsigned size_t.  Is this correct and safe?

> Source/WTF/wtf/IndexedIterator.h:241
> +        return result += static_cast<size_t>(decrement);

Ditto.  Signed long to unsigned size_t conversion.

[Oliver Hunt]

Comment on attachment 241999 [details]
sigh, another attempt to fix GIFDecoder

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

>> Source/WTF/wtf/IndexedIterator.h:33
>> +        OverflowHandler::overflowed();\
> 
> nit: indentation is funny here.  Can you indent these 2 lines 1 more level so that it is not at the same level as the while(0) below?

fighting Xcode auto indent, fixed

>> Source/WTF/wtf/IndexedIterator.h:111
>> +            INDEXED_ITERATOR_OVERFLOW(increment != std::numeric_limits<int32_t>::max());
> 
> if increment < 0, then it can never == std::numeric_limits<int32_t>::max().  Hence, this check will always pass.  The goal is so that when we do the negation below, we don’t overflow, right?  So, instead, I think you actually meant to check:
>     INDEXED_ITERATOR_OVERFLOW(increment > std::numeric_limits<int32_t>::min());

Aieeeee, good catch.

[Oliver Hunt]

Created attachment 242077 [details]
Patch

[WebKit Commit Bot]

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


ERROR: Source/WTF/wtf/IndexedIterator.h:40:  difference_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:41:  value_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:44:  iterator_category is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
Total errors found: 3 in 30 files


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

[Oliver Hunt]

Created attachment 242087 [details]
Patch

[WebKit Commit Bot]

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


ERROR: Source/WTF/wtf/IndexedIterator.h:40:  difference_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:41:  value_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:44:  iterator_category is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
Total errors found: 3 in 30 files


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

[Mark Lam]

Comment on attachment 242087 [details]
Patch

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

> Source/WTF/wtf/IndexedIterator.h:225
> +        return result += static_cast<unsigned long long>(decrement);

This should be:
    return result -= static_cast<unsigned long long>(decrement);

> Source/WTF/wtf/IndexedIterator.h:247
> +            return result + static_cast<size_t>(-increment);

This should be:
    return result - static_cast<size_t>(-increment);

> Source/WTF/wtf/IndexedIterator.h:259
> +        return result += static_cast<size_t>(decrement);

This should be:
    return result -= static_cast<size_t>(decrement);

[Oliver Hunt]

Created attachment 242275 [details]
sigh, webkit-patch was waiting for me to say yes before uploading...

[WebKit Commit Bot]

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


ERROR: Source/WTF/wtf/IndexedIterator.h:40:  difference_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:41:  value_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:44:  iterator_category is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
Total errors found: 3 in 30 files


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

[Mark Lam]

Comment on attachment 242275 [details]
sigh, webkit-patch was waiting for me to say yes before uploading...

r=me

[Oliver Hunt]

Committed r176592: <http://trac.webkit.org/changeset/176592>

[Csaba Osztrogonác]

(In reply to comment #29)
> Committed r176592: <http://trac.webkit.org/changeset/176592>

It broke Apple's 32 bit build: https://build.webkit.org/builders/Apple%20MountainLion%20Release%20%2832-bit%20Build%29/builds/17559

[Oliver Hunt]

(In reply to comment #30)
> (In reply to comment #29)
> > Committed r176592: <http://trac.webkit.org/changeset/176592>
> 
> It broke Apple's 32 bit build:
> https://build.webkit.org/builders/Apple%20MountainLion%20Release%20%2832-
> bit%20Build%29/builds/17559

goddammit. Looking into it.

[Csaba Osztrogonác]

(In reply to comment #31)
> (In reply to comment #30)
> > (In reply to comment #29)
> > > Committed r176592: <http://trac.webkit.org/changeset/176592>
> > 
> > It broke Apple's 32 bit build:
> > https://build.webkit.org/builders/Apple%20MountainLion%20Release%20%2832-
> > bit%20Build%29/builds/17559
> 
> goddammit. Looking into it.

The fix https://trac.webkit.org/changeset/176603 broke non Apple builds:
- EFL ARM Thumb2: https://build.webkit.org/builders/EFL%20Linux%20ARMv7%20Thumb2%20Release%20%28Build%29/builds/8754
- EFL ARM: https://build.webkit.org/builders/EFL%20Linux%20ARMv7%20Traditional%20Release%20%28Build%29/builds/8607
- GTK x86: https://build.webkit.org/builders/GTK%20Linux%2032-bit%20Release/builds/48526

[Carlos Alberto Lopez Perez]

(In reply to comment #32)
> The fix https://trac.webkit.org/changeset/176603 broke non Apple builds:
> - EFL ARM Thumb2:
> https://build.webkit.org/builders/
> EFL%20Linux%20ARMv7%20Thumb2%20Release%20%28Build%29/builds/8754
> - EFL ARM:
> https://build.webkit.org/builders/
> EFL%20Linux%20ARMv7%20Traditional%20Release%20%28Build%29/builds/8607
> - GTK x86:
> https://build.webkit.org/builders/GTK%20Linux%2032-bit%20Release/builds/48526

It broke also GTK ARM bot: https://build.webkit.org/builders/GTK%20Linux%2032-bit%20Release/builds/48526

I think the issue is incorrectly assuming that !WIN==MAC|IOS.

What about this fix? (I didn't tested it)

--- a/Source/WTF/wtf/IndexedIterator.h
+++ b/Source/WTF/wtf/IndexedIterator.h
@@ -225,7 +225,7 @@ template <typename VectorType, typename T, typename OverflowHandler = CrashOnOve
         return result -= static_cast<unsigned long long>(decrement);
     }
 
-#if __SIZEOF_SIZE_T__ != __SIZEOF_INT__ || !PLATFORM(WIN)
+#if __SIZEOF_SIZE_T__ != __SIZEOF_INT__ || (PLATFORM(COCOA) && !PLATFORM(WIN))
     IndexedIterator operator+(unsigned increment) const
     {
         IndexedIterator result(*this);

[Carlos Alberto Lopez Perez]

Fixed by: https://trac.webkit.org/changeset/176616

[Chris Dumez]

Looks like we took a 1-1.5% hit on Speedometer:
https://perf.webkit.org/#mode=charts&chartList=%5B%5B%22gtk%22%2C%22DoYouEvenBench%2FFull%3ATime%3ATotal%22%5D%5D
https://perf.webkit.org/#mode=charts&chartList=%5B%5B%22mac-mavericks%22%2C%22DoYouEvenBench%2FFull%3ATime%3ATotal%22%5D%5D

And a 1.7% hit on HTML5 Full Render:
https://perf.webkit.org/#mode=charts&chartList=%5B%5B%22efl%22%2C%22Parser%2Fhtml5-full-render%3ATime%22%5D%5D

This change is the only commit in the Range so I am fairly confident this caused the regression.

[Oliver Hunt]

ok, this is weird as stephanie had perf checked it before - i'll see if i can get her to re-test the final commit.  I didn't think that there had been any changes that would impact perf, but maybe i was wrong?

[Mark Lam]

Rolled out r176592, r176603, r176616, and r176705 in 176709: <http://trac.webkit.org/r176709>.

[Oliver Hunt]

Created attachment 242506 [details]
Patch

[WebKit Commit Bot]

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


ERROR: Source/WTF/wtf/IndexedIterator.h:40:  difference_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:41:  value_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:44:  iterator_category is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
Total errors found: 3 in 30 files


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

[Oliver Hunt]

Created attachment 242511 [details]
Patch

[WebKit Commit Bot]

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


ERROR: Source/WTF/wtf/IndexedIterator.h:40:  difference_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:41:  value_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:44:  iterator_category is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
Total errors found: 3 in 30 files


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

[Mark Lam]

Comment on attachment 242511 [details]
Patch

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

It looks like the change you made is to allow the iterator value to be out of range.  However, when the iterator is actually used to access the element via get(), you to the overflow check then.  I understand that this is probably done for performance reasons.

Based on how the iterators work, it looks like you're allowing overflow and underflow when applying signed increments / decrements, as long as the end result is a legal index into the vector.  The result is that bad code that adds / subtracts a ridiculously large / negative delta can go undetected as long as the resultant index is within range.  I assume that this is intentional, and that we're willing to live with this limitation?

r=me with the blank line removed, assuming the above is the intended behavior you want.

> Source/WTF/wtf/IndexedIterator.h:150
> +

Extra line here which can be removed.

[Oliver Hunt]

Comment on attachment 242511 [details]
Patch

Yeah, basically we're now relying on the Vector's own bounds checking logic for more or less everything. This means we should remain memory safe even if you misuse the iterators. Still waiting on final perf numbers.

[Anders Carlsson]

If this is still a 1.5-1.7% performance regression I don't see how it can be landed.

[Oliver Hunt]

(In reply to comment #44)
> If this is still a 1.5-1.7% performance regression I don't see how it can be
> landed.

It should not be a regression anymore - it's dropped all the expensive checks. If it's not possible to fix this we need to stop use of the range syntax as every use of it is a security regression vs. the old indexed iteration.

[Mark Lam]

(In reply to comment #45)
> (In reply to comment #44)
> > If this is still a 1.5-1.7% performance regression I don't see how it can be
> > landed.
> 
> It should not be a regression anymore - it's dropped all the expensive
> checks. If it's not possible to fix this we need to stop use of the range
> syntax as every use of it is a security regression vs. the old indexed
> iteration.

Is this ready to land yet?  Did the perf test run pan out?

[Stephanie Lewis]

Patch passed all perf. tests and might even be a little faster.  Due to the unsigned vs. size_t discussion in Vector the patch no longer applies cleanly.

[Oliver Hunt]

Created attachment 243259 [details]
Patch

[WebKit Commit Bot]

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


ERROR: Source/WTF/wtf/IndexedIterator.h:40:  difference_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:41:  value_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:44:  iterator_category is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
Total errors found: 3 in 30 files


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

[Mark Lam]

Comment on attachment 243259 [details]
Patch

r=me

[WebKit Commit Bot]

Comment on attachment 243259 [details]
Patch

Clearing flags on attachment: 243259

Committed r177284: <http://trac.webkit.org/changeset/177284>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Geoffrey Garen]

Does this mean that any time you use .data() you go fast and any time you use .begin() you go slow?

How do you propose that authors go about choosing one or the other?

This strikes me as a dangerous and confusing booby trap to leave in the code.

[Oliver Hunt]

(In reply to comment #53)
> Does this mean that any time you use .data() you go fast and any time you
> use .begin() you go slow?
> 
> How do you propose that authors go about choosing one or the other?
> 
> This strikes me as a dangerous and confusing booby trap to leave in the code.

Seriously, there's no performance regression from this. The correct thing is to use begin()/end() if you want to iterate, and data() if you need to pass a pointer to some non-c++ API.

Stephanie's perf measuring says that if anything this improves performance.

[Geoffrey Garen]

> Seriously, there's no performance regression from this.

In that case, what changed between the first landed version of this patch and the second, which accounts for fixing the 1.7% performance regression?

[Oliver Hunt]

(In reply to comment #55)
> > Seriously, there's no performance regression from this.
> 
> In that case, what changed between the first landed version of this patch
> and the second, which accounts for fixing the 1.7% performance regression?

I removed a lot of the intermediate overflow checks, so it's not as brutal as it used to be. Most of the original performance regression occurred due to complications added when trying to convince all the various changes needed to appease MSVC

[WebKit Commit Bot]

Re-opened since this is blocked by bug 139658

[Andreas Kling]

I think this is about to get rolled out for breaking debug builds, but FWIW the single data point we got on perf.webkit.org's mac-mavericks builder saw a 0.85% regression on Speedometer and 1.96% on html5-full-render.html

[Oliver Hunt]

Created attachment 258044 [details]
Patch

[WebKit Commit Bot]

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


ERROR: Source/WTF/wtf/IndexedIterator.h:40:  difference_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:41:  value_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:44:  iterator_category is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
Total errors found: 3 in 26 files


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

[Oliver Hunt]

Throwing this at the bots because i'm too lazy to build myself :D

[Oliver Hunt]

Created attachment 260442 [details]
Patch

[Oliver Hunt]

Comment on attachment 260442 [details]
Patch

Not complete yet (aside from anything else i'm going to make it debug only at first)

[Oliver Hunt]

Created attachment 260450 [details]
Patch

[WebKit Commit Bot]

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


ERROR: Source/WTF/wtf/IndexedIterator.h:40:  difference_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:41:  value_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/IndexedIterator.h:44:  iterator_category is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
Total errors found: 3 in 28 files


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

[Darin Adler]

Comment on attachment 260450 [details]
Patch

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

Currently compiles only on iOS and Mac, so needs more work.

Performance testing results?

Should be using get() more and getPtr() much less (see below).

Vector uses pointers and iterators interchangeably in its implementation. I think this patch causes it to use the iterators too much instead of pointers.

We are now range checking approach too much. We have functions like Vector::remove that already have range checking with ASSERT_WITH_SECURITY_IMPLICATION, but then we are letting them be written in terms of these new checked iterators so they are checking twice. That’s sloppy. We can switch to the iterators and do lots of range checking and remove ASSERT_WITH_SECURITY_IMPLICATION, or we can decide to use pointers inside Vector’s own implementation. We need a principle about how to implement Vector itself that is separate from how code outside Vector uses iterators.

I like the idea of landing the changes that make this refactoring possible separately before changing Vector itself. Most changes that are outside Vector could be landed that way. (That’s one argument for using getPtr, since it would work both before and after, but I’d still prefer to keep that to a minimum so maybe hold off on the changes that actually require using get/getPtr explicitly.)

> Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.cpp:96
>      for (FunctionExpressionVector::iterator ptr = thisObject->m_functionDecls.begin(), end = thisObject->m_functionDecls.end(); ptr != end; ++ptr)
> -        visitor.append(ptr);
> +        visitor.append(WTF::getPtr(ptr));
>      for (FunctionExpressionVector::iterator ptr = thisObject->m_functionExprs.begin(), end = thisObject->m_functionExprs.end(); ptr != end; ++ptr)
> -        visitor.append(ptr);
> +        visitor.append(WTF::getPtr(ptr));

I think it would be nicer to rewrite these two loops to use modern C++ iteration, since we have to touch them.

    for (auto& expression : thisObject->m_functionDecls)
        visitor.append(&expression);
    for (auto& expression : thisObject->m_functionExprs)
        visitor.append(&expression);

> Source/WTF/wtf/IndexedIterator.h:2
> + * Copyright (C) 2014 Apple Inc. All rights reserved.

2014?

> Source/WTF/wtf/IndexedIterator.h:34
> +#define INDEXED_ITERATOR_OVERFLOW(check) do {\
> +    if (!(check))\
> +        OverflowHandler::overflowed();\
> +} while (0)

Seems unhelpful to use a macro for this; we only use the macro in one place.

> Source/WTF/wtf/IndexedIterator.h:36
> +template <typename VectorType, typename T, typename OverflowHandler = CrashOnOverflow> struct IndexedIterator {

This should be a class template, not a struct template. We use struct when we have public data members as the primary interface and in that case we do not use the "m_" prefix on the data members; in cases like this where we don’t, then we use class, not struct.

> Source/WTF/wtf/IndexedIterator.h:37
> +    typedef struct IndexedIterator<const VectorType, const T, OverflowHandler> const_iterator;

I don’t think const_iterator is a good name for this type. That’s a name used on collections to give the type for their const iterator. The IndexedIterator class is an iterator, not a collection. Using the same name is a bit clever but I think subtly confusing.

> Source/WTF/wtf/IndexedIterator.h:50
> +    IndexedIterator()
> +        : m_vector(nullptr)
> +        , m_position(0)
> +    {
> +    }

Newly written code should initialize data members where they are defined instead of listing them all in places like this. If we did that, then this would be more like this:

    IndexedIterator() -> default;

> Source/WTF/wtf/IndexedIterator.h:56
> +    IndexedIterator(std::nullptr_t)
> +        : m_vector(nullptr)
> +        , m_position(0)
> +    {
> +    }

And this would just be a function with an empty body, no need to specify m_vector and m_position.

> Source/WTF/wtf/IndexedIterator.h:58
> +    IndexedIterator(VectorType& vector, ValueType* position)

Since ValueType* must never be null, I suggest we let it be a reference even if it feels a little “pointer-y”.

> Source/WTF/wtf/IndexedIterator.h:68
> +    IndexedIterator(const IndexedIterator& other)
> +        : m_vector(other.m_vector)
> +        , m_position(other.m_position)
> +    {
> +    }

Should not declare this. This is what the compiler will generate as long as we don’t write it explicitly.

> Source/WTF/wtf/IndexedIterator.h:82
> +        m_position++;

Our idiom in WebKit code is to use pre-increment in places like this.

> Source/WTF/wtf/IndexedIterator.h:89
> +        m_position++;

Ditto.

> Source/WTF/wtf/IndexedIterator.h:95
> +        m_position--;

Ditto.

> Source/WTF/wtf/IndexedIterator.h:102
> +        m_position--;

Ditto.

> Source/WTF/wtf/IndexedIterator.h:108
> +    // This conversion operator allows implicit conversion to bool but not to other integer types.
> +    typedef size_t (IndexedIterator::*UnspecifiedBoolType);
> +    operator UnspecifiedBoolType() const { return m_vector ? &IndexedIterator::m_position : nullptr; }

This is not allowed or needed any more in more modern C++. Instead just write this:

    explicit operator bool const() { return m_vector; }

> Source/WTF/wtf/IndexedIterator.h:122
> +#if __SIZEOF_SIZE_T__ != __SIZEOF_INT__ || PLATFORM(COCOA)
> +#define _UNSIGNED_If_DIFFERENT(macro) macro(unsigned)
> +#else
> +#define _UNSIGNED_If_DIFFERENT(macro)
> +#endif
> +
> +#define FOR_EACH_INTEGER_TYPE(macro) \
> +    macro(size_t) \
> +    macro(int32_t) \
> +    macro(long) \
> +    macro(long long) \
> +    macro(unsigned long long) \
> +    _UNSIGNED_If_DIFFERENT(macro)

This is not the right approach. I suggest overloading for int, long, long long, unsigned, unsigned long, and unsigned long long. Don’t overload for size_t or int32_t. Then you won’t need this complex #if.

But also, you should ask Anders if there’s a cleaner way to achieve this.

> Source/WTF/wtf/IndexedIterator.h:169
> +    ptrdiff_t operator-(const const_iterator& right) const
> +    {
> +        return m_position - right.m_position;
> +    }
> +
> +    ptrdiff_t operator-(const ValueType* right) const
> +    {
> +        return get() - right;
> +    }

These should not be member functions; should just be non-member functions; friends if necessary.

> Source/WTF/wtf/IndexedIterator.h:175
> +    void operator=(const IndexedIterator& other)
> +    {
> +        m_vector = other.m_vector;
> +        m_position = other.m_position;
> +    }

Please omit this and let the compiler generate it. It will generate exactly this if you don’t write it out explicitly.

> Source/WTF/wtf/IndexedIterator.h:235
> +    bool operator==(const const_iterator& other) const
> +    {
> +        return unsafeGet() == other.unsafeGet();
> +    }
> +
> +    bool operator!=(const const_iterator& other) const
> +    {
> +        return unsafeGet() != other.unsafeGet();
> +    }
> +
> +    bool operator==(const ValueType* other) const
> +    {
> +        return unsafeGet() == other;
> +    }
> +
> +    bool operator!=(const ValueType* other) const
> +    {
> +        return unsafeGet() != other;
> +    }
> +
> +    bool operator<(const ValueType* other) const
> +    {
> +        return unsafeGet() < other;
> +    }
> +
> +    bool operator<=(const ValueType* other) const
> +    {
> +        return unsafeGet() <= other;
> +    }
> +
> +    bool operator<(const const_iterator& other) const
> +    {
> +        return unsafeGet() < other.unsafeGet();
> +    }
> +
> +    bool operator<=(const const_iterator& other) const
> +    {
> +        return unsafeGet() <= other.unsafeGet();
> +    }
> +
> +    bool operator>(const IndexedIterator& other) const
> +    {
> +        return unsafeGet() > other.unsafeGet();
> +    }
> +
> +    bool operator>=(const const_iterator& other) const
> +    {
> +        return unsafeGet() >= other.unsafeGet();
> +    }
> +
> +    bool operator>(const ValueType* other) const
> +    {
> +        return unsafeGet() > other;
> +    }
> +
> +    bool operator>=(const ValueType* other) const
> +    {
> +        return unsafeGet() >= other;
> +    }

These should not be member functions; should just be non-member functions; friends if necessary. Unclear why these need to do unsafe_get.

I believe it’s possibly inefficient to only define versions that compare with the const_iterator class. We might be creating and destroying temporaries unnecessarily unless the compiler does a great job optimizing.

> Source/WTF/wtf/IndexedIterator.h:243
> +    operator const_iterator() const
> +    {
> +        const_iterator result;
> +        result.m_vector = m_vector;
> +        result.m_position = m_position;
> +        return result;
> +    }

Surprised this compiles when const_iterator is the same type as this class’s type.

> Source/WTF/wtf/IndexedIterator.h:246
> +    VectorType* m_vector;
> +    size_t m_position;

VectorType* m_vector { nullptr };
    size_t m_position { 0 };

> Source/WTF/wtf/IndexedIterator.h:253
> +    ValueType* unsafeGet() const
> +    {
> +        if (!m_vector)
> +            return nullptr;
> +        return get();
> +    }

We don’t normally put functions after the data members. Please let the data members be last.

> Source/WTF/wtf/IndexedIterator.h:257
> +inline typename IndexedIterator<T, ValueType, OverflowHandler>::ValueType* getPtr(IndexedIterator<T, ValueType, OverflowHandler> p)

This should take const IndexedIterator&, not copy an IndexedIterator.

> Source/WTF/wtf/Vector.h:615
> +            TypeOperations::initialize(getPtr(begin()), getPtr(end()));

The getPtr function is only intended to be used in code that’s so generic that we can’t know whether it’s a class or a raw pointer. This code doesn’t qualify. Here we should write begin().get(). Or alternatively have private functions that return pointers for use inside the class? I don’t like the idea of doing the range checking unnecessarily inside the class so it seems bad to be calling get() here instead of unsafeGet().

> Source/WTF/wtf/Vector.h:624
> +            TypeOperations::uninitializedFill(getPtr(begin()), getPtr(end()), val);

Ditto.

> Source/WTF/wtf/Vector.h:693
> +    iterator begin() { return IteratorSelector::makeIterator(*this, data()); }

Why isn’t this just:

    return { *this, data() };

I don’t understand the need for IteratorSelector.

> Source/WTF/wtf/Vector.h:694
> +    iterator end() { return begin() + size(); }

Is this efficient enough? Would it be better to write:

    return { *this, data() + size(); }

> Source/WTF/wtf/Vector.h:695
> +    const_iterator begin() const { return IteratorSelector::makeConstIterator(*this, data()); }

Ditto.

> Source/WTF/wtf/Vector.h:696
> +    const_iterator end() const { return begin() + size(); }

Ditto.

> Source/WTF/wtf/Vector.h:737
> +    void append(const_iterator, size_t);

Not sure we want this. If we do want it, I think we’d want a template version that supports iterators from vectors with other element types too, just like all the other append functions.

> Source/WebCore/platform/graphics/cairo/GradientCairo.cpp:65
> -    Vector<ColorStop>::iterator stopIterator = m_stops.begin();
> +    auto stopIterator = m_stops.begin();
>      while (stopIterator != m_stops.end()) {

Better to use a modern for loop here.

> Source/WebCore/svg/SVGFontElement.cpp:246
> +        size_t it = kerningVector->size();

I don’t think “it” is a good name for an index.

> Source/WebCore/svg/SVGFontElement.cpp:248
> +            auto& value = kerningVector->at(it);

We normally prefer the [] syntax to the at() function.

> Source/WebCore/svg/SVGFontElement.cpp:257
> +            size_t it = kerningVector->size();

Ditto.

> Source/WebCore/svg/SVGFontElement.cpp:259
> +                auto& value = kerningVector->at(it);

Ditto.

> Source/WebCore/svg/SVGFontElement.cpp:266
> +            size_t it = kerningMap.kerningUnicodeRangeMap.size();

Ditto.