Allow LinkedList to hold RefPtr elements

RESOLVED FIXED in Firefox 52

Status

()

defect
RESOLVED FIXED
3 years ago
3 years ago

People

(Reporter: billm, Assigned: billm)

Tracking

unspecified
mozilla52
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox52 fixed)

Details

Attachments

(2 attachments, 2 obsolete attachments)

Posted patch patch (obsolete) — Splinter Review
The usefulness of LinkedList is somewhat diminished by the fact that it can't be used to hold refcounted elements. I don't think there's a specific reason for this. I wrote a little adapter class that makes it work. With this patch, you can use LinkedList<RefPtr<T>> for a linked list that holds strong references to T elements (where T must be a subclass of LinkedListElement<RefPtr<T>>).

This would probably make more sense if in all other places we used LinkedList<Foo*> instead of LinkedList<Foo>. I'm not sure what to do about that. Maybe instead of writing LinkedList<RefPtr<T>> we should use LinkedList<T, something>? Somehow LinkedList<RefPtr<T>> seems very natural though. Anyway, I'm open to ideas.
Attachment #8801613 - Flags: review?(nfroyd)
Comment on attachment 8801613 [details] [diff] [review]
patch

Review of attachment 8801613 [details] [diff] [review]:
-----------------------------------------------------------------

This is great.  I was just reviewing a patch the other day that had LinkedList<T*> where T* was refcounted, and the logic was...awkward.

The only real concern I have is about efficiency, see below.  I'm not really sure how to solve this, though...I'd like to at least have some sort of discussion before r+'ing this.

::: mfbt/LinkedList.h
@@ +79,5 @@
> +
> +/**
> + * LinkedList supports refcounted elements using this adapter class. Clients
> + * using LinkedList<RefPtr<T>> will get a data structure that holds a strong
> + * reference to T as long as T is in the list.

I think we should put these adapters in mozilla::detail.

@@ +212,5 @@
>     * Get the next element in the list, or nullptr if this is the last element
>     * in the list.
>     */
> +  ClientType getNext()            { return ClientType(mNext->asT()); }
> +  ConstClientType getNext() const { return ConstClientType(mNext->asT()); }

This part requires you to add a reference every time you call this method; particularly when you're traversing a linked list, we're going to incur a lot of refcounting traffic for very little gain.

I guess the problem here is that if the list holds the only reference to the element, you can't have this method return T*, because then when you remove the element from the list, you are going to release the element, which leaves you holding a bogus pointer.  Right?

