Bug 176487 – Add a lambda-based map for Vectors

• Component: WebCore Misc.
• Status: RESOLVED FIXED

[youenn fablet]

Add a lambda-based map for Vectors

[youenn fablet]

Created attachment 320081 [details]
Patch

[youenn fablet]

Created attachment 320128 [details]
Patch

[Saam Barati]

Comment on attachment 320128 [details]
Patch

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

> Source/WTF/wtf/Vector.h:1595
> +template<typename Transformer, typename VectorType>
> +Vector<typename Mapper<Transformer, VectorType>::DestinationItemType> map(VectorType&& source, const Transformer& transformer)
> +{
> +    return Mapper<Transformer, VectorType>::map(std::forward<VectorType>(source), transformer);
> +}

I'm slightly hesitant to assume here we're only going to map over Vector types. Can we come up with a way to do this so we can easily map over HashSet, HashMap, etc.

If other folks are interested in mapping over HashSet, HashMap, etc, one interesting question is, what's the return type? I'd assume map by default returns its input type, so map over HashSet returns a Vector. But I could sometimes see mapping a HashSet into a Vector. Maybe we can come up with a nice default, with the ability to override via templates?

[youenn fablet]

Discussing with Jer, there is already a Vector::map method taking a lambda.

It might be good to move it to a free function like done in this patch and maybe move it to some other place and try making it work for more than Vector.

Also, this patch is implementing map for both const Vector& and Vector&&.
In the latter case, the items are passed as && to the transformer.
Apparently, map is supposed to be const so maybe it is best to split these two patterns, or just not add the Vector&& as a pattern at all.

[youenn fablet]

Discussing with Jer, there is already a Vector::map method taking a lambda.

It might be good to move it to a free function like done in this patch and maybe move it to some other place and try making it work for more than Vector.

Also, this patch is implementing map for both const Vector& and Vector&&.
In the latter case, the items are passed as && to the transformer.
Apparently, map is supposed to be const so maybe it is best to split these two patterns, or just not add the Vector&& as a pattern at all.

[Darin Adler]

Comment on attachment 320128 [details]
Patch

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

> Source/WTF/wtf/Vector.h:1571
> +        for (const auto& item : source)

No need for the "const" here.

>> Source/WTF/wtf/Vector.h:1595
>> +}
> 
> I'm slightly hesitant to assume here we're only going to map over Vector types. Can we come up with a way to do this so we can easily map over HashSet, HashMap, etc.
> 
> If other folks are interested in mapping over HashSet, HashMap, etc, one interesting question is, what's the return type? I'd assume map by default returns its input type, so map over HashSet returns a Vector. But I could sometimes see mapping a HashSet into a Vector. Maybe we can come up with a nice default, with the ability to override via templates?

I think the first sentence here is attacking a straw man. This code doesn’t mean that we are mapping only over Vector types. In C++ we can use overloading to implement a function for more than one type. But perhaps the question is "how compatible would this be with other overloads". I don’t think we should force Youenn to make a more general purpose map function right now, but if there is some choice he is making here that will make it hard to implement the others in future, that might be nice.

My design suggestion would be that the WTF::map function produces the same type it is passed, but then there is map<T> which produces the type T for various cases where that is easy to support and unambiguous. I think we should approve this patch without undue worry about that more general map function for the future; I expect we can implement it later relatively easily or change all callers if we really have to.

> Source/WebKit/NetworkProcess/cache/CacheStorageEngineCaches.cpp:243
> +        callback(WTF::map(WTFMove(result.value()), [this](String&& name) {

I believe our coding style asks to put a space between [this] and (String&& name).

> Tools/TestWebKitAPI/Tests/WTF/Vector.cpp:656
> +    Vector<int> vector { 1, 1, 1};

I’m not sure we tested all the cases we should.

We tested how it behaves when we pass a Vector, and when we pass a Vector&&, using WTFMove. But we don’t explicitly test passing a Vector& (which I think should allow the lambda to modify the values during the mapping process, right, including allowing them to be explicitly moved, right, or maybe as a matter of policy we would choose to not allow that?) and passing an actual const Vector&. Some of these could really be relevant to how we implemented Mapper.

Also, should probably initialize the vector with different values rather than all with the same value.

> Tools/TestWebKitAPI/Tests/WTF/Vector.cpp:659
> +    auto mapped = WTF::map(vector, [&](const auto& item) {

Ditto.

> Tools/TestWebKitAPI/Tests/WTF/Vector.cpp:679
> +    auto mapped = WTF::map(WTFMove(vector), [&](MoveOnly&& item) {

Ditto.

[youenn fablet]

Thanks for the review.

> > I'm slightly hesitant to assume here we're only going to map over Vector types. Can we come up with a way to do this so we can easily map over HashSet, HashMap, etc.
> > 
> > If other folks are interested in mapping over HashSet, HashMap, etc, one interesting question is, what's the return type? I'd assume map by default returns its input type, so map over HashSet returns a Vector. But I could sometimes see mapping a HashSet into a Vector. Maybe we can come up with a nice default, with the ability to override via templates?
> 
> I think the first sentence here is attacking a straw man. This code doesn’t
> mean that we are mapping only over Vector types. In C++ we can use
> overloading to implement a function for more than one type. But perhaps the
> question is "how compatible would this be with other overloads". I don’t
> think we should force Youenn to make a more general purpose map function
> right now, but if there is some choice he is making here that will make it
> hard to implement the others in future, that might be nice.
> 
> My design suggestion would be that the WTF::map function produces the same
> type it is passed, but then there is map<T> which produces the type T for
> various cases where that is easy to support and unambiguous. I think we
> should approve this patch without undue worry about that more general map
> function for the future; I expect we can implement it later relatively
> easily or change all callers if we really have to.

Going from Map values or Map keys to a vector is a pattern that would be useful.
I guess this could be handled with a way to get iterator + size.

 
> > Source/WebKit/NetworkProcess/cache/CacheStorageEngineCaches.cpp:243
> > +        callback(WTF::map(WTFMove(result.value()), [this](String&& name) {
> 
> I believe our coding style asks to put a space between [this] and (String&&
> name).

OK.
I am not sure we have consistency in the code base here.

> > Tools/TestWebKitAPI/Tests/WTF/Vector.cpp:656
> > +    Vector<int> vector { 1, 1, 1};
> 
> I’m not sure we tested all the cases we should.
> 
> We tested how it behaves when we pass a Vector, and when we pass a Vector&&,
> using WTFMove. But we don’t explicitly test passing a Vector& (which I think
> should allow the lambda to modify the values during the mapping process,
> right, including allowing them to be explicitly moved, right, or maybe as a
> matter of policy we would choose to not allow that?) and passing an actual
> const Vector&. Some of these could really be relevant to how we implemented
> Mapper.

The target is to expose mapping for const Vector& and Vector&&.
A Vector& should be mapped as a const Vector&.
I haven't seen use case yet on wanting to move items from a Vector& inside the lambda and I am not sure this is a very comprehensible pattern.

> Also, should probably initialize the vector with different values rather
> than all with the same value.

OK

[youenn fablet]

Created attachment 320642 [details]
Patch for landing

[WebKit Commit Bot]

Comment on attachment 320642 [details]
Patch for landing

Clearing flags on attachment: 320642

Committed r221977: <http://trac.webkit.org/changeset/221977>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Radar WebKit Bug Importer]

<rdar://problem/34693618>