Bug 137374 – Support insert iterators for Vectors. [Part 1]

• Status: NEW
• Component: New Bugs

[Jer Noble]

Support insert iterators for Vectors.

[Jer Noble]

Created attachment 239176 [details]
Patch

[WebKit Commit Bot]

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


ERROR: Source/WTF/wtf/VectorIterators.h:40:  difference_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/VectorIterators.h:43:  iterator_category is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/VectorIterators.h:74:  difference_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/VectorIterators.h:77:  iterator_category is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
Total errors found: 4 in 3 files


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

[Daniel Bates]

Comment on attachment 239176 [details]
Patch

We should add unit tests for this functionality. You can see examples of unit tests in Tools/TestWebKitAPI/Tests. In particular, we have WTF-specific unit tests in Tools/TestWebKitAPI/Tests/WTF.

[Jer Noble]

Created attachment 239213 [details]
Patch

[Jer Noble]

(In reply to comment #3)
> (From update of attachment 239176 [details])
> We should add unit tests for this functionality. You can see examples of unit tests in Tools/TestWebKitAPI/Tests. In particular, we have WTF-specific unit tests in Tools/TestWebKitAPI/Tests/WTF.

Oh I wrote them; but somehow managed to upload a patch without them. :-/

[Daniel Bates]

We need to add file VectorIterators.h to the Windows and CMake build systems.

[WebKit Commit Bot]

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


ERROR: Source/WTF/wtf/VectorIterators.h:40:  difference_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/VectorIterators.h:43:  iterator_category is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/VectorIterators.h:74:  difference_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/VectorIterators.h:77:  iterator_category is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
Total errors found: 4 in 5 files


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

[Jer Noble]

Created attachment 239214 [details]
Patch

[Anders Carlsson]

Why can't we use std::back_insert_iterator? 

http://en.cppreference.com/w/cpp/iterator/back_insert_iterator

[WebKit Commit Bot]

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


ERROR: Source/WTF/wtf/VectorIterators.h:40:  difference_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/VectorIterators.h:43:  iterator_category is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/VectorIterators.h:74:  difference_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/VectorIterators.h:77:  iterator_category is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
Total errors found: 4 in 5 files


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

[Jer Noble]

Created attachment 239215 [details]
Patch

[WebKit Commit Bot]

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


ERROR: Source/WTF/wtf/VectorIterators.h:40:  difference_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/VectorIterators.h:43:  iterator_category is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/VectorIterators.h:74:  difference_type is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
ERROR: Source/WTF/wtf/VectorIterators.h:77:  iterator_category is incorrectly named. Don't use underscores in your identifier names.  [readability/naming/underscores] [4]
Total errors found: 4 in 7 files


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

[Jer Noble]

(In reply to comment #9)
> Why can't we use std::back_insert_iterator? 
> 
> http://en.cppreference.com/w/cpp/iterator/back_insert_iterator

Because Vector doesn't have a push_back().  Its iterator types also don't have the std standard typedefs, like value_type, etc.

[Anders Carlsson]

(In reply to comment #13)
> (In reply to comment #9)
> > Why can't we use std::back_insert_iterator? 
> > 
> > http://en.cppreference.com/w/cpp/iterator/back_insert_iterator
> 
> Because Vector doesn't have a push_back().  Its iterator types also don't have the std standard typedefs, like value_type, etc.

I think it's much better to make our containers play well with the STL than it is to replicate STL functionality. (Our transition from OwnPtr to std::unique_ptr is an example of this).

[Darin Adler]

(In reply to comment #14)
> (In reply to comment #13)
> > (In reply to comment #9)
> > > Why can't we use std::back_insert_iterator? 
> > > 
> > > http://en.cppreference.com/w/cpp/iterator/back_insert_iterator
> > 
> > Because Vector doesn't have a push_back().  Its iterator types also don't have the std standard typedefs, like value_type, etc.
> 
> I think it's much better to make our containers play well with the STL than it is to replicate STL functionality. (Our transition from OwnPtr to std::unique_ptr is an example of this).

I’m with Anders on this. Seems like a natural refinement to improve the Vector iterators, add push_back, and then use back_insert_iterator.

[Jer Noble]

(In reply to comment #15)
> (In reply to comment #14)
> > (In reply to comment #13)
> > > (In reply to comment #9)
> > > > Why can't we use std::back_insert_iterator? 
> > > > 
> > > > http://en.cppreference.com/w/cpp/iterator/back_insert_iterator
> > > 
> > > Because Vector doesn't have a push_back().  Its iterator types also don't have the std standard typedefs, like value_type, etc.
> > 
> > I think it's much better to make our containers play well with the STL than it is to replicate STL functionality. (Our transition from OwnPtr to std::unique_ptr is an example of this).
> 
> I’m with Anders on this. Seems like a natural refinement to improve the Vector iterators, add push_back, and then use back_insert_iterator.

Okay, that's fine.  And back_insert_iterator was actually my primary use-case anyway.

But for insert_iterator, the default STL implementation won't work, as Vector invalidates all outstanding iterators when it does a re-alloc.  The version I posted here works around this by resetting the internal iterator in that scenario, so it may still be useful as a template specification version of std::insert_Iterator.

[Darin Adler]

(In reply to comment #16)
> But for insert_iterator, the default STL implementation won't work, as Vector invalidates all outstanding iterators when it does a re-alloc.

How does insert_iterator work with std::vector? If the answer is that it doesn’t then we should consider whether we have a good reason that we want WTF::Vector to work with it.

[Jer Noble]

(In reply to comment #17)
> (In reply to comment #16)
> > But for insert_iterator, the default STL implementation won't work, as Vector invalidates all outstanding iterators when it does a re-alloc.
> 
> How does insert_iterator work with std::vector? If the answer is that it doesn’t then we should consider whether we have a good reason that we want WTF::Vector to work with it.

std::vector has the same problem, in that all iterators are invalidated in the event of a re-alloc. The way you'd make a insert_iterator work with std::vector is the same as with WTF::Vector: by increasing the container's capacity with reserve()/reserveCapacity() before the insert operations.

[Jer Noble]

Created attachment 239267 [details]
Patch

Trying the alternative approach of making Vector compatible with back_insert_iterator and insert_iterator. This requires Vector to have an insert(iterator, value) method, which causes compile-time errors due to an ambiguity between insert(iterator, value) and insert(size_t, value) when passing in a literal (e.g., 0). So Part 1 is to rename insert(size_t, value) to insertAt(size_t, value), and Part 2 will be adding a new insert(iterator, value) method.

[Brent Fulgham]

Was this abandoned? Should we be getting it up-to-date and landed?

[Michael Catanzaro]

Comment on attachment 239267 [details]
Patch

Hi,

Apologies that your patch was not reviewed in a timely manner. Since it's now quite old, I am removing it from the review request queue. Please consider rebasing it on trunk and resubmitting.

To increase the chances of getting a review, consider using 'Tools/Scripts/webkit-patch upload --suggest-reviewers' to CC reviewers who might be interested in this bug.