(I guess in some ways this is an argument for encouraging people to use for_each or equivalent, so we could do the efficient thing in that case, and then if somebody really needed manual traversal, they would have to accept a tiny amount of inefficiency.  But even then, you could still call .remove() and blow things up, so that's not a total solution...)

::: mfbt/tests/TestLinkedList.cpp
@@ +169,5 @@
> +  while (ptr) {
> +    MOZ_RELEASE_ASSERT(ptr->mCount == 2);
> +    RefPtr<CountedClass> next = ptr->getNext();
> +    ptr->remove();
> +    ptr = next;

Might as well do |ptr = Move(next);|.
Attachment #8801613 - Flags: review?(nfroyd) → feedback+
For the efficiency issue, the only thing I can think of is to make getNext/getPrevious return raw pointers. That's a little less safe but it's not really any different than what we would get for nsTArray. What do you think Nathan?

That also raises the issue of what to do about the other ClientType stuff:
- setNext/setPrevious
- Iterator
- insertFront/insertBack
- getFirst/getLast
- popFirst/popLast

popFirst/popLast pretty much have to return ClientType since they remove the element. But all the others could be raw pointers.
Flags: needinfo?(nfroyd)
(In reply to Bill McCloskey (:billm) from comment #2)
> For the efficiency issue, the only thing I can think of is to make
> getNext/getPrevious return raw pointers. That's a little less safe but it's
> not really any different than what we would get for nsTArray. What do you
> think Nathan?


Yeah, I think that's what we're going to have to do.  Returning RefPtr<T>&, as nsTArray would do, doesn't make sense here, AFAICT.

> That also raises the issue of what to do about the other ClientType stuff:
> - setNext/setPrevious
> - Iterator
> - insertFront/insertBack
> - getFirst/getLast
> - popFirst/popLast
> 
> popFirst/popLast pretty much have to return ClientType since they remove the
> element. But all the others could be raw pointers.

Sounds good to me.
Flags: needinfo?(nfroyd)
Posted patch patch v2Splinter Review
Attachment #8801613 - Attachment is obsolete: true
Attachment #8804508 - Flags: review?(nfroyd)
Posted patch removeAndGetNext/Previous (obsolete) — Splinter Review
I'm going to throw this in here since I found it useful. I have a couple of loops where I need to iterate over the list and conditionally remove elements. It's kind of annoying to have to do:

for (RefPtr<T> p = list.getFirst(); p; ) {
  if (...) {
    RefPtr<T> next = p->getNext();
    p->remove();
    p = next;
    continue
  }
  ...
  p = p->getNext();
}

This patch allows you instead to do:

for (RefPtr<T> p = list.getFirst(); p; ) {
  if (...) {
    p = p->removeAndGetNext();
    continue
  }
  ...
  p = p->getNext();
}

which is a little nicer. I feel like this could be improved more, but I don't have any ideas.
Attachment #8804550 - Flags: review?(nfroyd)
Comment on attachment 8804508 [details] [diff] [review]
patch v2

Review of attachment 8804508 [details] [diff] [review]:
-----------------------------------------------------------------

Looks good, r=me with changes below.

::: mfbt/LinkedList.h
@@ +84,5 @@
> + * using LinkedList<RefPtr<T>> will get a data structure that holds a strong
> + * reference to T as long as T is in the list.
> + */
> +template<typename T>
> +struct LinkedListAdapter

Nit: we should call this LinkedListElementTraits.

@@ +92,5 @@
> +  typedef T* ClientType;
> +  typedef const T* ConstClientType;
> +
> +  static void enterList(LinkedListElement<T>* elt) {}
> +  static void exitList(LinkedListElement<T>* elt) {}

Documentation on these two functions would be good.

@@ +118,5 @@
>  {
> +  typedef typename detail::LinkedListAdapter<T>::RawType RawType;
> +  typedef typename detail::LinkedListAdapter<T>::ConstRawType ConstRawType;
> +  typedef typename detail::LinkedListAdapter<T>::ClientType ClientType;
> +  typedef typename detail::LinkedListAdapter<T>::ConstClientType ConstClientType;

Maybe we should do something like:

typedef typename detail::LinkedListElementTraits<T> Traits;
typedef Traits::RawType RawType;
...

?  That would enable shortening of calls to enterList and exitList below as well.

@@ +355,5 @@
>  private:
> +  typedef typename detail::LinkedListAdapter<T>::RawType RawType;
> +  typedef typename detail::LinkedListAdapter<T>::ConstRawType ConstRawType;
> +  typedef typename detail::LinkedListAdapter<T>::ClientType ClientType;
> +  typedef typename detail::LinkedListAdapter<T>::ConstClientType ConstClientType;

Same typedef dance as we did in LinkedListElement would be helpful here.

@@ +433,2 @@
>      if (ret) {
> +      static_cast<LinkedListElement<T>*>(RawType(ret))->remove();

It would be great it we could implement this without the extra refcounting, something like:

RawType ret = sentinel.getNext();
if (ret) {
  static_cast<LinkedListElement<T>*>(ret)->unlink();
}
// dont_AddRef isn't available in MFBT. :(
return already_AddRefed(ret);

unlink() is a new, private function that implements the guts of remove(), but without the exitList() call.

But that'd require another traits typedef or two, and I'm not sure if it generalizes nicely to other kinds of elements. =/  I guess file a followup bug for that, unless you think the above scheme is reasonable.
Attachment #8804508 - Flags: review?(nfroyd) → review+
Comment on attachment 8804550 [details] [diff] [review]
removeAndGetNext/Previous

We'd need tests for this, along with documentation, but I think this is reasonable.  Same comments about avoiding extra refcounting apply here.
Attachment #8804550 - Flags: review?(nfroyd) → feedback+
With docs and tests.

I'll file a new bug for getting rid of the refcounting in popFirst and such.
Attachment #8804550 - Attachment is obsolete: true
Attachment #8805316 - Flags: review?(nfroyd)
Comment on attachment 8805316 [details] [diff] [review]
removeAndGetNext/Previous v2

Review of attachment 8805316 [details] [diff] [review]:
-----------------------------------------------------------------

Thank you!
Attachment #8805316 - Flags: review?(nfroyd) → review+

Comment 10

3 years ago
Pushed by wmccloskey@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/c41a71b1c24e
Allow LinkedList to hold RefPtr elements (r=froydnj)
https://hg.mozilla.org/integration/mozilla-inbound/rev/721e3171510d
Add removeAndGetNext/Previous methods to LinkedList (r=froydnj)
https://hg.mozilla.org/integration/mozilla-inbound/rev/aeeb739b7ba7
Use CancelableRunnable for mOnChannelConnectedTask (r=dvander)
https://hg.mozilla.org/integration/mozilla-inbound/rev/eccaf394924f
Remove FlushPendingInterruptQueue (r=dvander)
https://hg.mozilla.org/integration/mozilla-inbound/rev/73e04e795ec3
Associate each message in IPC queue with the runnable that will run it (r=dvander)

Comment 11

3 years ago
Pushed by wmccloskey@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/b119fb8bc703
Revert "Bug 1310547 - Associate each message in IPC queue with the runnable that will run it (r=dvander)"
https://hg.mozilla.org/integration/mozilla-inbound/rev/767af6517e3e
Revert "Bug 1310547 - Remove FlushPendingInterruptQueue (r=dvander)"
https://hg.mozilla.org/integration/mozilla-inbound/rev/cdcde3282769
Revert "Bug 1310547 - Use CancelableRunnable for mOnChannelConnectedTask (r=dvander)"
Landed some stuff here with the wrong bug number. I backed it out and re-landed.
Backed bug 1312960 and bug 1310547 out for failing splitText-normalize.html in reftests on Windows 7 VM debug:

Bug 1312960:
https://hg.mozilla.org/integration/mozilla-inbound/rev/be5f087a2c4e3fcfd64a56921429f2a5b76dc02f
https://hg.mozilla.org/integration/mozilla-inbound/rev/07f30746ec45034db4a2d6da54796e6742ab7dfb
https://hg.mozilla.org/integration/mozilla-inbound/rev/4b390287fd434a9256a424a88f59d37cf1073362
https://hg.mozilla.org/integration/mozilla-inbound/rev/4c5b55684c21a261a1f4187b290d6ac7b4d5891c
https://hg.mozilla.org/integration/mozilla-inbound/rev/c4f2be33044f293bba6518622bbf4043b48e57bb

Bug 1310547:
https://hg.mozilla.org/integration/mozilla-inbound/rev/b38d9a1cd7995c1cf79d7fc9e5351839a1a2d95c
https://hg.mozilla.org/integration/mozilla-inbound/rev/0e4c28cbee9c44b1e1a97846212f03f95f4b11fb
https://hg.mozilla.org/integration/mozilla-inbound/rev/ac349d1b3c10546da0193046d6ce4b7f065eb070
https://hg.mozilla.org/integration/mozilla-inbound/rev/d9c679129b669805d737c09c97a4768a8e6f7e6f
https://hg.mozilla.org/integration/mozilla-inbound/rev/7e9f99645168e37e0f7298faebeba3e263491bbc
https://hg.mozilla.org/integration/mozilla-inbound/rev/c5a67edeb6239cc576be71fc8ec4955e544a4ca4
https://hg.mozilla.org/integration/mozilla-inbound/rev/e419e663860780657e7825bd7a0108e414c1a134
https://hg.mozilla.org/integration/mozilla-inbound/rev/e0730d3f61026ed2d45b4f339b7a1082199bcedb
https://hg.mozilla.org/integration/mozilla-inbound/rev/ebd1c1823d617cabfc57d3d9325f2be4a28330ec

First not busted push which exposes the failure: https://treeherder.mozilla.org/#/jobs?repo=mozilla-inbound&revision=a171aae3ae491dd52e184735c51924c7a467a0bf
Failure log: https://treeherder.mozilla.org/logviewer.html#?job_id=38420599&repo=mozilla-inbound

01:36:25     INFO - REFTEST TEST-UNEXPECTED-FAIL | file:///C:/slave/test/build/tests/reftest/tests/layout/reftests/selection/splitText-normalize.html | load failed: timed out waiting for pending paint count to reach zero (waiting for MozAfterPaint)
Flags: needinfo?(wmccloskey)

Comment 15

3 years ago
Pushed by wmccloskey@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/815e8f226bb9
Allow LinkedList to hold RefPtr elements (r=froydnj)
https://hg.mozilla.org/integration/mozilla-inbound/rev/b30dfbf5fe2a
Add removeAndGetNext/Previous methods to LinkedList (r=froydnj)

Comment 16

3 years ago
bugherder
https://hg.mozilla.org/mozilla-central/rev/815e8f226bb9
https://hg.mozilla.org/mozilla-central/rev/b30dfbf5fe2a
Status: NEW → RESOLVED
Closed: 3 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla52
Flags: needinfo?(wmccloskey)
You need to log in before you can comment on or make changes to this bug.