Closed Bug 1311277 Opened 3 years ago Closed 3 years ago

Add move assignment support to LinkedList

Categories

(Core :: MFBT, defect)

defect
Not set

Tracking

()

RESOLVED FIXED
mozilla52
Tracking Status
firefox52 --- fixed

People

(Reporter: TYLin, Assigned: TYLin)

References

Details

Attachments

(4 files)

While converting PRCList to mozilla::LinkedList in Bug 1309445, I find that I need a O(1) operation to append all the elements from one list to another empty list to rewrite [1] while retaining the performance. 

Currently, LinkedList supports only move constructor. While move assignment is not explicit deleted, perhaps it's not a bad idea to support it.

[1] http://searchfox.org/mozilla-central/rev/d96317a351af8aa78ab9847e7feed964bbaac7d7/layout/base/nsCSSFrameConstructor.cpp#12815-12818
See Also: → 1309445
Comment on attachment 8802436 [details]
Bug 1311277 Part 1 - Convert |other| argument to Mozilla coding style.

https://reviewboard.mozilla.org/r/86820/#review85906
Attachment #8802436 - Flags: review?(nfroyd) → review+
Comment on attachment 8802437 [details]
Bug 1311277 Part 2 - Add move assignment for LinkedListElement and LinkedList.

https://reviewboard.mozilla.org/r/86822/#review85912

I have no problem with making `LinkedList` move-assignable (I'm a little surprised it didn't get added when we made it move-constructable), but we need to think a little harder about how `LinkedListElement` is going to play nicely with this so that people don't write bad code.  I'd welcome a double-check on my logic, though, so feel free to push back if you think I got some aspect of this wrong.

::: mfbt/LinkedList.h:136
(Diff revision 2)
> -      return;
> -    }
> +  }
>  
> -    MOZ_ASSERT(aOther.mNext->mPrev == &aOther);
> -    MOZ_ASSERT(aOther.mPrev->mNext == &aOther);
> -
> +  LinkedListElement& operator=(LinkedListElement<T>&& aOther)
> +  {
> +    MOZ_ASSERT(mIsSentinel == aOther.mIsSentinel, "Mismatch NodeKind!");

This part strikes me as incorrect.  It's clearly safe to move sentinel nodes, but what about other kinds of nodes?  For instance, let's say we have two objects that implement `LinkedListElement<T>`, `x` and `y`.  Consider what `*x = Move(*y)` should do when:

1. `x` and `y` are both not part of a list?  This seems safe.
2. `x` is not part of a list, but `y` is?  I think this is OK, since this is analogous to move construction.
2. When `x` is already part of a list, regardless of `y`'s status?  This seems like we're asking for trouble.

I think we want a stronger assertion here.  (Actually, I think what we *really* want is to make the move constructor and assignment operator of `LinkedListElement<T>` private, but I'm not sure we can get away with that.)

::: mfbt/LinkedList.h:279
(Diff revision 2)
> +    if (!aOther.isInList()) {
> +      mNext = this;
> +      mPrev = this;
> +      return;
> +    }

This code was only valid when we were initializing a `LinkedListElement<T>` object; now we have to deal with the case where `this` might already be in a list.  (It would be OK if `this` wasn't in a list per the comment above, but we haven't really assured ourselves of that yet, also per the comment above.)

::: mfbt/LinkedList.h:345
(Diff revision 2)
>      : sentinel(mozilla::Move(aOther.sentinel))
>    { }
>  
> +  LinkedList& operator=(LinkedList<T>&& aOther)
> +  {
> +    MOZ_ASSERT(isEmpty(), "Assign to a non-empty list leaks elements in that list!");

Nit: "Assigning to a non-empty list..."

::: mfbt/tests/TestLinkedList.cpp:121
(Diff revision 2)
>    MOZ_RELEASE_ASSERT(list.getFirst()->mValue == 3);
>    MOZ_RELEASE_ASSERT(list.getLast()->mValue == 4);
> +
> +  LinkedList<SomeClass> list2;
> +  list2 = Move(list);
> +  { unsigned int check[] { 3, 4 }; CheckListValues(list2, check); }

Thank you for writing tests!

We should assert that `list` is empty here, too.
Attachment #8802437 - Flags: review?(nfroyd) → review-
Comment on attachment 8802438 [details]
Bug 1311277 Part 3 - Use LinkedList's move assignment in FCItemIterator::AppendItemsToList.

https://reviewboard.mozilla.org/r/86824/#review85936
Attachment #8802438 - Flags: review?(nfroyd) → review+
Comment on attachment 8802437 [details]
Bug 1311277 Part 2 - Add move assignment for LinkedListElement and LinkedList.

https://reviewboard.mozilla.org/r/86822/#review85912

> This part strikes me as incorrect.  It's clearly safe to move sentinel nodes, but what about other kinds of nodes?  For instance, let's say we have two objects that implement `LinkedListElement<T>`, `x` and `y`.  Consider what `*x = Move(*y)` should do when:
> 
> 1. `x` and `y` are both not part of a list?  This seems safe.
> 2. `x` is not part of a list, but `y` is?  I think this is OK, since this is analogous to move construction.
> 2. When `x` is already part of a list, regardless of `y`'s status?  This seems like we're asking for trouble.
> 
> I think we want a stronger assertion here.  (Actually, I think what we *really* want is to make the move constructor and assignment operator of `LinkedListElement<T>` private, but I'm not sure we can get away with that.)

Making move constructor and assignment operator of LinkedListElement<T> private is probably too strict since it deprives the usage of constructing an LinkedListElement<T> from a return-by-value factory function.

I agree that all the issues come from `x` is already part of a list.  I think we could further assert that `x` must not being in a list. I cannot think of a real use case that one wants to move assign to a `x` wich is already in a list.

Even with the above constraint, another possible footgun is that `y` is already in a list. After `Move`, `x` effectively becomes part of the list while `y` is removed from the list. If the life time of `x` is shorter than `y`, this could lead to some surprise. It's safe however since element removes from the list automatically in the destructor. I guess in most of the cases, LinkedListElement<T> lives on heap, user is unlikely hit this situation. I'm not sure we want forbid this, so I add a documentation.

> This code was only valid when we were initializing a `LinkedListElement<T>` object; now we have to deal with the case where `this` might already be in a list.  (It would be OK if `this` wasn't in a list per the comment above, but we haven't really assured ourselves of that yet, also per the comment above.)

Per comment above, if we only allow `this` not being in a list, this is OK.

> Thank you for writing tests!
> 
> We should assert that `list` is empty here, too.

I add a test for list's move constructor, and construct element from a factory function. Thank you!
(In reply to Ting-Yu Lin [:TYLin] (UTC+8) from comment #13)
> Comment on attachment 8802437 [details]
> Bug 1311277 Part 2 - Add move assignment for LinkedListElement and
> LinkedList.
> 
> https://reviewboard.mozilla.org/r/86822/#review85912
> 
> > This part strikes me as incorrect.  It's clearly safe to move sentinel nodes, but what about other kinds of nodes?  For instance, let's say we have two objects that implement `LinkedListElement<T>`, `x` and `y`.  Consider what `*x = Move(*y)` should do when:
> > 
> > 1. `x` and `y` are both not part of a list?  This seems safe.
> > 2. `x` is not part of a list, but `y` is?  I think this is OK, since this is analogous to move construction.
> > 2. When `x` is already part of a list, regardless of `y`'s status?  This seems like we're asking for trouble.
> > 
> > I think we want a stronger assertion here.  (Actually, I think what we *really* want is to make the move constructor and assignment operator of `LinkedListElement<T>` private, but I'm not sure we can get away with that.)
> 
> Making move constructor and assignment operator of LinkedListElement<T>
> private is probably too strict since it deprives the usage of constructing
> an LinkedListElement<T> from a return-by-value factory function.

That's a good point.  But who's going to do this?  LinkedList<T> only deals with T*, so having non-heap allocated T would be extremely unusual already.  The only case I can think of where you might want something like this would be if you were maintaining a list of things on the stack of a chain of function calls...but even then, you probably don't need the doubly-linked list bit (singly-linked lists will do).

> Even with the above constraint, another possible footgun is that `y` is
> already in a list. After `Move`, `x` effectively becomes part of the list
> while `y` is removed from the list. If the life time of `x` is shorter than
> `y`, this could lead to some surprise. It's safe however since element
> removes from the list automatically in the destructor. I guess in most of
> the cases, LinkedListElement<T> lives on heap, user is unlikely hit this
> situation. I'm not sure we want forbid this, so I add a documentation.

I think this case works out OK.
OK, test code is going to allocate LinkedListElement<T> subclasses on the stack.  But that's just test code, which can be easily fixed.
Comment on attachment 8802857 [details]
Bug 1311277 Part 4 - Convert NodeKind to be an enum class.

https://reviewboard.mozilla.org/r/87136/#review86384
Attachment #8802857 - Flags: review?(nfroyd) → review+
Comment on attachment 8802437 [details]
Bug 1311277 Part 2 - Add move assignment for LinkedListElement and LinkedList.

https://reviewboard.mozilla.org/r/86822/#review86390

r=me with the documentation bit below.

::: mfbt/LinkedList.h:129
(Diff revision 3)
> +   * Note: Suppose aOther is already in a list. After move construction or
> +   * assignment, |*this| is effectively being in the list, and |aOther| is
> +   * removed from the list.

Let's modify this just a bit:

Moves |aOther| into |*this|.  If |aOther| is already in a list, then |aOther| is removed from the list and replaced by |*this|.
Attachment #8802437 - Flags: review?(nfroyd) → review+
Comment on attachment 8802437 [details]
Bug 1311277 Part 2 - Add move assignment for LinkedListElement and LinkedList.

https://reviewboard.mozilla.org/r/86822/#review86390

> Let's modify this just a bit:
> 
> Moves |aOther| into |*this|.  If |aOther| is already in a list, then |aOther| is removed from the list and replaced by |*this|.

Documentation updated. Thank you for the review!
Patch part 3 depends on Bug 1309445.
Depends on: 1309445
See Also: 1309445
Pushed by tlin@mozilla.com:
https://hg.mozilla.org/integration/autoland/rev/8cf3c1b52fac
Part 1 - Convert |other| argument to Mozilla coding style. r=froydnj
https://hg.mozilla.org/integration/autoland/rev/ba5d30bdad0d
Part 2 - Add move assignment for LinkedListElement and LinkedList. r=froydnj
https://hg.mozilla.org/integration/autoland/rev/d6bd5ef77aeb
Part 3 - Use LinkedList's move assignment in FCItemIterator::AppendItemsToList. r=froydnj
https://hg.mozilla.org/integration/autoland/rev/2626096d6704
Part 4 - Convert NodeKind to be an enum class. r=froydnj
You need to log in before you can comment on or make changes to this bug.