Add unit tests for red-black tree and (POD) arena

• Component: WebKit Misc.
• Status: RESOLVED FIXED

[Kenneth Russell]

The red-black tree being integrated in https://bugs.webkit.org/show_bug.cgi?id=45059 needs unit tests integrated as well.

[Kenneth Russell]

Created attachment 66273 [details]
Patch

Patch incorporating unit tests for PODRedBlackTree. They're currently being incorporated under the Chromium port only because it's this port which has a unit test framework (gtest) available.

[Kenneth Russell]

Created attachment 66288 [details]
Revised patch

Changed EXPECT_TRUE to ASSERT_TRUE in InsertionAndDeletionTest to abort execution upon first failure.

[WebKit Review Bot]

Attachment 66288 [details] did not build on chromium:
Build output: http://queues.webkit.org/results/3933043

[Kenneth Russell]

(In reply to comment #3)
> Attachment 66288 [details] did not build on chromium:
> Build output: http://queues.webkit.org/results/3933043

That's expected, since this can't land before https://bugs.webkit.org/show_bug.cgi?id=45059 .

[Kenneth Russell]

Changing synopsis to indicate that tests for both PODRedBlackTree and PODArena will be added.

[Kenneth Russell]

Created attachment 66460 [details]
Revised patch

Added tests for PODArena, and revised PODRedBlackTreeTests for updated tree API in bug 45059.

[WebKit Review Bot]

Attachment 66460 [details] did not pass style-queue:

Failed to run "['WebKitTools/Scripts/check-webkit-style']" exit_code: 1
WebKit/chromium/tests/PODArenaTest.cpp:57:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
WebKit/chromium/tests/PODArenaTest.cpp:63:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
WebKit/chromium/tests/PODArenaTest.cpp:65:  Consider using ASSERT_GE instead of ASSERT_TRUE(a >= b)  [readability/check] [2]
WebKit/chromium/tests/PODArenaTest.cpp:70:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
WebKit/chromium/tests/PODArenaTest.cpp:71:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
WebKit/chromium/tests/PODArenaTest.cpp:74:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
WebKit/chromium/tests/PODArenaTest.cpp:107:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
WebKit/chromium/tests/PODArenaTest.cpp:116:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
WebKit/chromium/tests/PODArenaTest.cpp:122:  One line control clauses should not use braces.  [whitespace/braces] [4]
WebKit/chromium/tests/PODArenaTest.cpp:129:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
Total errors found: 10 in 6 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Kenneth Russell]

Created attachment 66464 [details]
Revised patch

Fixed style errors in last patch.

[Darin Adler]

Can we please leave this POD prefix off of most of these class names? I don’t think the POD prefix adds anything in almsot every case.

The classes in WTF such as HashMap also have limitations for what objects they work with, but trying to encode those limitations into the class names seems awkward and unpleasant. Unless we have imminent plans to have a second red-black tree.

[Darin Adler]

Chromium-only unit tests seem wrong. We’ve added quite a few unit tests cross-platform by making them triggerable from DumpRenderTree.

It’s not a good direction for the WebKit project to add major new functionality with tests only on a single platform.

[Kenneth Russell]

