Bug 141143 – Add Vector::erase() for iterator-based removals

• Status: RESOLVED
• Resolution: WONTFIX
• Component: Web Template Framework

[Chris Dumez]

Add Vector::erase() for iterator-based removals. Currently, we only have Vector::remove() but it is index-based. Adding support for iterator-based removal makes our Vector container more convenient to use with STL (e.g. std::find(), std::find_if(), std::remove(), std::remove_if(), ...). Using STL algorithm usually results in less error-prone and shorter code.

[Chris Dumez]

Created attachment 245842 [details]
Patch

[Build Bot]

Comment on attachment 245842 [details]
Patch

Attachment 245842 [details] did not pass mac-wk2-ews (mac-wk2):
Output: http://webkit-queues.appspot.com/results/6754301766533120

New failing tests:
editing/execCommand/toggle-text-decorations.html

[Build Bot]

Created attachment 245845 [details]
Archive of layout-test-results from ews105 for mac-mavericks-wk2

The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: ews105  Port: mac-mavericks-wk2  Platform: Mac OS X 10.9.5

[Build Bot]

Comment on attachment 245842 [details]
Patch

Attachment 245842 [details] did not pass mac-ews (mac):
Output: http://webkit-queues.appspot.com/results/4607670669541376

New failing tests:
editing/execCommand/toggle-text-decorations.html

[Build Bot]

Created attachment 245846 [details]
Archive of layout-test-results from ews102 for mac-mavericks

The attached test failures were seen while running run-webkit-tests on the mac-ews.
Bot: ews102  Port: mac-mavericks  Platform: Mac OS X 10.9.5

[Chris Dumez]

Created attachment 245847 [details]
Patch

[Alexey Proskuryakov]

> editing/execCommand/toggle-text-decorations.html

It's crazy that a mistake like that was only caught by a single editing test! This makes me wish to stop everything and only work on unskipping skipped tests.

[Chris Dumez]

