117388 2013-06-09 18:50:40 -0700 Add special tree walking for the single tag or class CSS query selectors 2013-06-10 01:04:19 -0700 1 1 1 Unclassified WebKit New Bugs 528+ (Nightly build) Unspecified Unspecified RESOLVED FIXED P2 Normal --- 1 benjamin benjamin allan.jensen commit-queue esprehn+autocc glenn macpherson menard rniwa oldest_to_newest 898530 0 benjamin 2013-06-09 18:50:40 -0700 Add special tree walking for the single tag or class CSS query selectors 898531 1 204132 benjamin 2013-06-09 18:53:52 -0700 Created attachment 204132 Patch 898537 2 204132 rniwa 2013-06-09 20:11:35 -0700 Comment on attachment 204132 Patch View in context: https://bugs.webkit.org/attachment.cgi?id=204132&action=review > Source/WebCore/dom/SelectorQuery.cpp:228 > const SelectorData& selectorData = m_selectors[0]; Maybe we should consider the case where we have multiple selectors as a special case instead? It might also make sense to apply these optimizations to each selector even when we have multiple selectors. e.g. #hello, #world shouldn't be doing a tree traversal if #hello and #world didn't have multiple matching elements. 898539 3 benjamin 2013-06-09 20:26:51 -0700 > Maybe we should consider the case where we have multiple selectors as a special case instead? > It might also make sense to apply these optimizations to each selector even when we have multiple selectors. > e.g. #hello, #world shouldn't be doing a tree traversal if #hello and #world didn't have multiple matching elements. Since we need to preserve the order, we cannot apply the optimizations on each selector in the case of multiselector. "#hello, #world", or "#hello a, #hello b" are interesting cases. We should look into that. 898541 4 rniwa 2013-06-09 20:33:48 -0700 (In reply to comment #3) > > Maybe we should consider the case where we have multiple selectors as a special case instead? > > It might also make sense to apply these optimizations to each selector even when we have multiple selectors. > > e.g. #hello, #world shouldn't be doing a tree traversal if #hello and #world didn't have multiple matching elements. > > Since we need to preserve the order, we cannot apply the optimizations on each selector in the case of multiselector. > > "#hello, #world", or "#hello a, #hello b" are interesting cases. We should look into that. Suppose we have selectors #id_1, #id_2, #id_3, ... #id_n and each id_n resolves to exactly one element e_n, then we should be able to sort e_1, etc... e_n in O(k n log n) where k is the depth of the tree. 898571 5 benjamin 2013-06-10 01:04:19 -0700 Committed r151365: <http://trac.webkit.org/changeset/151365> 204132 2013-06-09 18:53:52 -0700 2013-06-09 20:11:35 -0700 Patch bug-117388-20130609185215.patch text/plain 6907 benjamin U3VidmVyc2lvbiBSZXZpc2lvbjogMTUxMzU5CmRpZmYgLS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9D aGFuZ2VMb2cgYi9Tb3VyY2UvV2ViQ29yZS9DaGFuZ2VMb2cKaW5kZXggZDY1NjhmOWU0NmZjY2E4 NThkYzMyNDBmNzcwMTkzMWNkNmIyZTg4My4uYTk2MDBiNzE5NWMyNTBjNGFmYTNkYTFiYTg3OWNi N2Q5M2EyZTUwMyAxMDA2NDQKLS0tIGEvU291cmNlL1dlYkNvcmUvQ2hhbmdlTG9nCisrKyBiL1Nv dXJjZS9XZWJDb3JlL0NoYW5nZUxvZwpAQCAtMSwzICsxLDI4IEBACisyMDEzLTA2LTA5ICBCZW5q YW1pbiBQb3VsYWluICA8YmVuamFtaW5Ad2Via2l0Lm9yZz4KKworICAgICAgICBBZGQgc3BlY2lh bCB0cmVlIHdhbGtpbmcgZm9yIHRoZSBzaW5nbGUgdGFnIG9yIGNsYXNzIENTUyBxdWVyeSBzZWxl Y3RvcnMKKyAgICAgICAgaHR0cHM6Ly9idWdzLndlYmtpdC5vcmcvc2hvd19idWcuY2dpP2lkPTEx NzM4OAorCisgICAgICAgIFJldmlld2VkIGJ5IE5PQk9EWSAoT09QUyEpLgorCisgICAgICAgIFF1 ZXJpZXMgZm9yIGEgc2luZ2xlIHRhZyBuYW1lIG9yIGEgc2luZ2xlIGNsYXNzIG5hbWUgYXJlIHRo ZSBtb3N0IGNvbW1vbgorICAgICAgICBpbnB1dCBvZiBxdWVyeVNlbGVjdG9yLgorCisgICAgICAg IFRoaXMgcGF0Y2ggYWRkcyBhIHNpbXBsaWZpZWQgdHJlZSB3YWxraW5nIGluIHRob3NlIGNhc2Vz LCBvbmx5IGNoZWNraW5nIHRoYXQgcGFydGljdWxhcgorICAgICAgICBjYXNlIGluc3RlYWQgb2Yg YSBmdWxsIHNlbGVjdG9yLgorCisgICAgICAgIFdpdGggdGhlIGNoYW5nZSwgdGhlIGJhbGFuY2Vk IHF1ZXJ5IHNlbGVjdG9yIGJlbmNobWFya3MgYmVjb21lIDExJSBmYXN0ZXIuCisKKyAgICAgICAg KiBjc3MvU2VsZWN0b3JDaGVja2VyRmFzdFBhdGguY3BwOgorICAgICAgICAoV2ViQ29yZTo6SFRN TE5hbWVzOjpjaGVja0NsYXNzVmFsdWUpOgorICAgICAgICAqIGRvbS9TZWxlY3RvclF1ZXJ5LmNw cDoKKyAgICAgICAgKFdlYkNvcmU6OmlzU2luZ2xlVGFnTmFtZVNlbGVjdG9yKToKKyAgICAgICAg KFdlYkNvcmU6OlNlbGVjdG9yRGF0YUxpc3Q6OmV4ZWN1dGVTaW5nbGVUYWdOYW1lU2VsZWN0b3JE YXRhKToKKyAgICAgICAgKFdlYkNvcmU6OmlzU2luZ2xlQ2xhc3NOYW1lU2VsZWN0b3IpOgorICAg ICAgICAoV2ViQ29yZTo6U2VsZWN0b3JEYXRhTGlzdDo6ZXhlY3V0ZVNpbmdsZUNsYXNzTmFtZVNl bGVjdG9yRGF0YSk6CisgICAgICAgIChXZWJDb3JlOjpTZWxlY3RvckRhdGFMaXN0OjpleGVjdXRl KToKKyAgICAgICAgKiBkb20vU2VsZWN0b3JRdWVyeS5oOgorCiAyMDEzLTA2LTA5ICBCZW5qYW1p biBQb3VsYWluICA8YnBvdWxhaW5AYXBwbGUuY29tPgogCiAgICAgICAgIFNwbGl0IHRoZSAzIHBh dGhzIG9mIFNlbGVjdG9yRGF0YUxpc3Q6OmV4ZWN1dGUoKSBpbnRvIDMgc2VwYXJhdGUgZnVuY3Rp b25zCmRpZmYgLS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9jc3MvU2VsZWN0b3JDaGVja2VyRmFzdFBh dGguY3BwIGIvU291cmNlL1dlYkNvcmUvY3NzL1NlbGVjdG9yQ2hlY2tlckZhc3RQYXRoLmNwcApp bmRleCAxOWE0NjYxOTc5MDI5MDljZWFjMjA0YmJmYjU5NzEyNzcwYjU0Mzg4Li5hN2U2ZmJlZWU2 MjNlODAzM2JlZGE1NDBhZGVkZGY4MTIwNGI2MmQyIDEwMDY0NAotLS0gYS9Tb3VyY2UvV2ViQ29y ZS9jc3MvU2VsZWN0b3JDaGVja2VyRmFzdFBhdGguY3BwCisrKyBiL1NvdXJjZS9XZWJDb3JlL2Nz cy9TZWxlY3RvckNoZWNrZXJGYXN0UGF0aC5jcHAKQEAgLTc1LDcgKzc1LDcgQEAgaW5saW5lIGJv b2wgZmFzdENoZWNrU2luZ2xlU2VsZWN0b3IoY29uc3QgQ1NTU2VsZWN0b3IqJiBzZWxlY3Rvciwg Y29uc3QgRWxlbWVudCoKIAogaW5saW5lIGJvb2wgY2hlY2tDbGFzc1ZhbHVlKGNvbnN0IEVsZW1l bnQqIGVsZW1lbnQsIGNvbnN0IENTU1NlbGVjdG9yKiBzZWxlY3RvcikKIHsKLSAgICByZXR1cm4g ZWxlbWVudC0+aGFzQ2xhc3MoKSAmJiBzdGF0aWNfY2FzdDxjb25zdCBTdHlsZWRFbGVtZW50Kj4o ZWxlbWVudCktPmNsYXNzTmFtZXMoKS5jb250YWlucyhzZWxlY3Rvci0+dmFsdWUoKS5pbXBsKCkp OworICAgIHJldHVybiBlbGVtZW50LT5oYXNDbGFzcygpICYmIHN0YXRpY19jYXN0PGNvbnN0IFN0 eWxlZEVsZW1lbnQqPihlbGVtZW50KS0+Y2xhc3NOYW1lcygpLmNvbnRhaW5zKHNlbGVjdG9yLT52 YWx1ZSgpKTsKIH0KIAogaW5saW5lIGJvb2wgY2hlY2tJRFZhbHVlKGNvbnN0IEVsZW1lbnQqIGVs ZW1lbnQsIGNvbnN0IENTU1NlbGVjdG9yKiBzZWxlY3RvcikKZGlmZiAtLWdpdCBhL1NvdXJjZS9X ZWJDb3JlL2RvbS9TZWxlY3RvclF1ZXJ5LmNwcCBiL1NvdXJjZS9XZWJDb3JlL2RvbS9TZWxlY3Rv clF1ZXJ5LmNwcAppbmRleCA0NGUwNTA1NGE5ZGI2MjkwMDc0ZGFiNTk3MDRlNTA2MmZjYzBkZGI0 Li45MjY0NWQ1ZWZjNDVmNWI4ZmRiODFkZGE2NTMyMDBiZTZmZTY5NWRmIDEwMDY0NAotLS0gYS9T b3VyY2UvV2ViQ29yZS9kb20vU2VsZWN0b3JRdWVyeS5jcHAKKysrIGIvU291cmNlL1dlYkNvcmUv ZG9tL1NlbGVjdG9yUXVlcnkuY3BwCkBAIC0xLDUgKzEsNSBAQAogLyoKLSAqIENvcHlyaWdodCAo QykgMjAxMSBBcHBsZSBJbmMuIEFsbCByaWdodHMgcmVzZXJ2ZWQuCisgKiBDb3B5cmlnaHQgKEMp IDIwMTEsIDIwMTMgQXBwbGUgSW5jLiBBbGwgcmlnaHRzIHJlc2VydmVkLgogICoKICAqIFJlZGlz dHJpYnV0aW9uIGFuZCB1c2UgaW4gc291cmNlIGFuZCBiaW5hcnkgZm9ybXMsIHdpdGggb3Igd2l0 aG91dAogICogbW9kaWZpY2F0aW9uLCBhcmUgcGVybWl0dGVkIHByb3ZpZGVkIHRoYXQgdGhlIGZv bGxvd2luZyBjb25kaXRpb25zCkBAIC0xNDksNiArMTQ5LDQ4IEBAIEFMV0FZU19JTkxJTkUgdm9p ZCBTZWxlY3RvckRhdGFMaXN0OjpleGVjdXRlRmFzdFBhdGhGb3JJZFNlbGVjdG9yKGNvbnN0IE5v ZGUqIHJvCiAgICAgICAgIG1hdGNoZWRFbGVtZW50cy5hcHBlbmQoZWxlbWVudCk7CiB9CiAKK3N0 YXRpYyBib29sIGlzU2luZ2xlVGFnTmFtZVNlbGVjdG9yKGNvbnN0IENTU1NlbGVjdG9yKiBzZWxl Y3RvcikKK3sKKyAgICByZXR1cm4gc2VsZWN0b3ItPmlzTGFzdEluVGFnSGlzdG9yeSgpICYmIHNl bGVjdG9yLT5tX21hdGNoID09IENTU1NlbGVjdG9yOjpUYWc7Cit9CisKK3RlbXBsYXRlIDxib29s IGZpcnN0TWF0Y2hPbmx5PgorQUxXQVlTX0lOTElORSB2b2lkIFNlbGVjdG9yRGF0YUxpc3Q6OmV4 ZWN1dGVTaW5nbGVUYWdOYW1lU2VsZWN0b3JEYXRhKGNvbnN0IE5vZGUqIHJvb3ROb2RlLCBjb25z dCBTZWxlY3RvckRhdGEmIHNlbGVjdG9yRGF0YSwgVmVjdG9yPFJlZlB0cjxOb2RlPiA+JiBtYXRj aGVkRWxlbWVudHMpIGNvbnN0Cit7CisgICAgQVNTRVJUKG1fc2VsZWN0b3JzLnNpemUoKSA9PSAx KTsKKyAgICBBU1NFUlQoaXNTaW5nbGVUYWdOYW1lU2VsZWN0b3Ioc2VsZWN0b3JEYXRhLnNlbGVj dG9yKSk7CisKKyAgICBjb25zdCBRdWFsaWZpZWROYW1lJiB0YWdRdWFsaWZpZWROYW1lID0gc2Vs ZWN0b3JEYXRhLnNlbGVjdG9yLT50YWdRTmFtZSgpOworICAgIGZvciAoRWxlbWVudCogZWxlbWVu dCA9IEVsZW1lbnRUcmF2ZXJzYWw6OmZpcnN0V2l0aGluKHJvb3ROb2RlKTsgZWxlbWVudDsgZWxl bWVudCA9IEVsZW1lbnRUcmF2ZXJzYWw6Om5leHQoZWxlbWVudCwgcm9vdE5vZGUpKSB7CisgICAg ICAgIGlmIChTZWxlY3RvckNoZWNrZXI6OnRhZ01hdGNoZXMoZWxlbWVudCwgdGFnUXVhbGlmaWVk TmFtZSkpIHsKKyAgICAgICAgICAgIG1hdGNoZWRFbGVtZW50cy5hcHBlbmQoZWxlbWVudCk7Cisg ICAgICAgICAgICBpZiAoZmlyc3RNYXRjaE9ubHkpCisgICAgICAgICAgICAgICAgcmV0dXJuOwor ICAgICAgICB9CisgICAgfQorfQorCitzdGF0aWMgYm9vbCBpc1NpbmdsZUNsYXNzTmFtZVNlbGVj dG9yKGNvbnN0IENTU1NlbGVjdG9yKiBzZWxlY3RvcikKK3sKKyAgICByZXR1cm4gc2VsZWN0b3It PmlzTGFzdEluVGFnSGlzdG9yeSgpICYmIHNlbGVjdG9yLT5tX21hdGNoID09IENTU1NlbGVjdG9y OjpDbGFzczsKK30KKwordGVtcGxhdGUgPGJvb2wgZmlyc3RNYXRjaE9ubHk+CitBTFdBWVNfSU5M SU5FIHZvaWQgU2VsZWN0b3JEYXRhTGlzdDo6ZXhlY3V0ZVNpbmdsZUNsYXNzTmFtZVNlbGVjdG9y RGF0YShjb25zdCBOb2RlKiByb290Tm9kZSwgY29uc3QgU2VsZWN0b3JEYXRhJiBzZWxlY3RvckRh dGEsIFZlY3RvcjxSZWZQdHI8Tm9kZT4gPiYgbWF0Y2hlZEVsZW1lbnRzKSBjb25zdAoreworICAg IEFTU0VSVChtX3NlbGVjdG9ycy5zaXplKCkgPT0gMSk7CisgICAgQVNTRVJUKGlzU2luZ2xlQ2xh c3NOYW1lU2VsZWN0b3Ioc2VsZWN0b3JEYXRhLnNlbGVjdG9yKSk7CisKKyAgICBjb25zdCBBdG9t aWNTdHJpbmcmIGNsYXNzTmFtZSA9IHNlbGVjdG9yRGF0YS5zZWxlY3Rvci0+dmFsdWUoKTsKKyAg ICBmb3IgKEVsZW1lbnQqIGVsZW1lbnQgPSBFbGVtZW50VHJhdmVyc2FsOjpmaXJzdFdpdGhpbihy b290Tm9kZSk7IGVsZW1lbnQ7IGVsZW1lbnQgPSBFbGVtZW50VHJhdmVyc2FsOjpuZXh0KGVsZW1l bnQsIHJvb3ROb2RlKSkgeworICAgICAgICBpZiAoZWxlbWVudC0+aGFzQ2xhc3MoKSAmJiBzdGF0 aWNfY2FzdDxjb25zdCBTdHlsZWRFbGVtZW50Kj4oZWxlbWVudCktPmNsYXNzTmFtZXMoKS5jb250 YWlucyhjbGFzc05hbWUpKSB7CisgICAgICAgICAgICBtYXRjaGVkRWxlbWVudHMuYXBwZW5kKGVs ZW1lbnQpOworICAgICAgICAgICAgaWYgKGZpcnN0TWF0Y2hPbmx5KQorICAgICAgICAgICAgICAg IHJldHVybjsKKyAgICAgICAgfQorICAgIH0KK30KKwogdGVtcGxhdGUgPGJvb2wgZmlyc3RNYXRj aE9ubHk+CiBBTFdBWVNfSU5MSU5FIHZvaWQgU2VsZWN0b3JEYXRhTGlzdDo6ZXhlY3V0ZVNpbmds ZVNlbGVjdG9yRGF0YShjb25zdCBOb2RlKiByb290Tm9kZSwgY29uc3QgU2VsZWN0b3JEYXRhJiBz ZWxlY3RvckRhdGEsIFZlY3RvcjxSZWZQdHI8Tm9kZT4gPiYgbWF0Y2hlZEVsZW1lbnRzKSBjb25z dAogewpAQCAtMTg2LDYgKzIyOCwxMCBAQCBBTFdBWVNfSU5MSU5FIHZvaWQgU2VsZWN0b3JEYXRh TGlzdDo6ZXhlY3V0ZShOb2RlKiByb290Tm9kZSwgVmVjdG9yPFJlZlB0cjxOb2RlPgogICAgICAg ICBjb25zdCBTZWxlY3RvckRhdGEmIHNlbGVjdG9yRGF0YSA9IG1fc2VsZWN0b3JzWzBdOwogICAg ICAgICBpZiAoY29uc3QgQ1NTU2VsZWN0b3IqIGlkU2VsZWN0b3IgPSBzZWxlY3RvckZvcklkTG9v a3VwKHJvb3ROb2RlLCBzZWxlY3RvckRhdGEuc2VsZWN0b3IpKQogICAgICAgICAgICAgZXhlY3V0 ZUZhc3RQYXRoRm9ySWRTZWxlY3RvcjxmaXJzdE1hdGNoT25seT4ocm9vdE5vZGUsIHNlbGVjdG9y RGF0YSwgaWRTZWxlY3RvciwgbWF0Y2hlZEVsZW1lbnRzKTsKKyAgICAgICAgZWxzZSBpZiAoaXNT aW5nbGVUYWdOYW1lU2VsZWN0b3Ioc2VsZWN0b3JEYXRhLnNlbGVjdG9yKSkKKyAgICAgICAgICAg IGV4ZWN1dGVTaW5nbGVUYWdOYW1lU2VsZWN0b3JEYXRhPGZpcnN0TWF0Y2hPbmx5Pihyb290Tm9k ZSwgc2VsZWN0b3JEYXRhLCBtYXRjaGVkRWxlbWVudHMpOworICAgICAgICBlbHNlIGlmIChpc1Np bmdsZUNsYXNzTmFtZVNlbGVjdG9yKHNlbGVjdG9yRGF0YS5zZWxlY3RvcikpCisgICAgICAgICAg ICBleGVjdXRlU2luZ2xlQ2xhc3NOYW1lU2VsZWN0b3JEYXRhPGZpcnN0TWF0Y2hPbmx5Pihyb290 Tm9kZSwgc2VsZWN0b3JEYXRhLCBtYXRjaGVkRWxlbWVudHMpOwogICAgICAgICBlbHNlCiAgICAg ICAgICAgICBleGVjdXRlU2luZ2xlU2VsZWN0b3JEYXRhPGZpcnN0TWF0Y2hPbmx5Pihyb290Tm9k ZSwgc2VsZWN0b3JEYXRhLCBtYXRjaGVkRWxlbWVudHMpOwogICAgICAgICByZXR1cm47CmRpZmYg LS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9kb20vU2VsZWN0b3JRdWVyeS5oIGIvU291cmNlL1dlYkNv cmUvZG9tL1NlbGVjdG9yUXVlcnkuaAppbmRleCAzNjRiZWY1ODhjMDZiN2U0YWI1MDY3MmNmY2Iy YTZjYmY2MWIwODU0Li5jYzdiNGY4NDYzODE5Yzg0ZWUxZDcxYWQ4NjU2MTgxMDZjMzEwZjNlIDEw MDY0NAotLS0gYS9Tb3VyY2UvV2ViQ29yZS9kb20vU2VsZWN0b3JRdWVyeS5oCisrKyBiL1NvdXJj ZS9XZWJDb3JlL2RvbS9TZWxlY3RvclF1ZXJ5LmgKQEAgLTYyLDYgKzYyLDggQEAgcHJpdmF0ZToK ICAgICB2b2lkIGV4ZWN1dGUoTm9kZSogcm9vdE5vZGUsIFZlY3RvcjxSZWZQdHI8Tm9kZT4gPiYp IGNvbnN0OwogCiAgICAgdGVtcGxhdGUgPGJvb2wgZmlyc3RNYXRjaE9ubHk+IHZvaWQgZXhlY3V0 ZUZhc3RQYXRoRm9ySWRTZWxlY3Rvcihjb25zdCBOb2RlKiByb290Tm9kZSwgY29uc3QgU2VsZWN0 b3JEYXRhJiwgY29uc3QgQ1NTU2VsZWN0b3IqIGlkU2VsZWN0b3IsIFZlY3RvcjxSZWZQdHI8Tm9k ZT4gPiYpIGNvbnN0OworICAgIHRlbXBsYXRlIDxib29sIGZpcnN0TWF0Y2hPbmx5PiB2b2lkIGV4 ZWN1dGVTaW5nbGVUYWdOYW1lU2VsZWN0b3JEYXRhKGNvbnN0IE5vZGUqIHJvb3ROb2RlLCBjb25z dCBTZWxlY3RvckRhdGEmLCBWZWN0b3I8UmVmUHRyPE5vZGU+ID4mKSBjb25zdDsKKyAgICB0ZW1w bGF0ZSA8Ym9vbCBmaXJzdE1hdGNoT25seT4gdm9pZCBleGVjdXRlU2luZ2xlQ2xhc3NOYW1lU2Vs ZWN0b3JEYXRhKGNvbnN0IE5vZGUqIHJvb3ROb2RlLCBjb25zdCBTZWxlY3RvckRhdGEmLCBWZWN0 b3I8UmVmUHRyPE5vZGU+ID4mKSBjb25zdDsKICAgICB0ZW1wbGF0ZSA8Ym9vbCBmaXJzdE1hdGNo T25seT4gdm9pZCBleGVjdXRlU2luZ2xlU2VsZWN0b3JEYXRhKGNvbnN0IE5vZGUqIHJvb3ROb2Rl LCBjb25zdCBTZWxlY3RvckRhdGEmLCBWZWN0b3I8UmVmUHRyPE5vZGU+ID4mKSBjb25zdDsKICAg ICB0ZW1wbGF0ZSA8Ym9vbCBmaXJzdE1hdGNoT25seT4gdm9pZCBleGVjdXRlU2luZ2xlTXVsdGlT ZWxlY3RvckRhdGEoY29uc3QgTm9kZSogcm9vdE5vZGUsIFZlY3RvcjxSZWZQdHI8Tm9kZT4gPiYp IGNvbnN0OwogCg==