1212624 - Implement range-based iteration for LinkedList

Status: RESOLVED FIXED

(Core :: MFBT, defect)

Description

[Steve Fink [:sfink] [:s:]]

The boilerplate, it boils me.

  for (MyType* e = snurf.snazzyList.getFirst(); e; e = e->getNext())
      e.yelp();

Comment 1

[Steve Fink [:sfink] [:s:]]

Attachment: Tests for LinkedList

I think this is prettier:

  for (MyType* e : snurf.snazzyList)
      e.yelp();

and some people will think this is even prettier:

  for (auto e : snurf.snazzyList)
      e.yelp();

Comment 2

[Steve Fink [:sfink] [:s:]]

Attachment: Implement range-based iteration for LinkedList

Oops, pushed the wrong patch last time. That was just the test. This is the actual change. (Still getting used to mq-less bzexport.)

Comment 3

[Steve Fink [:sfink] [:s:]]

Attachment: Use range-based iteration for various LinkedList<T> in spidermonkey

Make use of the shiny new toys within Spidermonkey.

Comment 4

[Steve Fink [:sfink] [:s:]]

Attachment: Make WeakMapBase be a LinkedListElement

And now, what got me started on doing this in the first place. Perhaps this should be in another bug.

Comment 5

[Steve Fink [:sfink] [:s:]]

Attachment: Use range-based iteration for various LinkedList<T> in spidermonkey

Not that it really matters for review, but it looks like I did one of those brilliant last-minute changes and removed a friend declaration that was, y'know, letting it compile.

Comment 6

[Jeff Walden [:Waldo]]

Comment on attachment 8671035 [details] [diff] [review]
Tests for LinkedList

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

Coments apply to all the bits, not just the ones I noted, obviously.

::: mfbt/tests/TestLinkedList.cpp
@@ +10,5 @@
> +using mozilla::LinkedList;
> +using mozilla::LinkedListElement;
> +
> +struct SomeClass : public LinkedListElement<SomeClass> {
> +  int mValue;

unsigned, please.

@@ +26,5 @@
> +{
> +  LinkedList<SomeClass> list;
> +
> +  SomeClass one(1), two(2), three(3);
> +  

Remove all the trailing WS.

@@ +34,5 @@
> +  MOZ_RELEASE_ASSERT(!list.popFirst());
> +  MOZ_RELEASE_ASSERT(!list.popLast());
> +
> +  {
> +    int count = 0;

Use unsigned for these counts, please.

@@ +36,5 @@
> +
> +  {
> +    int count = 0;
> +    for (SomeClass* x : list) {
> +      x = x; // Suppress warning

MOZ_RELEASE_ASSERT(x, "can't have null elements in a list"); instead of this -- seems a slightly more sensible test.

@@ +87,5 @@
> +    }
> +  }
> +
> +  MOZ_RELEASE_ASSERT(list.getFirst()->mValue == 3);
> +  MOZ_RELEASE_ASSERT(list.getLast()->mValue == 4);

Add a couple removes (middle, then back, then front) and verify mValues and loop counts?  To cover the bases, mostly.

@@ +97,5 @@
> +  LinkedList<PrivateClass> list;
> +  PrivateClass one, two;
> +  list.insertBack(&one);
> +  list.insertBack(&two);
> +  for (PrivateClass* p : list) {

Blank line before the loop, and do a count == 2 check.

Comment 7

[Jeff Walden [:Waldo]]

Comment on attachment 8671039 [details] [diff] [review]
Implement range-based iteration for LinkedList

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

::: mfbt/LinkedList.h
@@ +405,5 @@
>  
>    /*
> +   * Allow range-based iterator:
> +   *
> +   *     for (auto& elt : myList) { ... }

Is there a reason to encourage &-binding here?  I assume you get the usual bind-ref-to-temp lifetime extension behavior, so this is safe.  But it seems like it's generally safer to encourage creation/use of copies, and for people to do ref-binding as the exception.

Comment 8

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

https://developer.mozilla.org/en-US/docs/Using_CXX_in_Mozilla_code recommends using refs with range-based for loops, FWIW.

Comment 9

[Jeff Walden [:Waldo]]

Comment on attachment 8671041 [details] [diff] [review]
Make WeakMapBase be a LinkedListElement

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

::: js/src/jsweakmap.cpp
@@ +123,1 @@
>          MOZ_ASSERT(m->isInList() && m->marked);

Brace this and split it into separate assertions, for debuggability?

::: js/src/jsweakmap.h
@@ +7,5 @@
>  #ifndef jsweakmap_h
>  #define jsweakmap_h
>  
>  #include "mozilla/Move.h"
> +#include "mozilla/LinkedList.h"

check-style no likey

Comment 10

[Jeff Walden [:Waldo]]

Hmm.  So I think that link is more in the mood of assuming a person's going to question what to use in *every* case.  Which is good advice.  Maybe just remove the |auto| suggestion at all in that comment, so people aren't led into one particular thing and have to question?

Comment 11

[Steve Fink [:sfink] [:s:]]

(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #7)
> Comment on attachment 8671039 [details] [diff] [review]
> Implement range-based iteration for LinkedList
> 
> Review of attachment 8671039 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: mfbt/LinkedList.h
> @@ +405,5 @@
> >  
> >    /*
> > +   * Allow range-based iterator:
> > +   *
> > +   *     for (auto& elt : myList) { ... }
> 
> Is there a reason to encourage &-binding here?  I assume you get the usual
> bind-ref-to-temp lifetime extension behavior, so this is safe.  But it seems
> like it's generally safer to encourage creation/use of copies, and for
> people to do ref-binding as the exception.

I was just wrong here. First, I personally think it's a bad idea to use auto at all here, because the documentation of the type is very important: if you were using range-based iteration over an array, you would be getting a reference to each element. Here, you are getting a *pointer* to each element. In all of the places I updated, it was much better to specify the exact type to make it clear what was going on.

And then there's the minor point that auto& doesn't even compile. Which is a good thing, since it would allow mutating the list structure by assigning to it. But instead, the compiler will barf about trying to cast a T* rvalue to a T*&.

Changed to

  /*
   * Allow range-based iteration:
   *
   *     for (MyElementType* elt : myList) { ... }
   */

Comment 12

[Emanuel Hoogeveen [:ehoogeveen]]

IIRC you can just use use auto&& to avoid getting an lvalue (and avoid copies in some cases), though that's not really relevant for pointers.

Comment 13

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/4f499d30a0e0
https://hg.mozilla.org/integration/mozilla-inbound/rev/f73fca35daad
https://hg.mozilla.org/integration/mozilla-inbound/rev/379edefa8e47
https://hg.mozilla.org/integration/mozilla-inbound/rev/0d7a968d2d64

Comment 14

[Pulsebot]

Backout:
https://hg.mozilla.org/integration/mozilla-inbound/rev/7c0c549a1a10

Comment 15

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/8b1831b24cea
https://hg.mozilla.org/integration/mozilla-inbound/rev/8aba07c1a690
https://hg.mozilla.org/integration/mozilla-inbound/rev/5dfeaa81f035
https://hg.mozilla.org/integration/mozilla-inbound/rev/0085266cdfd3

Comment 16

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/8b1831b24cea
https://hg.mozilla.org/mozilla-central/rev/8aba07c1a690
https://hg.mozilla.org/mozilla-central/rev/5dfeaa81f035
https://hg.mozilla.org/mozilla-central/rev/0085266cdfd3