Bug 215879 – Add a variant of map which filters items to Vector.h

• Component: Web Template Framework
• Status: RESOLVED FIXED

[Ryosuke Niwa]

Add filteredMap which calls mapFunction on each item on an iterable object
and filters the result by the boolean operator.

[Ryosuke Niwa]

Created attachment 407376 [details]
Adds filteredMap

[youenn fablet]

Comment on attachment 407376 [details]
Adds filteredMap

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

> Source/WTF/wtf/Vector.h:1694
> +    static ItemType extractValue(Optional<T>& returnValue) { return *returnValue; }

It seems we might be using ItemType copy constructor.
Ideally, we would take an Optional<>&& as input and use ItemType move constructor.
Can we add a test with a filter function returning an Optional<Ref-Like-For-Test<...>> and verify there is no unnecessary count churning?

[Sam Weinig]

Comment on attachment 407376 [details]
Adds filteredMap

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

> Source/WTF/ChangeLog:11
> +        This patch adds WTF::filteredMap, which calls a function on each item in an iterable object like WTF::map
> +        but also filters the returned value. The mapped function may return Optional<T> or RefPtr<T>. The value
> +        is kept in the result if the returned value is not WTF::nullopt in the case of Optional<T> and not null
> +        in the case of RefPtr<T>. The result will be either Vector<T> for Optional<T> or else Vector<Ref<T>>.

I get that Optional<Ref<T>> is a bad thing to store in a class (since it will be 2 * sizeof(T*) rather than sizeof(T*)), but I think for something like this, where we are only using it as a return type, Optional<Ref<T>> might be nicer, and would require less special casing. 

Is there a particular use where having this special case for RefPtr is useful?

