On Aug 25, 2010, at 1:46 PM, Geoffrey Garen wrote:

...

Sorry for the late-night webkit-dev spam, but in deploying adoptPtr, I've noticed a number of places where have a HashMap that owns its values as OwnPtrs. Unfortunately, this very clumsy currently. Each instance of this pattern has its own way of hacking around the problem, which might or might not result in memory errors. We really should have an OwnPtrHashMap (to complement RefPtrHashMap) that understands how to handle this case correctly.

To clarify:

Optimization aside, HashMap<RefPtr<T>, U> and HashMap<T, RefPtr<U> > work just fine. RefPtrHashMap was an optimization. The feature it needed, which HashMap did not provide, was the ability to look up a value by a non-key type (raw pointer), without first converting to key type (RefPtr), since converting to RefPtr would cause refcount churn. We couldn't find a way to do this using HashTraits without using casts that violated strict aliasing rules.

In contrast, HashMap<OwnPtr<T>, U> and HashMap<T, OwnPtr<U> > don't work at all. They don't compile, since OwnPtr is not copyable. If you made OwnPtr copyable, they would accidentally delete items during get() and resize() operations.

I think it is possible to make a specialization of HashMap that secretly uses a HashMap of raw pointers under the covers. That would fix the copies internal to HashTable. However, you'd have to decide on the correct semantics for get/set operations and possibly tweak their return types. In particular, for an OwnPtr value (likely the common case), you'd want get() to return a raw pointer, set() to take a PassOwnPtr, and take() to return a PassOwnPtr. You probably would not want to use OwnPtr anywhere in the API. This doesn't quite entirely match the HashMap contract, but it's close enough to be useful. (Note: I'm probably one of the people with enough template-fu to code this, but I probably won't have time in the very near future.)

A HashMap that owns its values wants to do something special when an item is overwritten, removed, or implicitly removed by HashMap destruction, but it doesn't want to do anything special when an item is copied or extracted.

I think the best way to achieve this with HashMap might be a hash trait, rather than literally putting an OwnPtr in the map. Specifically, the trait would be one willRemove callback, which took an iterator to an item, and one willRemoveAll callback, which took a begin iterator. These callbacks would default to empty inline functions.

But maybe there's a way to use special hash traits and translators to eliminate all or nearly all the C++ copying operations.

I don't think HashTraits is the right solution. It doesn't give as good type safety as a HashMap variant that takes PassOwnPtr for all set/add/whatever type functions. Also, HashTraits are about a type, but whether the HashMap takes single ownership is not intrinsic to the type, it is a question for the individual HashMap. You could validly have one HashMap that owns all its values (of type Foo*) and another HashMap with the same value space that does not. The only error would be multiple HashMaps trying to own the same object. Using PassOwnPtr as the way to transfer ownership to the HashMap would prevent this. Regards, Maciej

On Aug 28, 2010, at 10:57 PM, Darin Adler wrote:

We need Vector<OwnPtr> too. It has similar issues to HashMap with OwnPtr values, including the ones mentioned by Maciej.

For one example, look at CSSParser::m_floatingMediaQueryExpList.

Vector<OwnPtr> actually works[1], and I have an almost complete patch to fully OwnPtr-ize MediaQueryExp. The one problem is sorting - MediaQuery wants to sort the Vector<MediaQuery*> it gets with std::sort, followed by eliminating duplicates. A sort that solely uses swaps would work, but std::sort wants to make copies of the elements at times. I also tried to think of ways to cheat by copying to a vector of raw pointers and back, and it could be made to work with sufficiently aggressive use of leakPtr and adoptPtr, but at the cost of two extra copies. Yet another possibility is to use a hash to do the de-duping instead of sorting; I can't tell from context if the sorting is needed for any purpose other than subsequent de-duping. If you can help me think of a good solution for this I'll post my patch. Regards, Maciej [1] It works because: (a) VectorTraits already takes care of all internal copies that are actually moves, by cheating and doing them with memcpy. (b) Reads, and writes of an existing slot, all operate via a reference to the element type, so you can use -> or .get() on a returned element just fine, and you can assign in a PassOwnPtr<T> to an OwnPtr<T>&. (c) append() and similar methods that add an element to a not-yet-existing slot all are templatized on the type of the element being added, so appending a PassOwnPtr works. The Hash templates are more complicated, so they probably won't just work automatically.

On Aug 29, 2010, at 9:34 PM, Maciej Stachowiak wrote:

On Aug 29, 2010, at 9:14 PM, Maciej Stachowiak wrote:

...

Yet another possibility is to use a hash to do the de-duping instead of sorting; I can't tell from context if the sorting is needed for any purpose other than subsequent de-duping.

Turns out this doesn't work - the CSS Media Queries spec specifically requires serializing in sorted order and we have a test to that effect: http://dev.w3.org/csswg/cssom/#serializing-media-queries https://bugs.webkit.org/show_bug.cgi?id=39220

So it's down to violating the type system or writing my own sort.

OK, you silently guilted me into writing a non-copying sort function. <https://bugs.webkit.org/show_bug.cgi?id=44874> - Maciej