(In reply to comment #9)
> Can we please leave this POD prefix off of most of these class names? I don’t think the POD prefix adds anything in almsot every case.
> 
> The classes in WTF such as HashMap also have limitations for what objects they work with, but trying to encode those limitations into the class names seems awkward and unpleasant. Unless we have imminent plans to have a second red-black tree.

Darin, I will do my best to eliminate the restrictions on these classes and then remove the POD prefix -- after I have checkpointed the code. Right now I've landed two of the three classes and none of the using code, and to keep my bookkeeping sane I do not want to rename them until I've gotten an initial version of the code checked in, which hopefully should be within a week.

[Kenneth Russell]

(In reply to comment #10)
> Chromium-only unit tests seem wrong. We’ve added quite a few unit tests cross-platform by making them triggerable from DumpRenderTree.
> 
> It’s not a good direction for the WebKit project to add major new functionality with tests only on a single platform.

Could you point me to an example of a unit test that is hooked up in DRT and how it is invoked? I would definitely like to make these tests run on all ports.

[Darin Adler]

(In reply to comment #11)
> Darin, I will do my best to eliminate the restrictions on these classes and then remove the POD prefix

That’s nice to hear. But I think you’re missing my point. Even with the restrictions, the POD prefix is not helpful.

[Kenneth Russell]

(In reply to comment #13)
> (In reply to comment #11)
> > Darin, I will do my best to eliminate the restrictions on these classes and then remove the POD prefix
> 
> That’s nice to hear. But I think you’re missing my point. Even with the restrictions, the POD prefix is not helpful.

I understand your point. I am not prepared to rename these classes until I've checkpointed an initial version of this code so I can use svn and do-webcore-rename to do the work. I'd appreciate your help reviewing these patches modulo the naming convention.

[Darin Adler]

(In reply to comment #14)
> I'd appreciate your help reviewing these patches modulo the naming convention.

I can’t review these classes at all. I don’t understand the big picture. It seems like there is a lot of already working code that you want to get into WebKit as quickly as possible.

[Darin Fisher (:fishd, Google)]

(In reply to comment #15)
> (In reply to comment #14)
> > I'd appreciate your help reviewing these patches modulo the naming convention.
> 
> I can’t review these classes at all. I don’t understand the big picture. It seems like there is a lot of already working code that you want to get into WebKit as quickly as possible.

Hi Darin, yes... Ken is working to contribute his GPU based path renderer, which we discussed with cmarrin, hyatt, smfr, and others in person about a week ago.  These are preliminary patches.  The code will live in graphics/gpu/.

The plan is for Ken to land his code as a check point and then make incremental improvements.

There has been a healthy debate about naming conventions.  We have chosen a naming convention that has issues (the POD prefix), and we are committed to fixing that.  It is easier to rename using the tools in WebKit (that depend on code already being committed), so please bear with us as we take these incremental steps.

The unit test issue is another example.  In the Chromium port we have a well established way of writing unit tests using the Gtest framework.  WebCore seems to lack a good way to unit test basic data structures, but we'd like to find a way to share these unit tests with all ports so that this code will be sure to run properly on all ports.  The existing layout test framework does not seem to be a good fit, or at least it is not obvious how to make it fit.  Regardless, it is useful to check point these unit tests since they are already written and of value to Ken (who is developing this code).  We will figure out how best to make these tests available more universally.  We are taking an incremental path.

[Darin Fisher (:fishd, Google)]

Comment on attachment 66464 [details]
Revised patch

View in context: https://bugs.webkit.org/attachment.cgi?id=66464&action=prettypatch

> WebKit/chromium/tests/PODArenaTest.cpp:32
> +// Tests for the PODArena.
nit: I'd nuke this comment since it is redundant with the file name.

> WebKit/chromium/tests/PODArenaTest.cpp:82
> +protected:
nit: looks like this constructor can just be in the private section

> WebKit/chromium/tests/PODArenaTest.cpp:115
> +    for (int i = 0; i < 10000; ++i)
this choice of 10000 seems to depend on the value of DefaultChunkSize.
maybe you should parameterize this using that value?  this test could
fail if DefaultChunkSize were increased significantly.

> WebKit/chromium/tests/PODRedBlackTreeTest.cpp:44
> +using namespace TreeTestHelpers;
instead of a namespace, I think a class with static methods would be 
better.  it is just uncommon in webkit to use a namespace like this.

> WebKit/chromium/tests/PODRedBlackTreeTest.cpp:147
> +    tree.add(5113);
is there something special about the choice of numbers here?
maybe a comment would be good if so?  elsewhere, you use
smaller numbers :)

> WebKit/chromium/tests/PODRedBlackTreeTest.cpp:168
> +        int val = nextRandom(maximumValue);
nit: spell out "value"

> WebKit/chromium/tests/PODRedBlackTreeTest.cpp:176
> +        int idx = nextRandom(treeSize);
nit: spell out "index" and "value"

[Kenneth Russell]

Created attachment 66565 [details]
Revised patch

Addressed most review feedback; made TrackedAllocator constructor private, added FIXME about DefaultChunkSize, added comment about origin of values in one regression test, and avoided abbreviations in variable names.

[Kenneth Russell]

(In reply to comment #17)
> (From update of attachment 66464 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=66464&action=prettypatch
> 
> > WebKit/chromium/tests/PODArenaTest.cpp:32
> > +// Tests for the PODArena.
> nit: I'd nuke this comment since it is redundant with the file name.

Done.

> > WebKit/chromium/tests/PODArenaTest.cpp:82
> > +protected:
> nit: looks like this constructor can just be in the private section

Done.

> > WebKit/chromium/tests/PODArenaTest.cpp:115
> > +    for (int i = 0; i < 10000; ++i)
> this choice of 10000 seems to depend on the value of DefaultChunkSize.
> maybe you should parameterize this using that value?  this test could
> fail if DefaultChunkSize were increased significantly.

Right now DefaultChunkSize is private, and making this test a friend is really ugly due to gtest's name mangling. I added a FIXME. I hope this will be sufficient for now.

> > WebKit/chromium/tests/PODRedBlackTreeTest.cpp:44
> > +using namespace TreeTestHelpers;
> instead of a namespace, I think a class with static methods would be 
> better.  it is just uncommon in webkit to use a namespace like this.

The std namespace is used in many places in WebKit. The ability to use the TreeTestHelpers namespace rather than prefixing every method call with the class name really cleans up the code, and I'm using this technique elsewhere in forthcoming patches. I'd really rather leave this as is.

> > WebKit/chromium/tests/PODRedBlackTreeTest.cpp:147
> > +    tree.add(5113);
> is there something special about the choice of numbers here?
> maybe a comment would be good if so?  elsewhere, you use
> smaller numbers :)

Added a comment.

> > WebKit/chromium/tests/PODRedBlackTreeTest.cpp:168
> > +        int val = nextRandom(maximumValue);
> nit: spell out "value"

Done.

> > WebKit/chromium/tests/PODRedBlackTreeTest.cpp:176
> > +        int idx = nextRandom(treeSize);
> nit: spell out "index" and "value"

Done.

[Darin Fisher (:fishd, Google)]

(In reply to comment #19)
...
> > > WebKit/chromium/tests/PODArenaTest.cpp:115
> > > +    for (int i = 0; i < 10000; ++i)
> > this choice of 10000 seems to depend on the value of DefaultChunkSize.
> > maybe you should parameterize this using that value?  this test could
> > fail if DefaultChunkSize were increased significantly.
> 
> Right now DefaultChunkSize is private, and making this test a friend is really ugly due to gtest's name mangling. I added a FIXME. I hope this will be sufficient for now.

I was proposing that you make that public so it could be used here.
A FIXME is fine, but please consider making the change now since it
would be pretty trivial.


> > > WebKit/chromium/tests/PODRedBlackTreeTest.cpp:44
> > > +using namespace TreeTestHelpers;
> > instead of a namespace, I think a class with static methods would be 
> > better.  it is just uncommon in webkit to use a namespace like this.
> 
> The std namespace is used in many places in WebKit. The ability to use the TreeTestHelpers namespace rather than prefixing every method call with the class name really cleans up the code, and I'm using this technique elsewhere in forthcoming patches. I'd really rather leave this as is.

This is quite different from the std:: namespace.  The problem I had
when reading this code is that it wasn't obvious where some of these
functions are defined, so I had to go "grepping" for them, which led
me to the namespace.  That is not a problem for very commonly used
classes and functions like what you find in the WTF namespace.

Anyways, I don't feel strongly enough about this.  It was just something
I observed that might not be obvious when one already has all of this
code loaded in one's head.

[Kenneth Russell]

(In reply to comment #20)
> (In reply to comment #19)
> ...
> > > > WebKit/chromium/tests/PODArenaTest.cpp:115
> > > > +    for (int i = 0; i < 10000; ++i)
> > > this choice of 10000 seems to depend on the value of DefaultChunkSize.
> > > maybe you should parameterize this using that value?  this test could
> > > fail if DefaultChunkSize were increased significantly.
> > 
> > Right now DefaultChunkSize is private, and making this test a friend is really ugly due to gtest's name mangling. I added a FIXME. I hope this will be sufficient for now.
> 
> I was proposing that you make that public so it could be used here.
> A FIXME is fine, but please consider making the change now since it
> would be pretty trivial.

OK, I'll make it public and update the tests. Revised patch coming.

> > > > WebKit/chromium/tests/PODRedBlackTreeTest.cpp:44
> > > > +using namespace TreeTestHelpers;
> > > instead of a namespace, I think a class with static methods would be 
> > > better.  it is just uncommon in webkit to use a namespace like this.
> > 
> > The std namespace is used in many places in WebKit. The ability to use the TreeTestHelpers namespace rather than prefixing every method call with the class name really cleans up the code, and I'm using this technique elsewhere in forthcoming patches. I'd really rather leave this as is.
> 
> This is quite different from the std:: namespace.  The problem I had
> when reading this code is that it wasn't obvious where some of these
> functions are defined, so I had to go "grepping" for them, which led
> me to the namespace.  That is not a problem for very commonly used
> classes and functions like what you find in the WTF namespace.
> 
> Anyways, I don't feel strongly enough about this.  It was just something
> I observed that might not be obvious when one already has all of this
> code loaded in one's head.

I see your point. I could add explicit using directives for each of the imported functions so it would be more obvious. I'd really like to keep it as a namespace though.

[Kenneth Russell]

Created attachment 66567 [details]
Revised patch

Made DefaultChunkSize public in arena and use it in unit test rather than magic constant.

[Darin Fisher (:fishd, Google)]

Comment on attachment 66567 [details]
Revised patch

The explicit 'using TestTreeHelpers::nextRandom' and so on would be nice assuming
that works for functions?

R=me

[Kenneth Russell]

(In reply to comment #23)
> (From update of attachment 66567 [details])
> The explicit 'using TestTreeHelpers::nextRandom' and so on would be nice assuming
> that works for functions?

It does; see "using std::max" elsewhere in the source tree, for example. Changed in version to be committed; also fixed incorrect license at top of these files and the other recently checked in ones.

[Kenneth Russell]

Committed r66808: <http://trac.webkit.org/changeset/66808>