1309445 - Convert FrameConstructionItemList::mItems to use mozilla::LinkedList

Status: RESOLVED FIXED

(Core :: Layout, defect)

Description

[Ting-Yu Lin [:TYLin] (PDT, UTC-7)]

Spin off per bug 1304441 comment 24.

Comment 1

[Ting-Yu Lin [:TYLin] (PDT, UTC-7)]

Attachment: Bug 1309445 - Convert FrameConstructionItemList::mItems to use mozilla::LinkedList.

The major change to the Iterator is due to the fact that the end of an
LinkedList is represented by nullptr.

Also delete some conversion functions which are no longer needed.

Review commit: https://reviewboard.mozilla.org/r/86642/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/86642/

Comment 2

[Ting-Yu Lin [:TYLin] (PDT, UTC-7)]

Comment on attachment 8802120 [details]
Bug 1309445 - Convert FrameConstructionItemList::mItems to use mozilla::LinkedList.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/86642/diff/1-2/

Comment 3

[Ting-Yu Lin [:TYLin] (PDT, UTC-7)]

Comment on attachment 8802120 [details]
Bug 1309445 - Convert FrameConstructionItemList::mItems to use mozilla::LinkedList.

https://reviewboard.mozilla.org/r/86642/#review85868

::: layout/base/nsCSSFrameConstructor.cpp:12819
(Diff revision 2)
> -  // move over the list of items
> -  PR_INSERT_AFTER(&aTargetList.mItems, &mList.mItems);
> -  // Need to init when we remove to makd ~FrameConstructionItemList work right.
> -  PR_REMOVE_AND_INIT_LINK(&mList.mItems);
> +  // Move our entire list of items into the empty target list.
> +  // XXX: If LinkedList supports move assignment, we could use
> +  // aTargetList.mItems = Move(mList.mItems);
> +  aTargetList.mItems.~LinkedList<FrameConstructionItem>();
> +  new (&aTargetList.mItems) LinkedList<FrameConstructionItem>(
> +    Move(mList.mItems));

We need to move list in O(1) time. I filed bug 1311277 to support move assignment in LinkedList. If the idea and implementation is sound, my patches Part 3 in that bug converts the above lines to `aTargetList.mItems = Move(mList.mItems);`

Comment 4

[Daniel Holbert [:dholbert]]

Comment on attachment 8802120 [details]
Bug 1309445 - Convert FrameConstructionItemList::mItems to use mozilla::LinkedList.

https://reviewboard.mozilla.org/r/86642/#review85960

Typo in extended commit message:
  s/an/a/ (in "end of an LinkedList")

