Closed Bug 1311277 Opened 9 years ago Closed 9 years ago

Add move assignment support to LinkedList

Categories

(Core :: MFBT, defect)

Product:
Core
Component:
MFBT
Type:
defect
Priority:
Not set
Severity:
normal

Tracking

()

Status:
RESOLVED FIXED
Milestone:
mozilla52
Tracking Flags:
Tracking Status
firefox52 --- fixed

People

(Reporter: TYLin, Assigned: TYLin)

References

Details

Attachments

(4 files)

Bug 1311277 Part 1 - Convert |other| argument to Mozilla coding style.
58 bytes, text/x-review-board-request
froydnj
: review+
Details
Bug 1311277 Part 2 - Add move assignment for LinkedListElement and LinkedList.
58 bytes, text/x-review-board-request
froydnj
: review+
Details
Bug 1311277 Part 3 - Use LinkedList's move assignment in FCItemIterator::AppendItemsToList.
58 bytes, text/x-review-board-request
froydnj
: review+
Details
Bug 1311277 Part 4 - Convert NodeKind to be an enum class.
58 bytes, text/x-review-board-request
froydnj
: review+
Details
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
status-firefox52: affected → ---
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.

Attachment

General

Creator:
Created:
Updated:
Size: