67686 2011-09-06 17:38:50 -0700 Optimize Node::isInShadowTree to execute in constant-time 2011-10-24 23:41:29 -0700 1 1 1 Unclassified WebKit New Bugs 528+ (Nightly build) Unspecified Unspecified RESOLVED FIXED P2 Normal --- 70649 1 adamk adamk dglazkov dominicc rafaelw rolandsteiner webkit.review.bot oldest_to_newest 463017 0 adamk 2011-09-06 17:38:50 -0700 Optimize Node::isInShadowTree to execute in constant-time 463018 1 106525 adamk 2011-09-06 17:39:52 -0700 Created attachment 106525 Patch 463024 2 106525 dominicc 2011-09-06 17:52:58 -0700 Comment on attachment 106525 Patch Awesome. 463026 3 adamk 2011-09-06 17:59:03 -0700 I should ask: do y'all know of a particular test that might exercise isInShadowTree()? There are only a few callers... 463093 4 dglazkov 2011-09-06 19:45:02 -0700 (In reply to comment #3) > I should ask: do y'all know of a particular test that might exercise isInShadowTree()? There are only a few callers... Let's just write one. 463439 5 adamk 2011-09-07 10:44:35 -0700 (In reply to comment #4) > (In reply to comment #3) > > I should ask: do y'all know of a particular test that might exercise isInShadowTree()? There are only a few callers... > > Let's just write one. That'll require finding an entry point I understand :). The clearest usage is in HTMLLinkElement; it looks like that call was added for http://trac.webkit.org/changeset/77834, and I've run the test that patch was meant to fix (svg/dom/use-transform.svg). It passes without crashing. The other two usages are in editing/range code and in SVGTrefElement, neither of which I'm familiar enough with to exercise. Let me know if you've got something in mind... 463457 6 rolandsteiner 2011-09-07 11:01:52 -0700 Unless someone changed SVG while I wasn't looking, this won't work for SVG, because SVG doesn't use TreeScope yet. Indeed, SVG is the only reason why we still have various functions climbing the tree to look for, e.g., the host element (Node::shadowTreeRootNode et al) rather than doing O(1) access. 463612 7 dominicc 2011-09-07 13:33:26 -0700 You could still fast-path the in new-style shadow case as a prefix. Maybe if you’re willing to assume SVG elements don’t display non-SVG children (pretty sure I have seen that elsewhere in SVG shadow walking code) you could test !isSVGElement and predicate the fast path on that. 463613 8 dglazkov 2011-09-07 13:35:17 -0700 This could be a bug in existing code, but it already ignores SVG shadow roots. So I think this change doesn't make things worse. Right? 463617 9 rolandsteiner 2011-09-07 13:39:54 -0700 (In reply to comment #8) IIRC isShadowRoot() works for both new-style shadows and SVG shadows. 488654 10 rafaelw 2011-10-21 14:17:57 -0700 This blocks an important optimization for mutation observers 488987 11 dominicc 2011-10-22 20:08:34 -0700 (In reply to comment #9) > IIRC isShadowRoot() works for both new-style shadows and SVG shadows. No it doesn't; look at the definition of isShadowRoot. Adam: Any reason not to R? this patch. It looks good to me. 489483 12 adamk 2011-10-24 11:39:41 -0700 (In reply to comment #11) > (In reply to comment #9) > > IIRC isShadowRoot() works for both new-style shadows and SVG shadows. > > No it doesn't; look at the definition of isShadowRoot. > > Adam: Any reason not to R? this patch. It looks good to me. Only Roland's comments, pushed back to R?. 489580 13 106525 webkit.review.bot 2011-10-24 13:40:42 -0700 Comment on attachment 106525 Patch Clearing flags on attachment: 106525 Committed r98275: <http://trac.webkit.org/changeset/98275> 489581 14 webkit.review.bot 2011-10-24 13:40:47 -0700 All reviewed patches have been landed. Closing bug. 489828 15 rolandsteiner 2011-10-24 18:41:26 -0700 (In reply to comment #11) > (In reply to comment #9) > > IIRC isShadowRoot() works for both new-style shadows and SVG shadows. > > No it doesn't; look at the definition of isShadowRoot. That definition has changed since I made the comment! And I wonder if we haven't introduced a bug here: If I reconstruct this correctly, isInShadowTree is used in SVG at least by SVGTRefElement. This used to climb the tree looking for isShadowRoot, which used to be set for both SVG and new-style shadow roots. With the changes that isShadowRoot no longer applies for SVG and the shortcut introduced here, this is probably broken (?). 489887 16 dominicc 2011-10-24 23:41:29 -0700 (In reply to comment #15) > (In reply to comment #11) > > (In reply to comment #9) > > > IIRC isShadowRoot() works for both new-style shadows and SVG shadows. > > > > No it doesn't; look at the definition of isShadowRoot. > > That definition has changed since I made the comment! Can you point to when it changed? I don't think it has. > And I wonder if we haven't introduced a bug here: If there a bug, it was probably introduced in this revision: <http://trac.webkit.org/changeset/84225> so maybe we should re-review that. > If I reconstruct this correctly, isInShadowTree is used in SVG at least by SVGTRefElement. This used to climb the tree looking for isShadowRoot, which used to be set for both SVG and new-style shadow roots. With the changes that isShadowRoot no longer applies for SVG and the shortcut introduced here, this is probably broken (?). Yes, it looks broken to me. (Looks like I broke it.) 106525 2011-09-06 17:39:52 -0700 2011-10-24 13:40:41 -0700 Patch bug-67686-20110906173951.patch text/plain 1301 adamk U3VidmVyc2lvbiBSZXZpc2lvbjogOTQ2MTMKZGlmZiAtLWdpdCBhL1NvdXJjZS9XZWJDb3JlL0No YW5nZUxvZyBiL1NvdXJjZS9XZWJDb3JlL0NoYW5nZUxvZwppbmRleCA4MmFlNWFiZjQ5YTU0MTE2 MTE5NWRlMWE3NDEwOWJmNmIzZGVmMTdmLi5lMDQ0Y2RmYTdjYjg2YzMyOTNiNWIxYTdjYzA3MmFl ZTg2MjE3MzFlIDEwMDY0NAotLS0gYS9Tb3VyY2UvV2ViQ29yZS9DaGFuZ2VMb2cKKysrIGIvU291 cmNlL1dlYkNvcmUvQ2hhbmdlTG9nCkBAIC0xLDMgKzEsMTUgQEAKKzIwMTEtMDktMDYgIEFkYW0g S2xlaW4gIDxhZGFta0BjaHJvbWl1bS5vcmc+CisKKyAgICAgICAgT3B0aW1pemUgTm9kZTo6aXNJ blNoYWRvd1RyZWUgdG8gZXhlY3V0ZSBpbiBjb25zdGFudC10aW1lCisgICAgICAgIGh0dHBzOi8v YnVncy53ZWJraXQub3JnL3Nob3dfYnVnLmNnaT9pZD02NzY4NgorCisgICAgICAgIFJldmlld2Vk IGJ5IE5PQk9EWSAoT09QUyEpLgorCisgICAgICAgIE5vIGV4cGVjdGVkIGNoYW5nZSBpbiBiZWhh dmlvciwgc28gbm8gbmV3IHRlc3RzLgorCisgICAgICAgICogZG9tL05vZGUuY3BwOgorICAgICAg ICAoV2ViQ29yZTo6Tm9kZTo6aXNJblNoYWRvd1RyZWUpOgorCiAyMDExLTA5LTA2ICBSeW9zdWtl IE5pd2EgIDxybml3YUB3ZWJraXQub3JnPgogCiAgICAgICAgIFJlbmFtZSBjb25maXJtQ29tcG9z aXRpb25XaXRob3V0RGlzdHVyYmluZ1NlbGVjdGlvbiB0byBjYW5jZWxDb21wb3NpdGlvbgpkaWZm IC0tZ2l0IGEvU291cmNlL1dlYkNvcmUvZG9tL05vZGUuY3BwIGIvU291cmNlL1dlYkNvcmUvZG9t L05vZGUuY3BwCmluZGV4IDBlOGNiYWZhYzA1YWVmZjk1YTJkNDNiNGViODdjYWFjMTcwNmY5NTYu LjY3MDBlYmQ2MjcwZDYyMzc1YzM0MDM4YzJiZjZjZTAwZDg1YjIwYjMgMTAwNjQ0Ci0tLSBhL1Nv dXJjZS9XZWJDb3JlL2RvbS9Ob2RlLmNwcAorKysgYi9Tb3VyY2UvV2ViQ29yZS9kb20vTm9kZS5j cHAKQEAgLTE1ODcsMTAgKzE1ODcsNyBAQCBDb250YWluZXJOb2RlKiBOb2RlOjpub25TaGFkb3dC b3VuZGFyeVBhcmVudE5vZGUoKSBjb25zdAogCiBib29sIE5vZGU6OmlzSW5TaGFkb3dUcmVlKCkK IHsKLSAgICBmb3IgKE5vZGUqIG4gPSB0aGlzOyBuOyBuID0gbi0+cGFyZW50Tm9kZSgpKQotICAg ICAgICBpZiAobi0+aXNTaGFkb3dSb290KCkpCi0gICAgICAgICAgICByZXR1cm4gdHJ1ZTsKLSAg ICByZXR1cm4gZmFsc2U7CisgICAgcmV0dXJuIHRyZWVTY29wZSgpICE9IGRvY3VtZW50KCk7CiB9 CiAKIEVsZW1lbnQqIE5vZGU6OnBhcmVudE9ySG9zdEVsZW1lbnQoKSBjb25zdAo=