WTF collections and std::algorithms

212 views
Skip to first unread message

Aleks Totic

unread,
Oct 20, 2016, 12:46:15 PM10/20/16
to platform-arc...@chromium.org
I've been working with WTF collections a lot recently. 
I often find myself imagining my code as STL, then
mapping the solution to WTF.

WTF having different method names for same functionality causes me trouble. 

In particular, the way we append elements: WTF::Array::append vs std::array::push_back.
- there is a mental cost of keeping track of two ways of doing it.
- you can't use some of std::algorithm for common tasks.

For example, back_inserter does not work, because it wants a collection that has push_back.

Instead of idiomatic:
std::copy (bar.begin(),bar.end(),back_inserter(foo));

I have to write manual loops instead (except for Vectors, can use copyToVector).

for (auto& n: bar)
  foo.push_back(n);

My questions are:
- is there any interest in alligning STL and WTF APIs?
- if not, how about a a one-off,  push_back be added to WTF::Vector?

Aleks

Kentaro Hara

unread,
Oct 20, 2016, 12:55:59 PM10/20/16
to Aleks Totic, platform-architecture-dev
I think we should do this -- we should make WTF APIs more consistent with STL APIs.

I don't think this is controversial, but the problem is how to find eng resources for the renaming work? :)

 
- if not, how about a a one-off,  push_back be added to WTF::Vector?

Aleks

--
You received this message because you are subscribed to the Google Groups "platform-architecture-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to platform-architecture-dev+unsub...@chromium.org.
To post to this group, send email to platform-architecture-dev@chromium.org.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/platform-architecture-dev/CAMdyzDvoGrOzXrbCPAmb4XXek6F8qLhmPsNRkuY%3DyT7%2BZACt%2Bw%40mail.gmail.com.



--
Kentaro Hara, Tokyo, Japan

Jeremy Roman

unread,
Oct 20, 2016, 12:56:08 PM10/20/16
to Aleks Totic, platform-architecture-dev
I'm a big fan of <algorithm> (though I admit, back_inserter hasn't come up much for me -- perhaps in part because I usually put a resize call in for efficiency, and then I can just use an ordinary iterator).

I generally like the idea of aligning with STL, but I don't know how wtf/ owners currently feel about this. Failing that, writing an OutputIterator that calls WTF::Vector::append doesn't seem unreasonable to me.

Alex Clarke

unread,
Oct 20, 2016, 12:56:19 PM10/20/16
to Aleks Totic, platform-architecture-dev
+1 to renaming WTF things to match STL ones, I find it confusing to have both.

Elliott Sprehn

unread,
Oct 20, 2016, 1:02:15 PM10/20/16
to Alex Clarke, Aleks Totic, platform-architecture-dev
Yeah I've wanted to do this for a while. We should align the names with the STL where the semantics are the same or very similar.

In terms of being pragmatic you're more than welcome to put up a patch that adds push_back to Vector so you can use it with something in <algorithm>. :)

On Thu, Oct 20, 2016 at 9:56 AM, 'Alex Clarke' via platform-architecture-dev <platform-architecture-dev@chromium.org> wrote:
+1 to renaming WTF things to match STL ones, I find it confusing to have both.
On 20 October 2016 at 17:45, 'Aleks Totic' via platform-architecture-dev <platform-architecture-dev@chromium.org> wrote:
I've been working with WTF collections a lot recently. 
I often find myself imagining my code as STL, then
mapping the solution to WTF.

WTF having different method names for same functionality causes me trouble. 

In particular, the way we append elements: WTF::Array::append vs std::array::push_back.
- there is a mental cost of keeping track of two ways of doing it.
- you can't use some of std::algorithm for common tasks.

For example, back_inserter does not work, because it wants a collection that has push_back.

Instead of idiomatic:
std::copy (bar.begin(),bar.end(),back_inserter(foo));

I have to write manual loops instead (except for Vectors, can use copyToVector).

for (auto& n: bar)
  foo.push_back(n);

My questions are:
- is there any interest in alligning STL and WTF APIs?
- if not, how about a a one-off,  push_back be added to WTF::Vector?

Aleks

--
You received this message because you are subscribed to the Google Groups "platform-architecture-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to platform-architecture-dev+unsubsc...@chromium.org.

--
You received this message because you are subscribed to the Google Groups "platform-architecture-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to platform-architecture-dev+unsubsc...@chromium.org.

To post to this group, send email to platform-architecture-dev@chromium.org.

Aleks Totic

unread,
Oct 21, 2016, 2:18:44 AM10/21/16
to Kentaro Hara, platform-architecture-dev
I think we should do this -- we should make WTF APIs more consistent with STL APIs.

I don't think this is controversial, but the problem is how to find eng resources for the renaming work? :)

That is really tempting, I love reducing the number of hops my brain has to make when writing code. I have 2 big things on my plate right now. Maybe after these are done. Any guess on how long might this take?

 Aleks

Daniel Cheng

