Bug 205449 – Allow Vectors as hash keys

• Component: Web Template Framework
• Status: RESOLVED FIXED

[Antti Koivisto]

Add traits to allow Vectors of hashable types to act as hash keys.

[Antti Koivisto]

Created attachment 386101 [details]
patch

[Antti Koivisto]

Created attachment 386102 [details]
patch

[Saam Barati]

Comment on attachment 386102 [details]
patch

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

> Source/WTF/wtf/VectorHash.h:52
> +    static constexpr bool emptyValueIsZero = false;

Don’t you need to make the empty value too? What is the empty value?

[Saam Barati]

Comment on attachment 386102 [details]
patch

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

> Source/WTF/ChangeLog:22
> +        Add traits. Empty Vector is the empty value.

I see this now. I’m not a huge fan of this. What if there is a scenario where empty vector is a legit key? Maybe just make the empty value Max - 1 and nullptr

> Source/WTF/wtf/Vector.h:670
> +        : Base(0, -1)

Should we use numeric_limits Max for cleanliness?

[Antti Koivisto]

> I see this now. I’m not a huge fan of this. What if there is a scenario
> where empty vector is a legit key? Maybe just make the empty value Max - 1
> and nullptr

Things are simpler and more understandable if the empty value is a regular valid value. I think for types that have well-defined "empty" it is better to stick with that.

This can be reconsider if a use case where this matters appears.

[Antti Koivisto]

Created attachment 386111 [details]
patch

[Antti Koivisto]

now with numeric_limits

[Geoffrey Garen]

Comment on attachment 386111 [details]
patch

r=me

I think you can use emptyValueIsZero if inlineCapacity is zero.

[Antti Koivisto]

Created attachment 386120 [details]
patch

[WebKit Commit Bot]

Comment on attachment 386120 [details]
patch

Clearing flags on attachment: 386120

Committed r253775: <https://trac.webkit.org/changeset/253775>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Radar WebKit Bug Importer]

<rdar://problem/58086272>

[Saam Barati]

(In reply to Antti Koivisto from comment #5)
> > I see this now. I’m not a huge fan of this. What if there is a scenario
> > where empty vector is a legit key? Maybe just make the empty value Max - 1
> > and nullptr
> 
> Things are simpler and more understandable if the empty value is a regular
> valid value. I think for types that have well-defined "empty" it is better
> to stick with that.
> 
> This can be reconsider if a use case where this matters appears.

Why introduce this footgun? We already know from experience people want to put nullptr, zero, etc, in hash tables as keys. I don't see why we wouldn't also want an empty vector. I don't understand why having a well-defined "empty" is any more important than a well defined "deleted" value? If we're introducing something new, we might as well introduce it without the footgun.

[Antti Koivisto]

> Why introduce this footgun? We already know from experience people want to
> put nullptr, zero, etc, in hash tables as keys. I don't see why we wouldn't
> also want an empty vector. I don't understand why having a well-defined
> "empty" is any more important than a well defined "deleted" value? If we're
> introducing something new, we might as well introduce it without the footgun.

Patches welcome. 

Deleted value is just some unique bits written to a hash table slot. The templates appear to expect empty value to be movable and destructible. It is not immediately obvious to me how to do without complicating Vector disproportionally.

[Alexey Proskuryakov]

Using a mutable container as key is a pretty big footgun by itself.

[Antti Koivisto]

(In reply to Alexey Proskuryakov from comment #15)
> Using a mutable container as key is a pretty big footgun by itself.

As opposed to any other mutable type?

[Alexey Proskuryakov]

A mutable container is more dangerous than e.g. an int. That's because those get passed over by reference all the time.