(as a side note, I think we should start thinking about what specializing Optional<Ref<T>> to be sizeof(T*) would mean. The most obvious thing it would mean is that we couldn't move to std::optional<>, but that seems contentious already).

[Darin Adler]

I agree with Sam’s comments and have some of the same thoughts and questions that he does.

I think we should look at optimizing Optional<Ref<T>> if we are willing to let the std::optional possibility go for good, and making Optional<Ref<T>> and RefPtr<T> much more interoperable. There’s already quite a bit, since the "*" operator works on both and if (x) works on both. But it would be nice to be able to use nullptr to mean WTF::nullopt in this case, and to support both move and copy assignment and conversion in both directions with syntax that’s as convenient as possible. There’s no need to be at all explicit about such conversions; they’re not lossy at all.

[Darin Adler]

Swift calls this operation compactMap. I like that name a bit better than filteredMap.

Could also consider reconciling terminology a bit between my makeNSArray, makeVector, map, and this new function. I don’t like how different those names are. Maybe we should rename makeNSArray and makeVector to compactMapToNSArray and compactMapToVector.

When programming in Swift I really enjoy map, filter, reduce, flatMap, and compactMap, and I think we might eventually find we want all 5 of them.

[Ryosuke Niwa]

(In reply to youenn fablet from comment #2)
> Comment on attachment 407376 [details]
> Adds filteredMap
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=407376&action=review
> 
> > Source/WTF/wtf/Vector.h:1694
> > +    static ItemType extractValue(Optional<T>& returnValue) { return *returnValue; }
> 
> It seems we might be using ItemType copy constructor.
> Ideally, we would take an Optional<>&& as input and use ItemType move
> constructor.

No. https://en.cppreference.com/w/cpp/language/copy_elision

(In reply to Sam Weinig from comment #3)
> Comment on attachment 407376 [details]
> Adds filteredMap
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=407376&action=review
> 
> > Source/WTF/ChangeLog:11
> > +        This patch adds WTF::filteredMap, which calls a function on each item in an iterable object like WTF::map
> > +        but also filters the returned value. The mapped function may return Optional<T> or RefPtr<T>. The value
> > +        is kept in the result if the returned value is not WTF::nullopt in the case of Optional<T> and not null
> > +        in the case of RefPtr<T>. The result will be either Vector<T> for Optional<T> or else Vector<Ref<T>>.
> 
> I get that Optional<Ref<T>> is a bad thing to store in a class (since it
> will be 2 * sizeof(T*) rather than sizeof(T*)), but I think for something
> like this, where we are only using it as a return type, Optional<Ref<T>>
> might be nicer, and would require less special casing. 
> 
> Is there a particular use where having this special case for RefPtr is
> useful?

The main use case is calling an existing function which returns RefPtr. It's annoying to write code like this:

filteredMap(~, Optional<Ref<X>> [] (auto& x) {
    auto result = foo(x);
    if (!result)
        return WTF::nullopt;
    return result.releaseNonNull();
});

(In reply to Darin Adler from comment #5)
> Swift calls this operation compactMap. I like that name a bit better than
> filteredMap.

Okay, we can call this compactMap.

[Ryosuke Niwa]

Created attachment 407450 [details]
Updated per review comments

[Ryosuke Niwa]

(In reply to Darin Adler from comment #5)
>
> When programming in Swift I really enjoy map, filter, reduce, flatMap, and
> compactMap, and I think we might eventually find we want all 5 of them.

I think filter is up next for sure.

[Sam Weinig]

(In reply to Ryosuke Niwa from comment #6)
> (In reply to youenn fablet from comment #2)
> > > Source/WTF/ChangeLog:11
> > > +        This patch adds WTF::filteredMap, which calls a function on each item in an iterable object like WTF::map
> > > +        but also filters the returned value. The mapped function may return Optional<T> or RefPtr<T>. The value
> > > +        is kept in the result if the returned value is not WTF::nullopt in the case of Optional<T> and not null
> > > +        in the case of RefPtr<T>. The result will be either Vector<T> for Optional<T> or else Vector<Ref<T>>.
> > 
> > I get that Optional<Ref<T>> is a bad thing to store in a class (since it
> > will be 2 * sizeof(T*) rather than sizeof(T*)), but I think for something
> > like this, where we are only using it as a return type, Optional<Ref<T>>
> > might be nicer, and would require less special casing. 
> > 
> > Is there a particular use where having this special case for RefPtr is
> > useful?
> 
> The main use case is calling an existing function which returns RefPtr. It's
> annoying to write code like this:
> 
> filteredMap(~, Optional<Ref<X>> [] (auto& x) {
>     auto result = foo(x);
>     if (!result)
>         return WTF::nullopt;
>     return result.releaseNonNull();
> });
> 

Is there a specific instance of this you have in mind for use with this new function? That would probably help me visualize things a bit better.

[Darin Adler]

Comment on attachment 407450 [details]
Updated per review comments

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

> Source/WTF/wtf/Vector.h:1741
> +template<typename MapFunction, typename SourceType>
> +Vector<typename CompactMapper<MapFunction, SourceType>::DestinationItemType> compactMap(SourceType&& source, MapFunction&& mapFunction)

With "map" still a member function but this a free function, we are a bit inconsistent.

> Tools/TestWebKitAPI/Tests/WTF/Vector.cpp:885
> +    auto mapped = WTF::compactMap(vector, evenMultipliedByFive);

Not sure the WTF prefix is needed here.

[Darin Adler]

Comment on attachment 407450 [details]
Updated per review comments

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

> Source/WTF/wtf/Vector.h:1716
> +                result.append(CompactMapTraits<ResultItemType>::extractValue(itemResult));

Don’t we want WTFMove here? Should we add test coverage tho check for that?

> Source/WTF/wtf/Vector.h:1718
> +        return result;

I think typically we’d want a call to shrinkToFit here if we don’t use reserveInitialCapacity.

> Source/WTF/wtf/Vector.h:1734
> +                result.append(CompactMapTraits<ResultItemType>::extractValue(itemResult));

Don’t we want WTFMove here? Should we add test coverage tho check for that?

> Source/WTF/wtf/Vector.h:1736
> +        return result;

I think typically we’d want a call to shrinkToFit here if we don’t use reserveInitialCapacity.

[Ryosuke Niwa]

(In reply to Sam Weinig from comment #9)
>
> Is there a specific instance of this you have in mind for use with this new
> function? That would probably help me visualize things a bit better.

Sure. In HTMLSlotElement::assignedNodes, we have a code like this:

Vector<Ref<Node>> nodes;
nodes.reserveInitialCapacity(assignedNodes->size());
for (auto& nodePtr : *assignedNodes) {
    auto* node = nodePtr.get();
    if (UNLIKELY(!node))
        continue;
    nodes.uncheckedAppend(*node);
}

This could be written as:

assignedNodes.compactMap([](auto& node) -> RefPtr<Node> { return node.get(); });

I guess we can add a helper on WeakPtr to return Optional<Ref<>> as well but given many of these classes and functions return RefPtr right now, it's going to be annoying. There is also the case of functions returning a raw pointer as well. Unless we create a helper to convert T* to Optional<T&> and Optional<Ref<T>>, it would be annoying to explicitly create either.

[Ryosuke Niwa]

Comment on attachment 407450 [details]
Updated per review comments

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

>> Source/WTF/wtf/Vector.h:1716
>> +                result.append(CompactMapTraits<ResultItemType>::extractValue(itemResult));
> 
> Don’t we want WTFMove here? Should we add test coverage tho check for that?

No, this is the version which doesn't move the original Vector.

I guess I didn't add a test coverage for this one so I'll add it.
(the r-reference version is now tested by CompactMapLambdaReturnOptionalCountedObject).

>> Source/WTF/wtf/Vector.h:1718
>> +        return result;
> 
> I think typically we’d want a call to shrinkToFit here if we don’t use reserveInitialCapacity.

Sure, I can add that call there.

>> Source/WTF/wtf/Vector.h:1734
>> +                result.append(CompactMapTraits<ResultItemType>::extractValue(itemResult));
> 
> Don’t we want WTFMove here? Should we add test coverage tho check for that?

No, Youenn mentioned that too earlier but copy elision takes care of that,
and I did add test a test per Youenn's comment: CompactMapLambdaReturnOptionalCountedObject

I guess I forgot to update the change log so I'll update that.

>> Source/WTF/wtf/Vector.h:1736
>> +        return result;
> 
> I think typically we’d want a call to shrinkToFit here if we don’t use reserveInitialCapacity.

Sure, will do.

>> Source/WTF/wtf/Vector.h:1741
>> +Vector<typename CompactMapper<MapFunction, SourceType>::DestinationItemType> compactMap(SourceType&& source, MapFunction&& mapFunction)
> 
> With "map" still a member function but this a free function, we are a bit inconsistent.

Hm... I guess we can call it CompactMapper<~>::compactMap.

[Ryosuke Niwa]

Comment on attachment 407450 [details]
Updated per review comments

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

>>> Source/WTF/wtf/Vector.h:1734
>>> +                result.append(CompactMapTraits<ResultItemType>::extractValue(itemResult));
>> 
>> Don’t we want WTFMove here? Should we add test coverage tho check for that?
> 
> No, Youenn mentioned that too earlier but copy elision takes care of that,
> and I did add test a test per Youenn's comment: CompactMapLambdaReturnOptionalCountedObject
> 
> I guess I forgot to update the change log so I'll update that.

Oh, now I see what's wrong here. You were talking about the argument to extractValue, not the return value.
My test had a bug to not catch this. Fixed that.

[Ryosuke Niwa]

Created attachment 407649 [details]
Updated patch

[Ryosuke Niwa]

Putting this up for a review once again since I've added quite a few new unit tests and there has been some semantic changes in the code as well.

[Ryosuke Niwa]

Ping reviewers.

[Yusuke Suzuki]

Comment on attachment 407649 [details]
Updated patch

r=me

[youenn fablet]

Comment on attachment 407649 [details]
Updated patch

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

> Tools/TestWebKitAPI/Tests/WTF/Vector.cpp:926
> +    Vector<Ref<RefCountedObject>> mapped = WTF::compactMap(vector, createRefCountedForOdd);

auto

> Tools/TestWebKitAPI/Tests/WTF/Vector.cpp:946
> +    Vector<Ref<RefCountedObject>> mapped = WTF::compactMap(vector, createRefCountedForEven);

auto

> Tools/TestWebKitAPI/Tests/WTF/Vector.cpp:968
> +    Vector<RefPtr<RefCountedObject>> mapped = WTF::compactMap(vector, createRefCountedWhenDivisibleByThree);

auto

> Tools/TestWebKitAPI/Tests/WTF/Vector.cpp:995
> +    CountedObject(int value)

explicit

> Tools/TestWebKitAPI/Tests/WTF/Vector.cpp:1063
> +    Vector<Ref<RefCountedObject>> mapped = WTF::compactMap(vector, [](int value) -> RefPtr<RefCountedObject> {

auto

> Tools/TestWebKitAPI/Tests/WTF/Vector.cpp:1102
> +    Vector<RefPtr<RefCountedObject>> mapped = WTF::compactMap(vector, [&](int value) -> Optional<RefPtr<RefCountedObject>> {

s/Vector<RefPtr<RefCountedObject>>/auto

> Tools/TestWebKitAPI/Tests/WTF/Vector.cpp:1110
> +    EXPECT_EQ(0U, RefCountedObject::s_totalRefCount);

I guess you might want to set s_totalRefCount to zero at the beginning of this test

[Ryosuke Niwa]

(In reply to youenn fablet from comment #19)
> Comment on attachment 407649 [details]
> Updated patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=407649&action=review
> 
> > Tools/TestWebKitAPI/Tests/WTF/Vector.cpp:926
> > +    Vector<Ref<RefCountedObject>> mapped = WTF::compactMap(vector, createRefCountedForOdd);
> 
> auto

I actually wanted to explicitly write out the type so that if we regress compactMap to start returning a wrong type, we'd catch it.

> 
> > Tools/TestWebKitAPI/Tests/WTF/Vector.cpp:946
> > +    Vector<Ref<RefCountedObject>> mapped = WTF::compactMap(vector, createRefCountedForEven);
> 
> auto

I guess we can use auto here since I've already tested above.

> > Tools/TestWebKitAPI/Tests/WTF/Vector.cpp:968
> > +    Vector<RefPtr<RefCountedObject>> mapped = WTF::compactMap(vector, createRefCountedWhenDivisibleByThree);
> 
> auto

Here, because it's RefPtr, I'd like to test it.

> 
> > Tools/TestWebKitAPI/Tests/WTF/Vector.cpp:995
> > +    CountedObject(int value)
> 
> explicit

Fixed.

> > Tools/TestWebKitAPI/Tests/WTF/Vector.cpp:1063
> > +    Vector<Ref<RefCountedObject>> mapped = WTF::compactMap(vector, [](int value) -> RefPtr<RefCountedObject> {
> 
> auto

Ditto about testing the type.

> > Tools/TestWebKitAPI/Tests/WTF/Vector.cpp:1102
> > +    Vector<RefPtr<RefCountedObject>> mapped = WTF::compactMap(vector, [&](int value) -> Optional<RefPtr<RefCountedObject>> {
> 
> s/Vector<RefPtr<RefCountedObject>>/auto

Ditto.

> > Tools/TestWebKitAPI/Tests/WTF/Vector.cpp:1110
> > +    EXPECT_EQ(0U, RefCountedObject::s_totalRefCount);
> 
> I guess you might want to set s_totalRefCount to zero at the beginning of
> this test

Good point. Fixed.

[Ryosuke Niwa]

Created attachment 407783 [details]
Patch for landing

[EWS]

Committed r266488: <https://trac.webkit.org/changeset/266488>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 407783 [details].

[Radar WebKit Bug Importer]

<rdar://problem/68232471>

[Darin Adler]

Comment on attachment 407649 [details]
Updated patch

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

>>> Tools/TestWebKitAPI/Tests/WTF/Vector.cpp:926
>>> +    Vector<Ref<RefCountedObject>> mapped = WTF::compactMap(vector, createRefCountedForOdd);
>> 
>> auto
> 
> I actually wanted to explicitly write out the type so that if we regress compactMap to start returning a wrong type, we'd catch it.

Technically that’s not right. Assigning to a specific type will test that we can convert to that type, not that we return the right type. The way to check what type we return is with a static_assert of what the return type is.

>>> Tools/TestWebKitAPI/Tests/WTF/Vector.cpp:968
>>> +    Vector<RefPtr<RefCountedObject>> mapped = WTF::compactMap(vector, createRefCountedWhenDivisibleByThree);
>> 
>> auto
> 
> Here, because it's RefPtr, I'd like to test it.

Same comment as above.

[Ryosuke Niwa]

(In reply to Darin Adler from comment #24)
> Comment on attachment 407649 [details]
> Updated patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=407649&action=review
> 
> >>> Tools/TestWebKitAPI/Tests/WTF/Vector.cpp:926
> >>> +    Vector<Ref<RefCountedObject>> mapped = WTF::compactMap(vector, createRefCountedForOdd);
> >> 
> >> auto
> > 
> > I actually wanted to explicitly write out the type so that if we regress compactMap to start returning a wrong type, we'd catch it.
> 
> Technically that’s not right. Assigning to a specific type will test that we
> can convert to that type, not that we return the right type. The way to
> check what type we return is with a static_assert of what the return type is.

That's a good point.

[Ryosuke Niwa]

(In reply to Ryosuke Niwa from comment #25)
> (In reply to Darin Adler from comment #24)
> > Comment on attachment 407649 [details]
> > Updated patch
> > 
> > View in context:
> > https://bugs.webkit.org/attachment.cgi?id=407649&action=review
> > 
> > >>> Tools/TestWebKitAPI/Tests/WTF/Vector.cpp:926
> > >>> +    Vector<Ref<RefCountedObject>> mapped = WTF::compactMap(vector, createRefCountedForOdd);
> > >> 
> > >> auto
> > > 
> > > I actually wanted to explicitly write out the type so that if we regress compactMap to start returning a wrong type, we'd catch it.
> > 
> > Technically that’s not right. Assigning to a specific type will test that we
> > can convert to that type, not that we return the right type. The way to
> > check what type we return is with a static_assert of what the return type is.
> 
> That's a good point.

Addressing this in https://bugs.webkit.org/show_bug.cgi?id=216119