(In reply to comment #7)
> > editing/execCommand/toggle-text-decorations.html
> 
> It's crazy that a mistake like that was only caught by a single editing
> test! This makes me wish to stop everything and only work on unskipping
> skipped tests.

Yes, CSSValueList::removeAll() isn't used much, only in editing code. As a matter of fact, if it were, we would probably have noticed that it currently fails to remove consecutive matching value (because it fails to decrement index after calling remove()).

[Darin Adler]

Comment on attachment 245847 [details]
Patch

Why is this named erase? We have the same operation in HashSet and HashMap and it’s called remove, overloaded for both values and iterators. Why wouldn’t we overload remove here for both indexes and iterators?

[Chris Dumez]

(In reply to comment #9)
> Comment on attachment 245847 [details]
> Patch
> 
> Why is this named erase? We have the same operation in HashSet and HashMap
> and it’s called remove, overloaded for both values and iterators. Why
> wouldn’t we overload remove here for both indexes and iterators?

Oh I tried but remove(0) was ambiguous and it wouldn't build. the vector iterator is a raw pointer and 0 could be a null pointer or index 0.

[Darin Adler]

Comment on attachment 245847 [details]
Patch

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

In many of these cases I find the new code harder to read than the old code and not significantly shorter. I’m not sure the way we are using the erase function is an improvement.

> Source/WTF/ChangeLog:18
> +        * wtf/Ref.h:
> +        (WTF::Ref::operator=):
> +        Support assignment to a Ref that has previously been moved. This is
> +        necessary for std::remove() to work on Vectors of Ref<>.

Is Kling OK with this change?

> Source/JavaScriptCore/inspector/InspectorValues.cpp:791
> -    for (size_t i = 0; i < m_order.size(); ++i) {
> -        if (m_order[i] == name) {
> -            m_order.remove(i);
> -            break;
> -        }
> -    }
> +    auto it = std::find(m_order.begin(), m_order.end(), name);
> +    if (it != m_order.end())
> +        m_order.erase(it);

Doesn’t seem like the new code is much better than the old. Why didn’t the old code just use Vector::find?

> Source/JavaScriptCore/profiler/ProfileNode.cpp:80
> -    for (size_t i = 0; i < m_children.size(); ++i) {
> -        if (*node == m_children[i].get()) {
> -            m_children.remove(i);
> -            break;
> -        }
> -    }
> +    auto it = std::find(m_children.begin(), m_children.end(), node);
> +    if (it != m_children.end())
> +        m_children.erase(it);

Doesn’t seem like the new code is much better than the old. Why didn’t the old code just use Vector::find?

> Source/WTF/wtf/Vector.h:1312
> +    asanBufferSizeWillChangeTo(m_size - 1);
> +    --m_size;

No reason to call the asanBufferSizeWillChangeTo before the --m_size rather than calling it after. And after, we could just pass m_size.

> Source/WTF/wtf/Vector.h:1326
>      asanBufferSizeWillChangeTo(m_size - length);
>      m_size -= length;

No reason to call the asanBufferSizeWillChangeTo before the m_size -= length rather than calling it after. And after, we could just pass m_size.

> Source/WebCore/accessibility/AccessibilityScrollView.cpp:142
> -    size_t pos = m_children.find(scrollbar);
> -    if (pos != WTF::notFound) {
> -        m_children[pos]->detachFromParent();
> -        m_children.remove(pos);
> -    }
> +    auto it = std::find(m_children.begin(), m_children.end(), scrollbar);
> +    if (it == m_children.end())
> +        return;
> +    (*it)->detachFromParent();
> +    m_children.erase(it);

Why is this new code better than the old?

[Darin Adler]

I guess the std::remove_if ones are considerably better than deleting as we go, but even on those I would rather we wrote something to make the idiom more readable. I find the erase(remove_if(begin, end, lambda), end) to be really oblique and there’s no reason we couldn’t make a helper that takes a lambda that is more directly understandable.

[Anders Carlsson]

(In reply to comment #11)
> Comment on attachment 245847 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=245847&action=review
> 
> In many of these cases I find the new code harder to read than the old code
> and not significantly shorter. I’m not sure the way we are using the erase
> function is an improvement.
> 
> > Source/WTF/ChangeLog:18
> > +        * wtf/Ref.h:
> > +        (WTF::Ref::operator=):
> > +        Support assignment to a Ref that has previously been moved. This is
> > +        necessary for std::remove() to work on Vectors of Ref<>.
> 
> Is Kling OK with this change?

I'll let Kling speak for himself, but I think it's unfortunate that we have to make Ref even more complex. I think having objects go from invalid to valid is going to mess with the -Wconsumed warning as well.

[Chris Dumez]

(In reply to comment #11)
> Comment on attachment 245847 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=245847&action=review
> 
> In many of these cases I find the new code harder to read than the old code
> and not significantly shorter. I’m not sure the way we are using the erase
> function is an improvement.
> 
> > Source/WTF/ChangeLog:18
> > +        * wtf/Ref.h:
> > +        (WTF::Ref::operator=):
> > +        Support assignment to a Ref that has previously been moved. This is
> > +        necessary for std::remove() to work on Vectors of Ref<>.
> 
> Is Kling OK with this change?
> 
> > Source/JavaScriptCore/inspector/InspectorValues.cpp:791
> > -    for (size_t i = 0; i < m_order.size(); ++i) {
> > -        if (m_order[i] == name) {
> > -            m_order.remove(i);
> > -            break;
> > -        }
> > -    }
> > +    auto it = std::find(m_order.begin(), m_order.end(), name);
> > +    if (it != m_order.end())
> > +        m_order.erase(it);
> 
> Doesn’t seem like the new code is much better than the old. Why didn’t the
> old code just use Vector::find?
> 
> > Source/JavaScriptCore/profiler/ProfileNode.cpp:80
> > -    for (size_t i = 0; i < m_children.size(); ++i) {
> > -        if (*node == m_children[i].get()) {
> > -            m_children.remove(i);
> > -            break;
> > -        }
> > -    }
> > +    auto it = std::find(m_children.begin(), m_children.end(), node);
> > +    if (it != m_children.end())
> > +        m_children.erase(it);
> 
> Doesn’t seem like the new code is much better than the old. Why didn’t the
> old code just use Vector::find?
> 
> > Source/WTF/wtf/Vector.h:1312
> > +    asanBufferSizeWillChangeTo(m_size - 1);
> > +    --m_size;
> 
> No reason to call the asanBufferSizeWillChangeTo before the --m_size rather
> than calling it after. And after, we could just pass m_size.
> 
> > Source/WTF/wtf/Vector.h:1326
> >      asanBufferSizeWillChangeTo(m_size - length);
> >      m_size -= length;
> 
> No reason to call the asanBufferSizeWillChangeTo before the m_size -= length
> rather than calling it after. And after, we could just pass m_size.
> 
> > Source/WebCore/accessibility/AccessibilityScrollView.cpp:142
> > -    size_t pos = m_children.find(scrollbar);
> > -    if (pos != WTF::notFound) {
> > -        m_children[pos]->detachFromParent();
> > -        m_children.remove(pos);
> > -    }
> > +    auto it = std::find(m_children.begin(), m_children.end(), scrollbar);
> > +    if (it == m_children.end())
> > +        return;
> > +    (*it)->detachFromParent();
> > +    m_children.erase(it);
> 
> Why is this new code better than the old?

You are right that in some cases, using std::find() + Vector::erase() is not necessarily much better than before, just different. My longer term thinking was that we could drop Vector::find() and use std::find() everywhere. Vector::find() is not any more efficient that std::find() AFAIK so I am not convinced it provides much value. I guess there is the readability aspect that you mentioned as you don't have to specify begin / end iterators. If we care more about this than using STL more, then I guess we could add removeAll(value) / removeIf(lambda) methods to simplify call sites at least.

[Andreas Kling]

(In reply to comment #13)
> (In reply to comment #11)
> > Comment on attachment 245847 [details]
> > Patch
> > 
> > View in context:
> > https://bugs.webkit.org/attachment.cgi?id=245847&action=review
> > 
> > In many of these cases I find the new code harder to read than the old code
> > and not significantly shorter. I’m not sure the way we are using the erase
> > function is an improvement.
> > 
> > > Source/WTF/ChangeLog:18
> > > +        * wtf/Ref.h:
> > > +        (WTF::Ref::operator=):
> > > +        Support assignment to a Ref that has previously been moved. This is
> > > +        necessary for std::remove() to work on Vectors of Ref<>.
> > 
> > Is Kling OK with this change?
> 
> I'll let Kling speak for himself, but I think it's unfortunate that we have
> to make Ref even more complex. I think having objects go from invalid to
> valid is going to mess with the -Wconsumed warning as well.

Conditionally agreed. Unless we can transfer the "consumed" state from the Ref we are assigning from, this is going to be very confusing.

[Chris Dumez]

I would also like to note that even though the STL algorithm functions taking iterators makes them a bit more verbose, it is also a bit more flexible as you can do operations on only part of your container.

[Chris Dumez]

Ben is telling me that if we were to implement removeAll(lambda) / removeAll(value) ourselves in Vector, we could probably provide a more efficient implementation than Vector::erase() + std::remove() / std::removeAll() as we would be able to use VectorMover and use memcpy/memmove instead of WTF::move() for some types. If so, I think this is a good reason to provide our own implementation on Vector here instead of using std <algorithm> (in addition to the code readability reason).

[Chris Dumez]

Comment on attachment 245847 [details]
Patch

Based on feedback, I'll propose new removeOne() / removeAll() on Vector instead.