Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
148473003:
Begin getting rid of the recursion in the various RenderObject methods (Closed)
|
Created:
6 years, 11 months ago by atreat Modified:
6 years, 11 months ago CC:
blink-reviews, bemjb+rendering_chromium.org, zoltan1, eae+blinkwatch, leviw+renderwatch, jchaffraix+rendering, lgombos Base URL:
https://chromium.googlesource.com/chromium/blink.git@master Visibility:
Public. |
DescriptionBegin getting rid of the recursion in the various RenderObject methods
Begin getting rid of the recursion in the various RenderObject methods dealing
with layout. Recursion is a common pattern found throughout the render tree and
used indiscriminately when a non-recursive pattern would work just as well and
the code is just as clean.
BUG=331879
R=esprehn, eseidel
Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=165892
Patch Set 1 #
Total comments: 2
Patch Set 2 : Don't ascend to the root object! #Messages
Total messages: 13 (0 generated)
Please have a look. There are many more recursive utility methods throughout the render tree where I would like to do something very similar. In the future, I'd also like to see if some of these methods can be combined so that we do not have so many tree traversals for stuff like just marking various bits of state in the tree.
https://codereview.chromium.org/148473003/diff/1/Source/core/rendering/Render... File Source/core/rendering/RenderObject.cpp (right): https://codereview.chromium.org/148473003/diff/1/Source/core/rendering/Render... Source/core/rendering/RenderObject.cpp:289: for (RenderObject *object = this; object; object = object->nextInPreOrder()) { drive by comment: From someone new to the rendering code, the original version of this is easier to understand what will be affected by the iteration. I'm not sure I'd have realized (assuming I hadn't seen this patch go in) the nextInPreOrder() from the current object is the same as looking at all the descendants. Is this just to get rid of the recursion, or are there other factors that make the new version better?
https://codereview.chromium.org/148473003/diff/1/Source/core/rendering/Render... File Source/core/rendering/RenderObject.cpp (right): https://codereview.chromium.org/148473003/diff/1/Source/core/rendering/Render... Source/core/rendering/RenderObject.cpp:289: for (RenderObject *object = this; object; object = object->nextInPreOrder()) { This is not correct, nextInPreOrder() will walk all the way up to the RenderView since you don't pass a scope. You need object->nextInPreOrder(this)
On 2014/01/27 20:44:37, esprehn wrote: > https://codereview.chromium.org/148473003/diff/1/Source/core/rendering/Render... > File Source/core/rendering/RenderObject.cpp (right): > > https://codereview.chromium.org/148473003/diff/1/Source/core/rendering/Render... > Source/core/rendering/RenderObject.cpp:289: for (RenderObject *object = this; > object; object = object->nextInPreOrder()) { > This is not correct, nextInPreOrder() will walk all the way up to the RenderView > since you don't pass a scope. > > You need object->nextInPreOrder(this) Indeed. Nice catch. Unfortunately we don't have a test to cover this kind of mistake.
On 2014/01/27 20:21:55, dsinclair wrote:I'm not > sure I'd have realized (assuming I hadn't seen this patch go in) the > nextInPreOrder() from the current object is the same as looking at all the > descendants. > > Is this just to get rid of the recursion, or are there other factors that make > the new version better? Is that because the name 'nextInPreOrder' ?? Does that not imply that we are traversing the tree to you? Perhaps it should be 'traverseNextInPreOrder' ?
On 2014/01/27 20:49:16, atreat wrote: > On 2014/01/27 20:21:55, dsinclair wrote:I'm not > > sure I'd have realized (assuming I hadn't seen this patch go in) the > > nextInPreOrder() from the current object is the same as looking at all the > > descendants. > > > > Is this just to get rid of the recursion, or are there other factors that make > > the new version better? > > Is that because the name 'nextInPreOrder' ?? Does that not imply that we are > traversing the tree to you? > > Perhaps it should be 'traverseNextInPreOrder' ? It implies we're getting the next thing in the tree, just that the recursive version is a lot clearer, at least me me, as to what we're getting.
On 2014/01/27 20:44:37, esprehn wrote: > https://codereview.chromium.org/148473003/diff/1/Source/core/rendering/Render... > File Source/core/rendering/RenderObject.cpp (right): > > https://codereview.chromium.org/148473003/diff/1/Source/core/rendering/Render... > Source/core/rendering/RenderObject.cpp:289: for (RenderObject *object = this; > object; object = object->nextInPreOrder()) { > This is not correct, nextInPreOrder() will walk all the way up to the RenderView > since you don't pass a scope. > > You need object->nextInPreOrder(this) Fixed!
lgtm
CQ is trying da patch. Follow status at https://chromium-status.appspot.com/cq/adam.treat@samsung.com/148473003/2
On 2014/01/27 20:55:06, dsinclair wrote: > On 2014/01/27 20:49:16, atreat wrote: > > On 2014/01/27 20:21:55, dsinclair wrote:I'm not > > > sure I'd have realized (assuming I hadn't seen this patch go in) the > > > nextInPreOrder() from the current object is the same as looking at all the > > > descendants. > > > > > > Is this just to get rid of the recursion, or are there other factors that > make > > > the new version better? > > > > Is that because the name 'nextInPreOrder' ?? Does that not imply that we are > > traversing the tree to you? > > > > Perhaps it should be 'traverseNextInPreOrder' ? > > > It implies we're getting the next thing in the tree, just that the recursive > version is a lot clearer, at least me me, as to what we're getting. Hmm. This is traversing the tree in pre-order although I don't think whether it is pre-order or post-order actually matters. I just left it as pre-order because that is what the code was doing before. Any suggestion as to how to make it clearer? And yes, this is really about getting rid of the recursion whose motivations are described in the associated bug. Not to mention that non-recursion is faster.
On 2014/01/27 21:12:15, atreat wrote: > On 2014/01/27 20:55:06, dsinclair wrote: > > On 2014/01/27 20:49:16, atreat wrote: > > > On 2014/01/27 20:21:55, dsinclair wrote:I'm not > > > > sure I'd have realized (assuming I hadn't seen this patch go in) the > > > > nextInPreOrder() from the current object is the same as looking at all the > > > > descendants. > > > > > > > > Is this just to get rid of the recursion, or are there other factors that > > make > > > > the new version better? > > > > > > Is that because the name 'nextInPreOrder' ?? Does that not imply that we > are > > > traversing the tree to you? > > > > > > Perhaps it should be 'traverseNextInPreOrder' ? > > > > > > It implies we're getting the next thing in the tree, just that the recursive > > version is a lot clearer, at least me me, as to what we're getting. > > Hmm. This is traversing the tree in pre-order although I don't think whether it > is pre-order or post-order actually matters. I just left it as pre-order > because that is what the code was doing before. Any suggestion as to how to > make it clearer? I don't have any better suggestions. The code as it is now (with the 'this' param) is clearer. I think my confusing came from, it's nextInPreOrder, but next from where? There was no context as to the root of the tree (for some reason I didn't make the assumption it was rooted at the object.) So, I couldn't tell if you were going to iterate over the siblings or just children. It's clearer now that it's nextInPreOrder(this) that we're talking about the tree rooted at 'this'. > And yes, this is really about getting rid of the recursion whose motivations are > described in the associated bug. Not to mention that non-recursion is faster. Cool, makes sense.
CQ is trying da patch. Follow status at https://chromium-status.appspot.com/cq/adam.treat@samsung.com/148473003/2
Message was sent while issue was closed.
Change committed as 165892 |