::: layout/base/nsCSSFrameConstructor.h
(Diff revision 2)
> -        mEnd(aOther.mEnd),
>          mList(aOther.mList)
>        {}
>  
>        bool operator==(const Iterator& aOther) const {
> -        NS_ASSERTION(mEnd == aOther.mEnd, "Iterators for different lists?");

Can we preserve this assertion, but simply be asserting that &mList == &aOther.mList?

::: layout/base/nsCSSFrameConstructor.h
(Diff revision 2)
>        }
>        bool operator!=(const Iterator& aOther) const {
>          return !(*this == aOther);
>        }
>        Iterator& operator=(const Iterator& aOther) {
> -        NS_ASSERTION(mEnd == aOther.mEnd, "Iterators for different lists?");

(Same here - can we preserve this assertion but just make it about &mList == &aOther.mList?)

::: layout/base/nsCSSFrameConstructor.cpp
(Diff revision 2)
>  nsCSSFrameConstructor::FrameConstructionItemList::
>  Iterator::AppendItemsToList(const Iterator& aEnd,
>                              FrameConstructionItemList& aTargetList)
>  {
>    NS_ASSERTION(&aTargetList != &mList, "Unexpected call");
> -  NS_PRECONDITION(mEnd == aEnd.mEnd, "end iterator for some other list?");

Please preserve this assertion, and just make it about mList instead of mEnd.

I think this should work:
  NS_PRECONDITION(&mList == &aEnd.mList, ...);

::: layout/base/nsCSSFrameConstructor.cpp:12837
(Diff revision 2)
> -  mCurrent = mEnd = &mList.mItems;
> +  mCurrent = aEnd.mCurrent;
>    NS_POSTCONDITION(*this == aEnd, "How did that happen?");

I think the mCurrent assignment would be clearer/more direct as:
  mCurrent = nullptr;

The current assignment seems like we might actually be assigning it to some other pointer value -- but really, we know it's nullptr (and it better darn well be nullptr, or else we're in trouble).

(This is the chunk where we're clearing out our list entirely, which means we should be left with an iterator that's pointing at the end of an empty list, i.e. with mCurrent == nullptr.  And aEnd.mCurrent must necessarily be nullptr, based on the "!aEnd.IsDone()" early-return higher up in this function. And we're already enforcing that in an assertion, via the NS_POSTCONDITION here.)

::: layout/base/nsCSSFrameConstructor.cpp:12845
(Diff revision 2)
> +  if (IsDone()) {
> +    mList.mItems.insertBack(aItem);
> +    mCurrent = mList.mItems.getFirst();

Why are we setting mCurrent to the beginning of the list here?

This does not seem to match the old behavior, nor does it match what the function is documented as doing in this IsDone() case...
https://dxr.mozilla.org/mozilla-central/rev/90d8afaddf9150853b0b68b35b30c1e54a8683e7/layout/base/nsCSSFrameConstructor.h#1010-1013

If the mCurrent assignment were removed (i.e. if we left mCurrent pointing at nullptr in this case), then I think this would be correct...  Though maybe I'm missing something.  (This is the only piece I'm genuinely confused about & which is keeping this from being "r+ with nits addressed", BTW.)

::: layout/base/nsCSSFrameConstructor.cpp
(Diff revision 2)
>  
>  void
>  nsCSSFrameConstructor::FrameConstructionItemList::
>  Iterator::DeleteItemsTo(const Iterator& aEnd)
>  {
> -  NS_PRECONDITION(mEnd == aEnd.mEnd, "end iterator for some other list?");

As above, please preserve this assertion and make it about mList, like so:
  NS_PRECONDITION(&mList == &aEnd.mList, ...);

Comment 5

[Ting-Yu Lin [:TYLin] (PDT, UTC-7)]

Comment on attachment 8802120 [details]
Bug 1309445 - Convert FrameConstructionItemList::mItems to use mozilla::LinkedList.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/86642/diff/2-3/

Comment 6

[Ting-Yu Lin [:TYLin] (PDT, UTC-7)]

Comment on attachment 8802120 [details]
Bug 1309445 - Convert FrameConstructionItemList::mItems to use mozilla::LinkedList.

https://reviewboard.mozilla.org/r/86642/#review85960

I've preserved and modified all the assertions as requested. Thank you.

> I think the mCurrent assignment would be clearer/more direct as:
>   mCurrent = nullptr;
> 
> The current assignment seems like we might actually be assigning it to some other pointer value -- but really, we know it's nullptr (and it better darn well be nullptr, or else we're in trouble).
> 
> (This is the chunk where we're clearing out our list entirely, which means we should be left with an iterator that's pointing at the end of an empty list, i.e. with mCurrent == nullptr.  And aEnd.mCurrent must necessarily be nullptr, based on the "!aEnd.IsDone()" early-return higher up in this function. And we're already enforcing that in an assertion, via the NS_POSTCONDITION here.)

You're right. Our list will be cleared in this case, so mCurrent is nullptr. We happen to have `SetToEnd()` for this, and use the method should be clearer.

> Why are we setting mCurrent to the beginning of the list here?
> 
> This does not seem to match the old behavior, nor does it match what the function is documented as doing in this IsDone() case...
> https://dxr.mozilla.org/mozilla-central/rev/90d8afaddf9150853b0b68b35b30c1e54a8683e7/layout/base/nsCSSFrameConstructor.h#1010-1013
> 
> If the mCurrent assignment were removed (i.e. if we left mCurrent pointing at nullptr in this case), then I think this would be correct...  Though maybe I'm missing something.  (This is the only piece I'm genuinely confused about & which is keeping this from being "r+ with nits addressed", BTW.)

Thank you for catching this bug! We shouldn't change the fact that the iterator is done. It's correct to call `mList.mItems.insertBack(aItem)` as documented, but should leave mCurrent as being a nullptr;

Comment 7

[Daniel Holbert [:dholbert]]

Comment on attachment 8802120 [details]
Bug 1309445 - Convert FrameConstructionItemList::mItems to use mozilla::LinkedList.

https://reviewboard.mozilla.org/r/86642/#review86286

Thanks! This looks good. r=me

Comment 8

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/1aec2f248ad2
Convert FrameConstructionItemList::mItems to use mozilla::LinkedList. r=dholbert

Comment 9

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/1aec2f248ad2