unread,
Oct 21, 2016, 2:50:55 AM10/21/16
to Aleks Totic, Kentaro Hara, platform-architecture-dev
I think we'd want to come up with a reasonable migration plan. Just adding push_back() is easy enough, but there are several thousand uses of append(U&&) that we should switch for consistency. We also have emplaceAppend(Args&&...), an overload of append(U*, size_t), etc, that we'd probably want to update as well (IMO, it'd be even more confusing if we ended up in a halfway state for an extended period of time).

Daniel
 

 Aleks

--
You received this message because you are subscribed to the Google Groups "platform-architecture-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to platform-architect...@chromium.org.
To post to this group, send email to platform-arc...@chromium.org.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/platform-architecture-dev/CAMdyzDv_ireSeU1LCB7i_7_WD2u5fr7E%2BZrM%3Dp3o-CG4YvL%3DEQ%40mail.gmail.com.

Kentaro Hara

unread,
Oct 21, 2016, 4:23:16 AM10/21/16
to Daniel Cheng, Aleks Totic, platform-architecture-dev
On Fri, Oct 21, 2016 at 7:50 AM, Daniel Cheng <dch...@chromium.org> wrote:

On Thu, Oct 20, 2016 at 11:18 PM 'Aleks Totic' via platform-architecture-dev <platform-architecture-dev@chromium.org> wrote:
I think we should do this -- we should make WTF APIs more consistent with STL APIs.

I don't think this is controversial, but the problem is how to find eng resources for the renaming work? :)

That is really tempting, I love reducing the number of hops my brain has to make when writing code. I have 2 big things on my plate right now. Maybe after these are done. Any guess on how long might this take?

I think we'd want to come up with a reasonable migration plan. Just adding push_back() is easy enough, but there are several thousand uses of append(U&&) that we should switch for consistency. We also have emplaceAppend(Args&&...), an overload of append(U*, size_t), etc, that we'd probably want to update as well (IMO, it'd be even more confusing if we ended up in a halfway state for an extended period of time).

+1 to do planning before starting random replacement, at least about Vector, HashTable and String.

Is there any volunteer who is interested in this work?


 
Daniel
 

 Aleks

--
You received this message because you are subscribed to the Google Groups "platform-architecture-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to platform-architecture-dev+unsub...@chromium.org.
To post to this group, send email to platform-architecture-dev@chromium.org.

Mark

unread,
Oct 21, 2016, 2:41:47 PM10/21/16
to platform-architecture-dev, dch...@chromium.org, ato...@google.com
On Friday, October 21, 2016 at 4:23:16 AM UTC-4, Kentaro wrote:
On Fri, Oct 21, 2016 at 7:50 AM, Daniel Cheng <dch...@chromium.org> wrote:
On Thu, Oct 20, 2016 at 11:18 PM 'Aleks Totic' via platform-architecture-dev <platform-architecture-dev@chromium.org> wrote:
I think we should do this -- we should make WTF APIs more consistent with STL APIs.

I don't think this is controversial, but the problem is how to find eng resources for the renaming work? :)

That is really tempting, I love reducing the number of hops my brain has to make when writing code. I have 2 big things on my plate right now. Maybe after these are done. Any guess on how long might this take?

I think we'd want to come up with a reasonable migration plan. Just adding push_back() is easy enough, but there are several thousand uses of append(U&&) that we should switch for consistency. We also have emplaceAppend(Args&&...), an overload of append(U*, size_t), etc, that we'd probably want to update as well (IMO, it'd be even more confusing if we ended up in a halfway state for an extended period of time).

+1 to do planning before starting random replacement, at least about Vector, HashTable and String.

Is there any volunteer who is interested in this work?



I volunteer to do the grunt work. Who can help me come up with a migration plan?

-Mark

Mark

unread,
Oct 21, 2016, 3:08:17 PM10/21/16
to platform-architecture-dev, dch...@chromium.org, ato...@google.com
Following up on this, I looked at WTF::Vector::append() and there are several forms, not even counting emplaceAppend.

void append(U&&); <-- seems like a straight rename s/append/push_back/g

void append(const U*, size_t); <-- doesn't seem like it should be just renamed

void uncheckedAppend(U&& val); <-- WTF-specific, used a few hundred times throughout third_party/WebKit/, comment says "This version of append saves a branch in the case where you know that the vector's capacity is large enough for the append to succeed."

So as a first pass, I'd say only migrate the first form, but there's still enough instances of that one alone that we'd need to break it up into separate CLs for content/, chrome/, etc.

More thoughts?

-Mark

Elliott Sprehn

unread,
Oct 21, 2016, 4:26:48 PM10/21/16
to Mark, platform-architecture-dev, Aleks Totic, dch...@chromium.org

WTF isn't used in content or chrome, what do you need to change there?

>
> More thoughts?
>
> -Mark


>
> --
> You received this message because you are subscribed to the Google Groups "platform-architecture-dev" group.

> To unsubscribe from this group and stop receiving emails from it, send an email to platform-architect...@chromium.org.
> To post to this group, send email to platform-arc...@chromium.org.
> To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/platform-architecture-dev/59335a56-39d3-47ec-a94d-6b175d6b1159%40chromium.org.

Kentaro Hara

unread,
Oct 23, 2016, 6:56:17 PM10/23/16
to Elliott Sprehn, Mark, platform-architecture-dev, Aleks Totic, Daniel Cheng
> void append(U&&); <-- seems like a straight rename s/append/push_back/g
>
> void append(const U*, size_t); <-- doesn't seem like it should be just renamed
>
> void uncheckedAppend(U&& val); <-- WTF-specific, used a few hundred times throughout third_party/WebKit/, comment says "This version of append saves a branch in the case where you know that the vector's capacity is large enough for the append to succeed."

If we rename the first one to push_back, I'd prefer renaming the second one to push_back and the third one to unchecked_push_back.

Would it be possible to create a list of Vector's methods and a renaming plan for them? For example, isEmpty() => empty(), reserveCapacity() => reserve() etc.



> To unsubscribe from this group and stop receiving emails from it, send an email to platform-architecture-dev+unsub...@chromium.org.
> To post to this group, send email to platform-architecture-dev@chromium.org.

--
You received this message because you are subscribed to the Google Groups "platform-architecture-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to platform-architecture-dev+unsub...@chromium.org.
To post to this group, send email to platform-architecture-dev@chromium.org.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/platform-architecture-dev/CAO9Q3iKYbVh6QJd2z9_vB8W3UFvRGyTLGPKYUrqY070hkbtUnA%40mail.gmail.com.

Aleks Totic

unread,
Oct 23, 2016, 11:27:50 PM10/23/16
to Kentaro Hara, platform-architecture-dev
Would it be possible to create a list of Vector's methods and a renaming plan for them? For example, isEmpty() => empty(), reserveCapacity() => reserve() etc.

It might be a good time to produce better docs for our collections while looking over existing collection APIs in detail. 
I'd love to see better Oilpan integration docs inside .md, lots of valuable info is only available in not-so-readable template files. See https://crbug.com/655787 for examples. I volunteer for this if you need help.

Aleks

Elliott Sprehn

unread,
Oct 23, 2016, 11:43:36 PM10/23/16
to Kentaro Hara, dch...@chromium.org, Mark, Aleks Totic, platform-architecture-dev

I think we should leave isEmpty() as an alias of empty(). We use isEmpty all over and the isFoo() for boolean test methods is both common practice all over chromium and well understood. This is a place where the stl is weirdly named compared to most other languages and common practice.


> To unsubscribe from this group and stop receiving emails from it, send an email to platform-architecture-dev+unsubsc...@chromium.org.

--
You received this message because you are subscribed to the Google Groups "platform-architecture-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to platform-architecture-dev+unsubsc...@chromium.org.

To post to this group, send email to platform-architecture-dev@chromium.org.

Kentaro Hara

unread,
Oct 24, 2016, 1:29:07 AM10/24/16
to Aleks Totic, platform-architecture-dev
Regarding Oilpan, we have a tutorial and a full documentation

Aleks Totic

unread,
Oct 24, 2016, 2:17:05 AM10/24/16
to platform-architecture-dev
I'd love to see better Oilpan integration docs inside .md, lots of valuable info is only available in not-so-readable template files. See https://crbug.com/655787 for examples. I volunteer for this if you need help.

Regarding Oilpan, we have a tutorial and a full documentation

Full documentation has an empty section for Heap Collections. 

I've been unable to find docs about:

- What collections are available, and what do they do (or just a pointer to standards class they are modeled after).
- Do they accept WeakMembers? What are the performance characteristics?
- Other details of using Oilpan, mentioned in the bug.

After working on Chrome for a while, I've gained a lot of this knowledge from verbal communication, and reading of header  files and existing code. It was an inefficient process.

Having ~complete docs for foundational classes would help all new Chrome developers. In a perfect world, every time I have to ask a question about foundational stuff, it should be answered by a link to an updated doc (or make it asker's job to update the docs).

Aleks

Joshua Bell

unread,
Oct 24, 2016, 2:16:03 PM10/24/16
to Aleks Totic, platform-architecture-dev
How about we (Mark?) create a spreadsheet, one sheet per class (?), list the current methods/overloads, note potential renames/etc for alignment with STL (soliciting comments), and have column(s) for documentation/examples and we crowd-source the docs?

A willing volunteer would convert the results to Markdown when we're done.

BTW, is this a comprehensive list of the WTF container types, or are there more lurking?

BitVector Deque DoublyLinkedList HashCountedSet HashMap HashSet LinkedHashSet LinkedStack ListHashSet RefVector.h TerminatedArray(?) Vector


Yuta Kitamura

unread,
Oct 25, 2016, 4:02:17 AM10/25/16
to Joshua Bell, Aleks Totic, platform-architecture-dev
I'm not opposed to renaming things in our WTF containers, but that would be tricky because we special-case a container containing some smart pointer like RefPtr<T>, std::unique_ptr<T> or Member<T>, which is basically treated as an array of raw pointers instead of the smart pointers. (This lets you look up a pointer in HashSet<std::unique_ptr>, which isn't easy with std containers.)

I'm not sure whether renaming all the names around has justifiable merits (compared to the work amount), though. I consider WTF containers are different from std containers, and I think it's natural that we have different names for stuff with different functionalities. (And I feel uneasy when an non-std class provides only methods with a different naming convention; I need to switch my minds every time I deal with "Blink code but adopting std naming scheme", which costs me a significant cognitive burden. It's simple for me that all Blink things adopt the Blink style. I might be in the minority, though.)

In this specific case, adding a std-compatible push_back() function would be sufficient to unblock the OP's problem, right? I think that's definitely acceptable. Why do we need to go further?

Thanks,
Yuta

On Tue, Oct 25, 2016 at 3:15 AM, Joshua Bell <jsb...@chromium.org> wrote:

--
You received this message because you are subscribed to the Google Groups "platform-architecture-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to platform-architecture-dev+unsub...@chromium.org.
To post to this group, send email to platform-architecture-dev@chromium.org.

Alex Clarke

unread,
Oct 25, 2016, 5:56:06 AM10/25/16
to Yuta Kitamura, Joshua Bell, Aleks Totic, platform-architecture-dev
On 25 October 2016 at 09:01, Yuta Kitamura <yu...@chromium.org> wrote:
I'm not opposed to renaming things in our WTF containers, but that would be tricky because we special-case a container containing some smart pointer like RefPtr<T>, std::unique_ptr<T> or Member<T>, which is basically treated as an array of raw pointers instead of the smart pointers. (This lets you look up a pointer in HashSet<std::unique_ptr>, which isn't easy with std containers.)

I'm not sure whether renaming all the names around has justifiable merits (compared to the work amount), though. I consider WTF containers are different from std containers, and I think it's natural that we have different names for stuff with different functionalities. (And I feel uneasy when an non-std class provides only methods with a different naming convention; I need to switch my minds every time I deal with "Blink code but adopting std naming scheme", which costs me a significant cognitive burden. It's simple for me that all Blink things adopt the Blink style. I might be in the minority, though.)

In this specific case, adding a std-compatible push_back() function would be sufficient to unblock the OP's problem, right?


I'd like to propose we initially add aliases for all WTF container methods that map 1:1 to stl functions e.g.

WTF::Vector
  • push_back = append
  • erase = remove
  • empty = isEmpty
  • emplace_back = emplaceAppend
  • pop_back = removeLast
  • front = first
  • back = last
WTF::HashMap
  • insert = add
  • erase = remove
  • empty = isEmpty
  • at = get
  • (maybe) implement operator[]
WTF::HashSet
  • insert = add
  • erase = remove
  • empty = isEmpty

There might be some I missed, but for me that would solve most of the problem.  Of course we'd have two names for things.  It would be possible to write a clang tool to rename everything, although that does seem to be quite a bit of work.

On a side note I recently used WTF::HashMap with the key being a WTF::Vector<String> this was surprisingly difficult to write because it needed a custom hash traits class with lots of odd members.  I note the STL also requires you to write a custom hash function and comparison for it's equivalent but that's very much easier to do.   I don't have any specific proposal here, I appreciate the optimization that has gone into WTF::HashMap I just wish it was easier to write custom hash traits for it.

 

Thanks,
Yuta

On Tue, Oct 25, 2016 at 3:15 AM, Joshua Bell <jsb...@chromium.org> wrote:

On Sun, Oct 23, 2016 at 11:16 PM, 'Aleks Totic' via platform-architecture-dev <platform-architecture-dev@chromium.org> wrote:
I'd love to see better Oilpan integration docs inside .md, lots of valuable info is only available in not-so-readable template files. See https://crbug.com/655787 for examples. I volunteer for this if you need help.

Regarding Oilpan, we have a tutorial and a full documentation

Full documentation has an empty section for Heap Collections. 

I've been unable to find docs about:

- What collections are available, and what do they do (or just a pointer to standards class they are modeled after).
- Do they accept WeakMembers? What are the performance characteristics?
- Other details of using Oilpan, mentioned in the bug.

After working on Chrome for a while, I've gained a lot of this knowledge from verbal communication, and reading of header  files and existing code. It was an inefficient process.

Having ~complete docs for foundational classes would help all new Chrome developers. In a perfect world, every time I have to ask a question about foundational stuff, it should be answered by a link to an updated doc (or make it asker's job to update the docs).

 
How about we (Mark?) create a spreadsheet, one sheet per class (?), list the current methods/overloads, note potential renames/etc for alignment with STL (soliciting comments), and have column(s) for documentation/examples and we crowd-source the docs?

A willing volunteer would convert the results to Markdown when we're done.

BTW, is this a comprehensive list of the WTF container types, or are there more lurking?

BitVector Deque DoublyLinkedList HashCountedSet HashMap HashSet LinkedHashSet LinkedStack ListHashSet RefVector.h TerminatedArray(?) Vector


--
You received this message because you are subscribed to the Google Groups "platform-architecture-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to platform-architecture-dev+unsubsc...@chromium.org.

To post to this group, send email to platform-architecture-dev@chromium.org.

--
You received this message because you are subscribed to the Google Groups "platform-architecture-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to platform-architecture-dev+unsub...@chromium.org.
To post to this group, send email to platform-architecture-dev@chromium.org.

Ojan Vafai

unread,
Oct 25, 2016, 2:31:51 PM10/25/16
to Alex Clarke, Yuta Kitamura, Joshua Bell, Aleks Totic, platform-architecture-dev
On Tue, Oct 25, 2016 at 2:56 AM 'Alex Clarke' via platform-architecture-dev <platform-arc...@chromium.org> wrote:
On 25 October 2016 at 09:01, Yuta Kitamura <yu...@chromium.org> wrote:
I'm not opposed to renaming things in our WTF containers, but that would be tricky because we special-case a container containing some smart pointer like RefPtr<T>, std::unique_ptr<T> or Member<T>, which is basically treated as an array of raw pointers instead of the smart pointers. (This lets you look up a pointer in HashSet<std::unique_ptr>, which isn't easy with std containers.)

I'm not sure whether renaming all the names around has justifiable merits (compared to the work amount), though. I consider WTF containers are different from std containers, and I think it's natural that we have different names for stuff with different functionalities. (And I feel uneasy when an non-std class provides only methods with a different naming convention; I need to switch my minds every time I deal with "Blink code but adopting std naming scheme", which costs me a significant cognitive burden. It's simple for me that all Blink things adopt the Blink style. I might be in the minority, though.)

In this specific case, adding a std-compatible push_back() function would be sufficient to unblock the OP's problem, right?


I'd like to propose we initially add aliases for all WTF container methods that map 1:1 to stl functions e.g.

WTF::Vector
  • push_back = append
  • erase = remove
  • empty = isEmpty
  • emplace_back = emplaceAppend
  • pop_back = removeLast
  • front = first
  • back = last
WTF::HashMap
  • insert = add
  • erase = remove
  • empty = isEmpty
  • at = get
  • (maybe) implement operator[]
WTF::HashSet
  • insert = add
  • erase = remove
  • empty = isEmpty

What's the advantage of aliases instead of renames? Just that it's less short-term work? If so, I'd rather we bite the bullet and take the short-term pain to avoid the long-term lack of confusion.

FWIW, having the names match where the behavior is the same makes sense to me too (roughly the list above lgtm). I agree with yutak's mental model for myself, but I find that a lot of people with less experience in WTF have a hard time quickly understanding code in third_party/WebKit partially because the names are different. I think it will help us feel more like one team if there are lower barriers between the different parts of the codebase.
 

There might be some I missed, but for me that would solve most of the problem.  Of course we'd have two names for things.  It would be possible to write a clang tool to rename everything, although that does seem to be quite a bit of work.

On a side note I recently used WTF::HashMap with the key being a WTF::Vector<String> this was surprisingly difficult to write because it needed a custom hash traits class with lots of odd members.  I note the STL also requires you to write a custom hash function and comparison for it's equivalent but that's very much easier to do.   I don't have any specific proposal here, I appreciate the optimization that has gone into WTF::HashMap I just wish it was easier to write custom hash traits for it.

 

Thanks,
Yuta

On Tue, Oct 25, 2016 at 3:15 AM, Joshua Bell <jsb...@chromium.org> wrote:

On Sun, Oct 23, 2016 at 11:16 PM, 'Aleks Totic' via platform-architecture-dev <platform-arc...@chromium.org> wrote:
I'd love to see better Oilpan integration docs inside .md, lots of valuable info is only available in not-so-readable template files. See https://crbug.com/655787 for examples. I volunteer for this if you need help.

Regarding Oilpan, we have a tutorial and a full documentation

Full documentation has an empty section for Heap Collections. 

I've been unable to find docs about:

- What collections are available, and what do they do (or just a pointer to standards class they are modeled after).
- Do they accept WeakMembers? What are the performance characteristics?
- Other details of using Oilpan, mentioned in the bug.

After working on Chrome for a while, I've gained a lot of this knowledge from verbal communication, and reading of header  files and existing code. It was an inefficient process.

Having ~complete docs for foundational classes would help all new Chrome developers. In a perfect world, every time I have to ask a question about foundational stuff, it should be answered by a link to an updated doc (or make it asker's job to update the docs).

 
How about we (Mark?) create a spreadsheet, one sheet per class (?), list the current methods/overloads, note potential renames/etc for alignment with STL (soliciting comments), and have column(s) for documentation/examples and we crowd-source the docs?

A willing volunteer would convert the results to Markdown when we're done.

BTW, is this a comprehensive list of the WTF container types, or are there more lurking?

BitVector Deque DoublyLinkedList HashCountedSet HashMap HashSet LinkedHashSet LinkedStack ListHashSet RefVector.h TerminatedArray(?) Vector


--
You received this message because you are subscribed to the Google Groups "platform-architecture-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to platform-architect...@chromium.org.
To post to this group, send email to platform-arc...@chromium.org.

--
You received this message because you are subscribed to the Google Groups "platform-architecture-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to platform-architect...@chromium.org.
To post to this group, send email to platform-arc...@chromium.org.

--
You received this message because you are subscribed to the Google Groups "platform-architecture-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to platform-architect...@chromium.org.
To post to this group, send email to platform-arc...@chromium.org.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/platform-architecture-dev/CAPG_qM7ZCE7wpw%3DBups0daLnun%2BF51aGVEdBBoR3mPTV80eFbw%40mail.gmail.com.

Alex Clarke

unread,
Oct 25, 2016, 3:37:29 PM10/25/16
to Ojan Vafai, Yuta Kitamura, Joshua Bell, Aleks Totic, platform-architecture-dev


On 25 October 2016 at 19:31, Ojan Vafai <oj...@chromium.org> wrote:
Pretty much that.
 
If so, I'd rather we bite the bullet and take the short-term pain to avoid the long-term lack of confusion.

FWIW, having the names match where the behavior is the same makes sense to me too (roughly the list above lgtm). I agree with yutak's mental model for myself, but I find that a lot of people with less experience in WTF have a hard time quickly understanding code in third_party/WebKit partially because the names are different. I think it will help us feel more like one team if there are lower barriers between the different parts of the codebase.
 

There might be some I missed, but for me that would solve most of the problem.  Of course we'd have two names for things.  It would be possible to write a clang tool to rename everything, although that does seem to be quite a bit of work.

On a side note I recently used WTF::HashMap with the key being a WTF::Vector<String> this was surprisingly difficult to write because it needed a custom hash traits class with lots of odd members.  I note the STL also requires you to write a custom hash function and comparison for it's equivalent but that's very much easier to do.   I don't have any specific proposal here, I appreciate the optimization that has gone into WTF::HashMap I just wish it was easier to write custom hash traits for it.

 

Thanks,
Yuta

On Tue, Oct 25, 2016 at 3:15 AM, Joshua Bell <jsb...@chromium.org> wrote:

On Sun, Oct 23, 2016 at 11:16 PM, 'Aleks Totic' via platform-architecture-dev <platform-architecture-dev@chromium.org> wrote:
I'd love to see better Oilpan integration docs inside .md, lots of valuable info is only available in not-so-readable template files. See https://crbug.com/655787 for examples. I volunteer for this if you need help.

Regarding Oilpan, we have a tutorial and a full documentation

Full documentation has an empty section for Heap Collections. 

I've been unable to find docs about:

- What collections are available, and what do they do (or just a pointer to standards class they are modeled after).
- Do they accept WeakMembers? What are the performance characteristics?
- Other details of using Oilpan, mentioned in the bug.

After working on Chrome for a while, I've gained a lot of this knowledge from verbal communication, and reading of header  files and existing code. It was an inefficient process.

Having ~complete docs for foundational classes would help all new Chrome developers. In a perfect world, every time I have to ask a question about foundational stuff, it should be answered by a link to an updated doc (or make it asker's job to update the docs).

 
How about we (Mark?) create a spreadsheet, one sheet per class (?), list the current methods/overloads, note potential renames/etc for alignment with STL (soliciting comments), and have column(s) for documentation/examples and we crowd-source the docs?

A willing volunteer would convert the results to Markdown when we're done.

BTW, is this a comprehensive list of the WTF container types, or are there more lurking?

BitVector Deque DoublyLinkedList HashCountedSet HashMap HashSet LinkedHashSet LinkedStack ListHashSet RefVector.h TerminatedArray(?) Vector


--
You received this message because you are subscribed to the Google Groups "platform-architecture-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to platform-architecture-dev+unsub...@chromium.org.
To post to this group, send email to platform-architecture-dev@chromium.org.

--
You received this message because you are subscribed to the Google Groups "platform-architecture-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to platform-architecture-dev+unsub...@chromium.org.
To post to this group, send email to platform-architecture-dev@chromium.org.

--
You received this message because you are subscribed to the Google Groups "platform-architecture-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to platform-architecture-dev+unsub...@chromium.org.
To post to this group, send email to platform-architecture-dev@chromium.org.

--
You received this message because you are subscribed to the Google Groups "platform-architecture-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to platform-architecture-dev+unsub...@chromium.org.
To post to this group, send email to platform-architecture-dev@chromium.org.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/platform-architecture-dev/CANMdWTsJLKY-vZCt%2BBoQhRqbK3SH_C%3DQ%3DFy3WcG7rqzhBaLB%2Bg%40mail.gmail.com.

Mark

unread,
Oct 26, 2016, 5:03:51 PM10/26/16
to platform-architecture-dev, yu...@chromium.org, jsb...@chromium.org, ato...@google.com

On Tuesday, October 25, 2016 at 5:56:06 AM UTC-4, Alex Clarke wrote:
I'd like to propose we initially add aliases for all WTF container methods that map 1:1 to stl functions e.g.

WTF::Vector
  • push_back = append
  • erase = remove
  • empty = isEmpty
  • emplace_back = emplaceAppend
  • pop_back = removeLast
  • front = first
  • back = last
Code Search estimates of method usage:

append (2558)
remove (108)
isEmpty (623)
emplaceAppend (13)
removeLast (56)
first (57+15) [T&+const T&]
last (251+35) [T&+const T&]
 
WTF::HashMap
  • insert = add
  • erase = remove
  • empty = isEmpty
  • at = get
add (590)
remove (174+43) [KeyPeekInType+iterator]
isEmpty (111)
get (433)

WTF::HashSet
  • insert = add
  • erase = remove
  • empty = isEmpty


add (479)
remove (168+17) [ValuePeekInType+iterator]
isEmpty (154) 

So only 5 of these methods (Vector::append(), Vector::isEmpty(), HashMap::add(), HashMap::get(), and HashSet::add()) are used more than 300 times each. The rest could each be switched over with a little automation and a day's work, and some commit-queue coordination. And those 5 could be done in stages. The entire rename could be done in a few weeks with minimal disruption. I volunteer to do this work.

-Mark

Elliott Sprehn

unread,
Oct 26, 2016, 6:24:25 PM10/26/16
to Mark, platform-architecture-dev, yu...@chromium.org, Joshua Bell, Aleks Totic
I've been looking at this and not all of the methods mentioned below have the same semantics as the stl. For example HashMap::remove() returns void, and the stl returns an iterator or a number (which for a Map is apparently always 1?). 

As I said earlier in the thread I also think we should also leave isEmpty alone since is_empty and isEmpty are both common (and match our style guide), and also match the methods with the same name all over WTF and the resto of blink, and the stl naming here is confusing since it sounds like a verb (ex. clear() or reset()).

See:

The count() method in the stl for contains() has a similar confusion and I'd rather not copy that from the stl. contains() is also a place where WTF is more consistent than the stl since Vector, Map and Set all support it, while std::map has count() but std::vector does not.

I'm okay with the other renames if other people are okay with having the return types divergent from the stl. void erase(...) vs stl's iterator erase(...).

--
You received this message because you are subscribed to the Google Groups "platform-architecture-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to platform-architecture-dev+unsub...@chromium.org.
To post to this group, send email to platform-architecture-dev@chromium.org.

Alex Clarke

unread,
Oct 27, 2016, 8:59:51 AM10/27/16
to Elliott Sprehn, Mark, platform-architecture-dev, yu...@chromium.org, Joshua Bell, Aleks Totic
On 26 October 2016 at 23:23, Elliott Sprehn <esp...@chromium.org> wrote:
I've been looking at this and not all of the methods mentioned below have the same semantics as the stl. For example HashMap::remove() returns void, and the stl returns an iterator or a number (which for a Map is apparently always 1?).
This is a good point. Arguably if possible we should match the STL semantics.  In the case of return values I'd expect this to be zero cost on optimized builds since for inlined functions the compiler can throw away unused return values if there are no side effects.

As I said earlier in the thread I also think we should also leave isEmpty alone since is_empty and isEmpty are both common (and match our style guide), and also match the methods with the same name all over WTF and the resto of blink, and the stl naming here is confusing since it sounds like a verb (ex. clear() or reset()).

Even if the stl name is bad, it's a name the majority of C++ programmers are used to and expect :)   Personally I don't mind having both but I suspect I'm in a minority there.

 
To unsubscribe from this group and stop receiving emails from it, send an email to platform-architecture-dev+unsubsc...@chromium.org.

To post to this group, send email to platform-architecture-dev@chromium.org.

--
You received this message because you are subscribed to the Google Groups "platform-architecture-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to platform-architecture-dev+unsub...@chromium.org.
To post to this group, send email to platform-architecture-dev@chromium.org.

Mark

unread,
Oct 28, 2016, 3:40:14 PM10/28/16
to platform-architecture-dev, yu...@chromium.org, jsb...@chromium.org, ato...@google.com
On Wednesday, October 26, 2016 at 5:03:51 PM UTC-4, Mark wrote:

On Tuesday, October 25, 2016 at 5:56:06 AM UTC-4, Alex Clarke wrote:
I'd like to propose we initially add aliases for all WTF container methods that map 1:1 to stl functions e.g.

WTF::Vector
  • push_back = append
  • erase = remove
  • empty = isEmpty
  • emplace_back = emplaceAppend
  • pop_back = removeLast
  • front = first
  • back = last
Code Search estimates of method usage:

append (2558)
remove (108)
isEmpty (623)
emplaceAppend (13)
removeLast (56)
first (57+15) [T&+const T&]
last (251+35) [T&+const T&]


OK, I went ahead and tackled the smallest two of these, just to see what sort of issues would arise.

emplaceAppend -> emplace_back is https://codereview.chromium.org/2457163002


Some thoughts:

1. There are a few classes that basically "wrap" a vector with additional semantics, for example src/third_party/WebKit/Source/platform/graphics/ContiguousContainer.cpp defines a removeLast() method which now calls the pop_back() method of its underlying Vector. Not sure if we want to cascade these name changes into such wrapper classes.

2. check-webkit-style's readability/naming/underscores rule complains that emplace_back and pop_back are "incorrectly named. Don't use underscores in your identifier names." :)

3. Please add yourself and/or other relevant people to the CLs for CC or review. (I will do this myself in future CLs, once I know whom to add.)

-Mark

Jeremy Roman

unread,
Oct 28, 2016, 8:48:44 PM10/28/16
to Mark, platform-architecture-dev, Yuta Kitamura, Joshua Bell, Aleks Totic
An FYI about ContiguousContainer: it also has a copy in cc, so ideally the two would match. (Not sure about Chromium's general philosophy about whether to match STL names or use Google-style names.)
 
2. check-webkit-style's readability/naming/underscores rule complains that emplace_back and pop_back are "incorrectly named. Don't use underscores in your identifier names." :)

3. Please add yourself and/or other relevant people to the CLs for CC or review. (I will do this myself in future CLs, once I know whom to add.)

-Mark

--
You received this message because you are subscribed to the Google Groups "platform-architecture-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to platform-architecture-dev+unsub...@chromium.org.
To post to this group, send email to platform-architecture-dev@chromium.org.

Mark

unread,
Feb 23, 2017, 12:38:59 PM2/23/17
to platform-architecture-dev, yu...@chromium.org, jsb...@chromium.org, ato...@google.com
On Wednesday, October 26, 2016 at 5:03:51 PM UTC-4, Mark wrote:
This went well. I completed everything listed above except for the isEmpty() methods, which Elliott was unsure we should change. 

Some things to consider:

1. There are a number of classes throughout Blink that essentially wrap WTF classes. For example, these 7 classes that act like vectors now define their own append() method that does nothing but call m_something.push_back():

~/work/src/third_party/WebKit/Source% grep -r "append(" * | grep "push_back("
core/xml/XPathNodeSet.h:  void append(Node* node) { m_nodes.push_back(node); }
core/dom/DOMStringList.h:  void append(const String& string) { m_strings.push_back(string); }
core/dom/TouchList.h:  void append(Touch* touch) { m_values.push_back(touch); }
core/fileapi/FileList.h:  void append(File* file) { m_files.push_back(file); }
core/css/CSSValueList.h:  void append(const CSSValue& value) { m_values.push_back(value); }
platform/fonts/opentype/FontSettings.h:  void append(const T& feature) { m_list.push_back(feature); }
wtf/RefVector.h:  void append(const T& decoration) { m_vector.push_back(decoration); }

Also HTTPHeaderMap, which acts like a HashMap:

~/work/src/third_party/WebKit/Source% grep -r "remove(" * | grep "erase("
platform/network/HTTPHeaderMap.h:  void remove(const AtomicString& k) { m_headers.erase(k); }

Question: do we want to extend the naming normalization to these wrapper classes?

2. I renamed methods in Vector but not Deque. Do we want to normalize Deque in the same way?

3. In order to rename HashSet::add() to ::insert(), I had to also an insert() to LinkedHashSet and ListHashSet, because there is testing code that assumes these classes have the same API. Do we want to normalize LinkedHashSet and ListHashSet in the same way?

4. In order to rename Vector::append() to ::push_back(), I had to completely change how HexNumber::appendByteAsHex() worked so we could essentially overload it with Vector-specific versions. [Thanks to jsbell for his technical assistance in actually implementing this, once we figured out what we wanted.] There is now one templated version of this function that calls destination.append() and two untemplated versions that take different kinds of Vectors and call destination.push_back(). This seems like a code smell, but I'm not sure what, if anything, to do about it.

5. Vector::emplace_back() now returns a reference to the new value that was appended, which matches the behavior of std::emplace_back. See https://codereview.chromium.org/2457163002 for discussion. This was the only semantic change so far.

Cheers,
-Mark

Sasha Bermeister

unread,
Feb 23, 2017, 7:54:55 PM2/23/17
to Mark, platform-architecture-dev, Yuta Kitamura, jsb...@chromium.org, ato...@google.com
I can answer 1. As a person who has refactored CSSValueList a hundred times ;), yes, we should definitely extend the naming normalization to these wrapper classes.

In fact, I'd like to see a standard way of writing these wrappers in general, e.g. should we add the vector as a member or inherit from the required vector class? Depending on the usage, maybe the answer might be different, but finding all the vector/hashmap wrapper classes in the codebase seems important for things like memory-infra. Another important question might be, what extra functionality are these wrapper classes providing and are they needed? Should they just be replaced by a typedef?

Thank you for doing this grungy but very important work!! Our codebase thanks you. :)

Sasha

--
You received this message because you are subscribed to the Google Groups "platform-architecture-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to platform-architecture-dev+unsub...@chromium.org.
To post to this group, send email to platform-architecture-dev@chromium.org.

Kentaro Hara

unread,
Feb 23, 2017, 11:49:27 PM2/23/17
to Sasha Bermeister, Mark, platform-architecture-dev, Yuta Kitamura, Joshua Bell, Aleks Totic
Thanks Pilgrim for moving this forward!

1. There are a number of classes throughout Blink that essentially wrap WTF classes. For example, these 7 classes that act like vectors now define their own append() method that does nothing but call m_something.push_back(): 
 
~/work/src/third_party/WebKit/Source% grep -r "append(" * | grep "push_back("
core/xml/XPathNodeSet.h:  void append(Node* node) { m_nodes.push_back(node); }
core/dom/DOMStringList.h:  void append(const String& string) { m_strings.push_back(string); }
core/dom/TouchList.h:  void append(Touch* touch) { m_values.push_back(touch); }
core/fileapi/FileList.h:  void append(File* file) { m_files.push_back(file); }
core/css/CSSValueList.h:  void append(const CSSValue& value) { m_values.push_back(value); }
platform/fonts/opentype/FontSettings.h:  void append(const T& feature) { m_list.push_back(feature); }
wtf/RefVector.h:  void append(const T& decoration) { m_vector.push_back(decoration); } 
 
Also HTTPHeaderMap, which acts like a HashMap: 
 
~/work/src/third_party/WebKit/Source% grep -r "remove(" * | grep "erase("
platform/network/HTTPHeaderMap.h:  void remove(const AtomicString& k) { m_headers.erase(k); }
 

I'd say yes. It might be a bit weird to introduce a hacker_case method to these classes, but the concern will be gone once the Blink Big Rename is done (in the very near future).


Question: do we want to extend the naming normalization to these wrapper classes?
2. I renamed methods in Vector but not Deque. Do we want to normalize Deque in the same way?

Yes. Deque is part of a "standard library" of Blink.

3. In order to rename HashSet::add() to ::insert(), I had to also an insert() to LinkedHashSet and ListHashSet, because there is testing code that assumes these classes have the same API. Do we want to normalize LinkedHashSet and ListHashSet in the same way?

Yes. LinkedHashSet and ListHashSet are part of a "standard library" of Blink.


4. In order to rename Vector::append() to ::push_back(), I had to completely change how HexNumber::appendByteAsHex() worked so we could essentially overload it with Vector-specific versions. [Thanks to jsbell for his technical assistance in actually implementing this, once we figured out what we wanted.] There is now one templated version of this function that calls destination.append() and two untemplated versions that take different kinds of Vectors and call destination.push_back(). This seems like a code smell, but I'm not sure what, if anything, to do about it.

Yeah, I'm not sure how we can improve it.

5. Vector::emplace_back() now returns a reference to the new value that was appended, which matches the behavior of std::emplace_back. See https://codereview.chromium.org/2457163002 for discussion. This was the only semantic change so far.

The semantic change looks fine to me.


To unsubscribe from this group and stop receiving emails from it, send an email to platform-architecture-dev+unsubsc...@chromium.org.

--
You received this message because you are subscribed to the Google Groups "platform-architecture-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to platform-architecture-dev+unsub...@chromium.org.
To post to this group, send email to platform-architecture-dev@chromium.org.

Joshua Bell

unread,
Apr 12, 2017, 7:35:27 PM4/12/17
to Kentaro Hara, Sasha Bermeister, Mark, platform-architecture-dev, Yuta Kitamura, Aleks Totic
I'm noticing that the Great Blink Rename has somewhat undone a bunch of pilgrim@'s hard work here to align WTF collection method names with STL. For example:

WTF::Vector::data() is now WTF::Vector::Data() vs. std::vector::data()

Capacity, Find, Clear, Swap, and a few others got uppercased.

It looks like some method names were kept (push/pop/back/front, r/begin/end, etc).

Do we want to undo that to continue aligning these with STL?

It does make the non-STL method names present on some collections (e.g. RemoveAll, IsEmpty) stand out more. It gets weird when there are not exact counterparts, e.g. std::vector has capacity() but std::set doesn't; should Capacity() be uppercase on WTF::HashSet ?

Daniel Cheng

unread,
Apr 12, 2017, 7:38:25 PM4/12/17
to Joshua Bell, Kentaro Hara, Sasha Bermeister, Mark, platform-architecture-dev, Yuta Kitamura, Aleks Totic
On Wed, Apr 12, 2017 at 4:35 PM Joshua Bell <jsb...@chromium.org> wrote:
I'm noticing that the Great Blink Rename has somewhat undone a bunch of pilgrim@'s hard work here to align WTF collection method names with STL. For example:

WTF::Vector::data() is now WTF::Vector::Data() vs. std::vector::data()

Capacity, Find, Clear, Swap, and a few others got uppercased.

Yes, this is a known issue and tracked in https://bugs.chromium.org/p/chromium/issues/detail?id=709815.
 

It looks like some method names were kept (push/pop/back/front, r/begin/end, etc).

Yeah, we missed a few in our list of exceptions to skip.
 

Do we want to undo that to continue aligning these with STL?

I think we should, hence the bug =)
 

It does make the non-STL method names present on some collections (e.g. RemoveAll, IsEmpty) stand out more. It gets weird when there are not exact counterparts, e.g. std::vector has capacity() but std::set doesn't; should Capacity() be uppercase on WTF::HashSet ?

I think it should be uppercase. Similar for the Find() overloads on HashSet/HashMap that take a HashTranslator, since they don't map 1:1 to an STL equivalent.

Daniel
 

--
You received this message because you are subscribed to the Google Groups "platform-architecture-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to platform-architect...@chromium.org.
To post to this group, send email to platform-arc...@chromium.org.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/platform-architecture-dev/CAD649j6N8hVs%3DOoYHBLXjCWXU%2BEioYdZ17ngB%2Bv6PEJjs_b4fg%40mail.gmail.com.

Joshua Bell

unread,
Apr 12, 2017, 7:51:32 PM4/12/17
to Daniel Cheng, Kentaro Hara, Sasha Bermeister, Mark, platform-architecture-dev, Yuta Kitamura, Aleks Totic
On Wed, Apr 12, 2017 at 4:38 PM, Daniel Cheng <dch...@chromium.org> wrote:
On Wed, Apr 12, 2017 at 4:35 PM Joshua Bell <jsb...@chromium.org> wrote:
I'm noticing that the Great Blink Rename has somewhat undone a bunch of pilgrim@'s hard work here to align WTF collection method names with STL. For example:

WTF::Vector::data() is now WTF::Vector::Data() vs. std::vector::data()

Capacity, Find, Clear, Swap, and a few others got uppercased.

Yes, this is a known issue and tracked in https://bugs.chromium.org/p/chromium/issues/detail?id=709815.

Yay! Apologies for not searching.
 
 

It looks like some method names were kept (push/pop/back/front, r/begin/end, etc).

Yeah, we missed a few in our list of exceptions to skip.
 

Do we want to undo that to continue aligning these with STL?

I think we should, hence the bug =)
 

It does make the non-STL method names present on some collections (e.g. RemoveAll, IsEmpty) stand out more. It gets weird when there are not exact counterparts, e.g. std::vector has capacity() but std::set doesn't; should Capacity() be uppercase on WTF::HashSet ?

I think it should be uppercase. Similar for the Find() overloads on HashSet/HashMap that take a HashTranslator, since they don't map 1:1 to an STL equivalent.

SGTM. 

FYI we were trying to track the renames in https://docs.google.com/a/chromium.org/spreadsheets/d/1bYpQ9qPRe-E84YbBUf-UiMIq1DSltHbSVsB2BXJ97ZM/edit?usp=sharing (chromium.org) if anyone wants to help with updating that as this settled.

 

Daniel
 

--
You received this message because you are subscribed to the Google Groups "platform-architecture-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to platform-architecture-dev+unsub...@chromium.org.
To post to this group, send email to platform-architecture-dev@chromium.org.

--
You received this message because you are subscribed to the Google Groups "platform-architecture-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to platform-architecture-dev+unsub...@chromium.org.
To post to this group, send email to platform-architecture-dev@chromium.org.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/platform-architecture-dev/CAF3XrKpBfyE6Ji2LW44%2B7M1bN1e74qJ8Vti1ThAZqeC15%2B61wQ%40mail.gmail.com.

Reply all
Reply to author
Forward
0 new messages