734130 - Add comment with public linked list interface to LinkedList.h

Status: RESOLVED WONTFIX

(Core :: MFBT, defect)

Description

[Justin Lebar (not reading bugmail)]

We can fit the whole LinkedList interface into 20 lines or so, which makes using the class much easier than scrolling through the 400-line file looking for method names.

Patch in a moment.

Comment 1

[Justin Lebar (not reading bugmail)]

Attachment: Patch v1

Comment 2

[Jeff Walden [:Waldo]]

Comment on attachment 604085 [details] [diff] [review]
Patch v1

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

::: mfbt/LinkedList.h
@@ +85,5 @@
>   *     }
>   *   };
>   *
> + * 
> + * Here are the public methods on LinkedListElement and LinkedList:

Hmm.  If we want this information, this is one way to address the purpose.  Another way might be to declare all inline methods inline -- but only ever define them out-of-line.  Also we'd stick to some well-defined ordering of fields, public methods, and private methods such that it'd be easy to skim the class definition to see everything, without having to go out of our way to repeat ourselves like this.

Anyway, I'm not necessarily opposed to doing this.  But possibly we should address this concern a different way.  Good fodder for discussion for the new mfbt/STYLE, to which the result of this discussion should likely be added.  Let's rope in a few other people to this before deciding something here.

Comment 3

[Jeff Walden [:Waldo]]

CCing other people to decide on the best way to resolve this style/readability issue...

Comment 4

[Justin Lebar (not reading bugmail)]

> Another way might be to declare all inline methods inline -- but only ever define them out-of-line.

I considered that, but at least in this case, I thought the comment was nicer, because it lets us omit all the private members.  (My goal is an at-a-glance summary of the method names on the class.)  The comment is much denser; the class definitions together are 54 lines, while the comment is 21 lines.

For comparison with the patch, here's what the class definitions would look like:

template<typename T>
class LinkedListElement
{
private:
    LinkedListElement* next;
    LinkedListElement* prev;
    const bool isSentinel;

public:
    LinkedListElement();
    T* getNext();
    T* getPrevious();
    void setNext(T* elem);
    void setPrevious(T* elem);
    void remove();
    bool isInList();

private:
    LinkedListElement& operator=(const LinkedList<T>& other) MOZ_DELETE;
    LinkedListElement(const LinkedList<T>& other) MOZ_DELETE;

    friend class LinkedList<T>;

    enum NodeKind {
        NODE_KIND_NORMAL,
        NODE_KIND_SENTINEL
    };

    LinkedListElement(NodeKind nodeKind);
    T* asT()
    void setNextUnsafe(T* elem)
    void setPreviousUnsafe(T* elem)
};

template<typename T>
class LinkedList
{
private:
    LinkedListElement<T> sentinel;

public:
    LinkedList& operator=(const LinkedList<T>& other) MOZ_DELETE;
    LinkedList(const LinkedList<T>& other) MOZ_DELETE;

    LinkedList();
    void insertFront(T* elem);
    void insertBack(T* elem);
    T* getFirst();
    T* getLast();
    T* popFirst();
    T* popLast();
    bool isEmpty();
    void debugAssertIsSane();
};

An advantage of using the class heading as the summary is that we can't forget a method in the class, while we can forget it in the comment.  I'm not too worried about this, though.  The worst thing that happens is we forget something, someone notices, and then we add it to the comment.

Comment 5

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

I vote for decl + out-of-line defn.

Comment 6

[Justin Lebar (not reading bugmail)]

> Also we'd stick to some well-defined ordering of fields, public methods, and private methods such 
> that it'd be easy to skim the class definition to see everything, without having to go out of our 
> way to repeat ourselves like this.

I guess putting the public members first would be an improvement over what I posted above.  But that still doesn't improve the density in this case, because all of LinkedListElement's members, public and private, come before class LinkedList.

Another consideration is, sometimes we have a somewhat complex inheritance scheme in our collections classes.  Think nsTArray, which inherits from nsTArrayBase.  Or consider Gecko's ridiculous string classes, sprayed out over many files.

I'd love a summary comment laying out all the methods on nsTArray.  But if we instead used the classes themselves as the summary comment, then the public methods of nsTArray would be split between nsTArray and nsTArrayBase, which is an implementation detail.

Comment 7

[:Ms2ger (he/him; ⌚ UTC+1/+2)]

Comment on attachment 604085 [details] [diff] [review]
Patch v1

Looks good enough to me... I wouldn't do the

| template<typename T>
| class LinkedListElement {
|   T* getNext();

thing, though; just

# LinkedListElement:
#   T* getNext()

would probably do.

Also, s/error if !isInList()/only call when isInList()/ or something like that?

Comment 8

[Justin Lebar (not reading bugmail)]

Jeff, what do you think we should do here?

Personally, I'd leave things as they are or add the comment.  I'm not convinced that declaring small methods out of line is a readability improvement.

Comment 9

[Luke Wagner [:luke]]

I like letting the code read like documentation.  To keep things dense, out-of-line definitions make sense, allowing for inline definitions when the body is a trivial one-liner.

As for a useful welcome-get-started-quickly comment, I think it is nice to have a short paragraph that briefly mentions the classes and their purpose at a high level followed by one or more simple samples with explanations.

Comment 10

[Justin Lebar (not reading bugmail)]

> I like letting the code read like documentation.

Me too.  But I don't think the code in comment 4 reads like documentation.  Only half of the lines there are at all related to the public interface.

Comment 11

[Luke Wagner [:luke]]

(In reply to Justin Lebar [:jlebar] from comment #10)
> But I don't think the code in comment 4 reads like documentation.

Well, yeah, it doesn't have any documentation... if you are talking about the extra noise from private definitions, I don't think it is a big deal (although it would be nice to put the public members either all at the beginning or all at the end, on the subject).

Comment 12

[Justin Lebar (not reading bugmail)]

> (although it would be nice to put the public members either all at the beginning or all at the end, 
> on the subject).

I agree.  :)

> But I don't think the code in comment 4 reads like documentation.
>
> Well, yeah, it doesn't have any documentation... if you are talking about the extra noise from 
> private definitions, I don't think it is a big deal

Yes, I'm talking about the noise from the private declarations.  And also the fact that I think the actual code becomes harder to read when your goal is to make the class definition as compact as possible, because you end up out-of-lining a bunch of functions you'd otherwise inline.

My goal was to address the use-case of "I'm using this class, I'm relatively familiar with it, but I don't remember what anything is called."  This happens to me all the time (even with this class, which I wrote), and I don't think we address the ergonomics of this use-case well in our code.

So I wanted a clean and compact representation of the public interface.  You can look up its comment by pressing "*", if you're using a decent editor.  :)

Comment 13

[Justin Lebar (not reading bugmail)]

Sounds like I'm the only person in favor of this.  Oh well.