91320 2012-07-14 03:38:57 -0700 Accessing the last item in children should be a constant time operation 2012-07-14 14:38:44 -0700 1 1 1 Unclassified WebKit DOM 528+ (Nightly build) Unspecified Unspecified RESOLVED FIXED P2 Normal --- 91306 89919 1 rniwa rniwa andersca darin haraken kling koivisto ojan sam oldest_to_newest 669797 0 rniwa 2012-07-14 03:38:57 -0700 element.children[element.children.length - 1] should be a constant time operation with respect to the number of child nodes element has. 669798 1 152418 rniwa 2012-07-14 03:47:56 -0700 Created attachment 152418 Fixes the bug 669800 2 rniwa 2012-07-14 03:48:55 -0700 (provided that the length cache is available). 669806 3 rniwa 2012-07-14 04:13:44 -0700 Once this patch is landed, I'll post the final unification patch that merges DynamicNodeList::item and HTMLCollection::item. 669842 4 152418 ojan 2012-07-14 09:41:50 -0700 Comment on attachment 152418 Fixes the bug View in context: https://bugs.webkit.org/attachment.cgi?id=152418&action=review > Source/WebCore/html/HTMLCollection.cpp:336 > + if (isLengthCacheValid() && supportsItemBefore() && isLastItemCloserThanLastOrCachedItem(offset)) { > + // FIXME: Need to figure out the last offset in array for HTMLFormCollection and HTMLPropertiesCollection > + unsigned unusedOffsetInArray = 0; > + Node* lastItem = itemBefore(unusedOffsetInArray, 0); > + ASSERT(!unusedOffsetInArray); > + ASSERT(lastItem); > + setItemCache(lastItem, cachedLength() - 1, 0); > + } else if (!isItemCacheValid() || isFirstItemCloserThanCachedItem(offset) || (!supportsItemBefore() && offset < cachedItemOffset())) { This would probably be more readable if you had shouldSearchFromFirstItem and shouldSearchFromLastItem helper functions. 669850 5 152418 rniwa 2012-07-14 11:18:29 -0700 Comment on attachment 152418 Fixes the bug View in context: https://bugs.webkit.org/attachment.cgi?id=152418&action=review >> Source/WebCore/html/HTMLCollection.cpp:336 >> + } else if (!isItemCacheValid() || isFirstItemCloserThanCachedItem(offset) || (!supportsItemBefore() && offset < cachedItemOffset())) { > > This would probably be more readable if you had shouldSearchFromFirstItem and shouldSearchFromLastItem helper functions. I did that initially but then realized that the fact such as length is cached, and itemBefore is supported, etc... isn't obvious in the first if statement. Also, if I did add those two functions then I have to assume that either shouldSearchFromFirstItem or shouldSearchFromLastItem is called first since conditions in the function becomes way too complicated otherwise and making such call order assumption seemed error prone. 669870 6 rniwa 2012-07-14 14:38:44 -0700 Committed r122672: <http://trac.webkit.org/changeset/122672> 152418 2012-07-14 03:47:56 -0700 2012-07-14 11:18:29 -0700 Fixes the bug bug-91320-20120714035120.patch text/plain 6873 rniwa SW5kZXg6IFNvdXJjZS9XZWJDb3JlL0NoYW5nZUxvZwo9PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0tLSBTb3VyY2UvV2Vi Q29yZS9DaGFuZ2VMb2cJKHJldmlzaW9uIDEyMjY2NikKKysrIFNvdXJjZS9XZWJDb3JlL0NoYW5n ZUxvZwkod29ya2luZyBjb3B5KQpAQCAtMSwzICsxLDI5IEBACisyMDEyLTA3LTE0ICBSeW9zdWtl IE5pd2EgIDxybml3YUB3ZWJraXQub3JnPgorCisgICAgICAgIEFjY2Vzc2luZyB0aGUgbGFzdCBp dGVtIGluIGNoaWxkcmVuIHNob3VsZCBiZSBhIGNvbnN0YW50IHRpbWUgb3BlcmF0aW9uCisgICAg ICAgIGh0dHBzOi8vYnVncy53ZWJraXQub3JnL3Nob3dfYnVnLmNnaT9pZD05MTMyMAorCisgICAg ICAgIFJldmlld2VkIGJ5IE5PQk9EWSAoT09QUyEpLgorCisgICAgICAgIFRyYXZlcnNlIG5vZGVz IGZyb20gdGhlIGxhc3QgaXRlbSB3aGVuIHRoZSB0YXJnZXQgb2Zmc2V0IHdlJ3JlIGxvb2tpbmcg Zm9yIGlzIGNsb3NlciB0byB0aGUgbGFzdCBpdGVtCisgICAgICAgIHRoYW4gdG8gdGhlIGNhY2hl ZCBpdGVtLiBlLmcuIGlmIHRoZSBjYWNoZWQgaXRlbSB3YXMgYXQgb2Zmc2V0IDAgaW4gdGhlIGNv bGxlY3Rpb24gYW5kIGxlbmd0aCB3YXMgMTAwLAorICAgICAgICB3ZSBzaG91bGQgbm90IGJlIGxv b2tpbmcgZm9yIHRoZSBpdGVtIGF0IG9mZnNldCA5NSBmcm9tIHRoZSBjYWNoZWQgaXRlbS4KKwor ICAgICAgICBOb3RlIHRoYXQgdGhpcyB0cmljayBjYW4gYmUgb25seSB1c2VkIGluIEhUTUwgY29s bGVjdGlvbiB0aGF0IHN1cHBvcnRzIGl0ZW1CZWZvcmUgYW5kIHdoZW4gdGhlIGxlbmd0aAorICAg ICAgICBjYWNoZSBpcyBhdmFpbGFibGUuCisKKyAgICAgICAgQWxzbyBicm9rZSBzaG91bGRTZWFy Y2hGcm9tRmlyc3RJdGVtIGludG8gc21hbGxlciBsb2dpY2FsIHBpZWNlcyB0byBjbGFyaWZ5IHRo ZSBpbnRlbnRzLgorCisgICAgICAgIFRlc3Q6IHBlcmYvaHRtbGNvbGxlY3Rpb24tbGFzdC1pdGVt Lmh0bWwKKworICAgICAgICAqIGh0bWwvSFRNTENvbGxlY3Rpb24uY3BwOgorICAgICAgICAoV2Vi Q29yZSk6CisgICAgICAgIChXZWJDb3JlOjpIVE1MQ29sbGVjdGlvbjo6aXNMYXN0SXRlbUNsb3Nl clRoYW5MYXN0T3JDYWNoZWRJdGVtKToKKyAgICAgICAgKFdlYkNvcmU6OkhUTUxDb2xsZWN0aW9u Ojppc0ZpcnN0SXRlbUNsb3NlclRoYW5DYWNoZWRJdGVtKToKKyAgICAgICAgKFdlYkNvcmU6OkhU TUxDb2xsZWN0aW9uOjppdGVtKToKKyAgICAgICAgKiBodG1sL0hUTUxDb2xsZWN0aW9uLmg6Cisg ICAgICAgIChIVE1MQ29sbGVjdGlvbik6CisKIDIwMTItMDctMTQgIFNoZXJpZmYgQm90ICA8d2Vi a2l0LnJldmlldy5ib3RAZ21haWwuY29tPgogCiAgICAgICAgIFVucmV2aWV3ZWQsIHJvbGxpbmcg b3V0IHIxMjI2MTQuCkluZGV4OiBTb3VyY2UvV2ViQ29yZS9odG1sL0hUTUxDb2xsZWN0aW9uLmNw cAo9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09Ci0tLSBTb3VyY2UvV2ViQ29yZS9odG1sL0hUTUxDb2xsZWN0aW9uLmNwcAko cmV2aXNpb24gMTIyNjYyKQorKysgU291cmNlL1dlYkNvcmUvaHRtbC9IVE1MQ29sbGVjdGlvbi5j cHAJKHdvcmtpbmcgY29weSkKQEAgLTI3MSwxOCArMjcxLDI1IEBAIEVsZW1lbnQqIEhUTUxDb2xs ZWN0aW9uOjppdGVtQWZ0ZXIodW5zaWcKIHsKICAgICByZXR1cm4gaXRlbUJlZm9yZU9yQWZ0ZXI8 dHJ1ZT4odHlwZSgpLCBiYXNlKCksIG9mZnNldEluQXJyYXksIHByZXZpb3VzKTsKIH0KLSAgICAK LWJvb2wgQUxXQVlTX0lOTElORSBIVE1MQ29sbGVjdGlvbjo6c2hvdWxkU2VhcmNoRnJvbUZpcnN0 SXRlbSh1bnNpZ25lZCBvZmZzZXQpIGNvbnN0CisKK2Jvb2wgQUxXQVlTX0lOTElORSBIVE1MQ29s bGVjdGlvbjo6aXNMYXN0SXRlbUNsb3NlclRoYW5MYXN0T3JDYWNoZWRJdGVtKHVuc2lnbmVkIG9m ZnNldCkgY29uc3QKIHsKKyAgICBBU1NFUlQoaXNMZW5ndGhDYWNoZVZhbGlkKCkpOworICAgIHVu c2lnbmVkIGRpc3RhbmNlRnJvbUxhc3RJdGVtID0gY2FjaGVkTGVuZ3RoKCkgLSBvZmZzZXQ7CiAg ICAgaWYgKCFpc0l0ZW1DYWNoZVZhbGlkKCkpCi0gICAgICAgIHJldHVybiB0cnVlOworICAgICAg ICByZXR1cm4gZGlzdGFuY2VGcm9tTGFzdEl0ZW0gPCBvZmZzZXQ7CiAKLSAgICBBU1NFUlQob2Zm c2V0ICE9IGNhY2hlZEl0ZW1PZmZzZXQoKSk7Ci0gICAgaWYgKG9mZnNldCA+IGNhY2hlZEl0ZW1P ZmZzZXQoKSkKKyAgICByZXR1cm4gY2FjaGVkSXRlbU9mZnNldCgpIDwgb2Zmc2V0ICYmIGRpc3Rh bmNlRnJvbUxhc3RJdGVtIDwgb2Zmc2V0IC0gY2FjaGVkSXRlbU9mZnNldCgpOworfQorICAgIAor Ym9vbCBBTFdBWVNfSU5MSU5FIEhUTUxDb2xsZWN0aW9uOjppc0ZpcnN0SXRlbUNsb3NlclRoYW5D YWNoZWRJdGVtKHVuc2lnbmVkIG9mZnNldCkgY29uc3QKK3sKKyAgICBBU1NFUlQoaXNJdGVtQ2Fj aGVWYWxpZCgpKTsKKyAgICBpZiAoY2FjaGVkSXRlbU9mZnNldCgpIDwgb2Zmc2V0KQogICAgICAg ICByZXR1cm4gZmFsc2U7CiAKICAgICB1bnNpZ25lZCBkaXN0YW5jZUZyb21DYWNoZWRJdGVtID0g Y2FjaGVkSXRlbU9mZnNldCgpIC0gb2Zmc2V0OwotICAgIHJldHVybiAhc3VwcG9ydHNJdGVtQmVm b3JlKCkgfHwgb2Zmc2V0IDwgZGlzdGFuY2VGcm9tQ2FjaGVkSXRlbTsKKyAgICByZXR1cm4gb2Zm c2V0IDwgZGlzdGFuY2VGcm9tQ2FjaGVkSXRlbTsKIH0KIAogdW5zaWduZWQgSFRNTENvbGxlY3Rp b246Omxlbmd0aCgpIGNvbnN0CkBAIC0zMTksNyArMzI2LDE0IEBAIE5vZGUqIEhUTUxDb2xsZWN0 aW9uOjppdGVtKHVuc2lnbmVkIG9mZnMKICAgICAgICAgc3RhdGljX2Nhc3Q8Y29uc3QgSFRNTFBy b3BlcnRpZXNDb2xsZWN0aW9uKj4odGhpcyktPnVwZGF0ZVJlZkVsZW1lbnRzKCk7CiAjZW5kaWYK IAotICAgIGlmIChzaG91bGRTZWFyY2hGcm9tRmlyc3RJdGVtKG9mZnNldCkpIHsKKyAgICBpZiAo aXNMZW5ndGhDYWNoZVZhbGlkKCkgJiYgc3VwcG9ydHNJdGVtQmVmb3JlKCkgJiYgaXNMYXN0SXRl bUNsb3NlclRoYW5MYXN0T3JDYWNoZWRJdGVtKG9mZnNldCkpIHsKKyAgICAgICAgLy8gRklYTUU6 IE5lZWQgdG8gZmlndXJlIG91dCB0aGUgbGFzdCBvZmZzZXQgaW4gYXJyYXkgZm9yIEhUTUxGb3Jt Q29sbGVjdGlvbiBhbmQgSFRNTFByb3BlcnRpZXNDb2xsZWN0aW9uCisgICAgICAgIHVuc2lnbmVk IHVudXNlZE9mZnNldEluQXJyYXkgPSAwOworICAgICAgICBOb2RlKiBsYXN0SXRlbSA9IGl0ZW1C ZWZvcmUodW51c2VkT2Zmc2V0SW5BcnJheSwgMCk7CisgICAgICAgIEFTU0VSVCghdW51c2VkT2Zm c2V0SW5BcnJheSk7CisgICAgICAgIEFTU0VSVChsYXN0SXRlbSk7CisgICAgICAgIHNldEl0ZW1D YWNoZShsYXN0SXRlbSwgY2FjaGVkTGVuZ3RoKCkgLSAxLCAwKTsKKyAgICB9IGVsc2UgaWYgKCFp c0l0ZW1DYWNoZVZhbGlkKCkgfHwgaXNGaXJzdEl0ZW1DbG9zZXJUaGFuQ2FjaGVkSXRlbShvZmZz ZXQpIHx8ICghc3VwcG9ydHNJdGVtQmVmb3JlKCkgJiYgb2Zmc2V0IDwgY2FjaGVkSXRlbU9mZnNl dCgpKSkgewogICAgICAgICB1bnNpZ25lZCBvZmZzZXRJbkFycmF5ID0gMDsKICAgICAgICAgTm9k ZSogZmlyc3RJdGVtID0gaXRlbUFmdGVyKG9mZnNldEluQXJyYXksIDApOwogICAgICAgICBpZiAo IWZpcnN0SXRlbSkgewpAQCAtMzI4LDEwICszNDIsMTEgQEAgTm9kZSogSFRNTENvbGxlY3Rpb246 Oml0ZW0odW5zaWduZWQgb2ZmcwogICAgICAgICB9CiAgICAgICAgIHNldEl0ZW1DYWNoZShmaXJz dEl0ZW0sIDAsIG9mZnNldEluQXJyYXkpOwogICAgICAgICBBU1NFUlQoIWNhY2hlZEl0ZW1PZmZz ZXQoKSk7Ci0gICAgICAgIGlmICghb2Zmc2V0KQotICAgICAgICAgICAgcmV0dXJuIGNhY2hlZEl0 ZW0oKTsKICAgICB9CiAKKyAgICBpZiAoY2FjaGVkSXRlbU9mZnNldCgpID09IG9mZnNldCkKKyAg ICAgICAgcmV0dXJuIGNhY2hlZEl0ZW0oKTsKKwogICAgIHJldHVybiBpdGVtQmVmb3JlT3JBZnRl ckNhY2hlZEl0ZW0ob2Zmc2V0KTsKIH0KIApJbmRleDogU291cmNlL1dlYkNvcmUvaHRtbC9IVE1M Q29sbGVjdGlvbi5oCj09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIFNvdXJjZS9XZWJDb3JlL2h0bWwvSFRNTENvbGxl Y3Rpb24uaAkocmV2aXNpb24gMTIyNjYyKQorKysgU291cmNlL1dlYkNvcmUvaHRtbC9IVE1MQ29s bGVjdGlvbi5oCSh3b3JraW5nIGNvcHkpCkBAIC0xMTUsNyArMTE1LDggQEAgcHJpdmF0ZToKICAg ICBib29sIGNoZWNrRm9yTmFtZU1hdGNoKEVsZW1lbnQqLCBib29sIGNoZWNrTmFtZSwgY29uc3Qg QXRvbWljU3RyaW5nJiBuYW1lKSBjb25zdDsKIAogICAgIEVsZW1lbnQqIGl0ZW1CZWZvcmUodW5z aWduZWQmIG9mZnNldEluQXJyYXksIEVsZW1lbnQqKSBjb25zdDsKLSAgICBib29sIHNob3VsZFNl YXJjaEZyb21GaXJzdEl0ZW0odW5zaWduZWQgb2Zmc2V0KSBjb25zdDsKKyAgICBib29sIGlzTGFz dEl0ZW1DbG9zZXJUaGFuTGFzdE9yQ2FjaGVkSXRlbSh1bnNpZ25lZCBvZmZzZXQpIGNvbnN0Owor ICAgIGJvb2wgaXNGaXJzdEl0ZW1DbG9zZXJUaGFuQ2FjaGVkSXRlbSh1bnNpZ25lZCBvZmZzZXQp IGNvbnN0OwogICAgIEVsZW1lbnQqIGl0ZW1CZWZvcmVPckFmdGVyQ2FjaGVkSXRlbSh1bnNpZ25l ZCBvZmZzZXQpIGNvbnN0OwogCiAgICAgUmVmUHRyPE5vZGU+IG1fYmFzZTsKSW5kZXg6IExheW91 dFRlc3RzL0NoYW5nZUxvZwo9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0tLSBMYXlvdXRUZXN0cy9DaGFuZ2VMb2cJKHJl dmlzaW9uIDEyMjY2NikKKysrIExheW91dFRlc3RzL0NoYW5nZUxvZwkod29ya2luZyBjb3B5KQpA QCAtMSwzICsxLDE1IEBACisyMDEyLTA3LTE0ICBSeW9zdWtlIE5pd2EgIDxybml3YUB3ZWJraXQu b3JnPgorCisgICAgICAgIEFjY2Vzc2luZyB0aGUgbGFzdCBpdGVtIGluIGNoaWxkcmVuIHNob3Vs ZCBiZSBhIGNvbnN0YW50IHRpbWUgb3BlcmF0aW9uCisgICAgICAgIGh0dHBzOi8vYnVncy53ZWJr aXQub3JnL3Nob3dfYnVnLmNnaT9pZD05MTMyMAorCisgICAgICAgIFJldmlld2VkIGJ5IE5PQk9E WSAoT09QUyEpLgorCisgICAgICAgIEFkZGVkIGFuIGFzeW1wdG90aWMgdGltZSBjb21wbGV4aXR5 IHRlc3QuCisKKyAgICAgICAgKiBwZXJmL2h0bWxjb2xsZWN0aW9uLWxhc3QtaXRlbS1leHBlY3Rl ZC50eHQ6IEFkZGVkLgorICAgICAgICAqIHBlcmYvaHRtbGNvbGxlY3Rpb24tbGFzdC1pdGVtLmh0 bWw6IEFkZGVkLgorCiAyMDEyLTA3LTE0ICBSb2JlcnQgSG9nYW4gIDxyb2JlcnRAd2Via2l0Lm9y Zz4KIAogICAgICAgICBTa2lwIHRlc3QgYWRkZWQgaW4gcjEyMjY2MyBvbiBRdCBhbmQgR1RLCklu ZGV4OiBMYXlvdXRUZXN0cy9wZXJmL2h0bWxjb2xsZWN0aW9uLWxhc3QtaXRlbS1leHBlY3RlZC50 eHQKPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PQotLS0gTGF5b3V0VGVzdHMvcGVyZi9odG1sY29sbGVjdGlvbi1sYXN0LWl0 ZW0tZXhwZWN0ZWQudHh0CShyZXZpc2lvbiAwKQorKysgTGF5b3V0VGVzdHMvcGVyZi9odG1sY29s bGVjdGlvbi1sYXN0LWl0ZW0tZXhwZWN0ZWQudHh0CShyZXZpc2lvbiAwKQpAQCAtMCwwICsxLDMg QEAKK1Rlc3RzIHRoYXQgYWNjZXNzaW5nIHRoZSBsYXN0IGl0ZW0gaW4gY2hpbGRyZW4gSFRNTENv bGxlY3Rpb24gaXMgYSBjb25zdGFudCB0aW1lIG9wZXJhdGlvbi4KK1BBU1MKKwpJbmRleDogTGF5 b3V0VGVzdHMvcGVyZi9odG1sY29sbGVjdGlvbi1sYXN0LWl0ZW0uaHRtbAo9PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0t LSBMYXlvdXRUZXN0cy9wZXJmL2h0bWxjb2xsZWN0aW9uLWxhc3QtaXRlbS5odG1sCShyZXZpc2lv biAwKQorKysgTGF5b3V0VGVzdHMvcGVyZi9odG1sY29sbGVjdGlvbi1sYXN0LWl0ZW0uaHRtbAko cmV2aXNpb24gMCkKQEAgLTAsMCArMSwyNyBAQAorPCFET0NUWVBFIGh0bWw+Cis8Ym9keT4KKzxk aXYgaWQ9ImNvbnRhaW5lciIgc3R5bGU9ImRpc3BsYXk6IG5vbmU7Ij48L2Rpdj4KKzxzY3JpcHQg c3JjPSIuLi9yZXNvdXJjZXMvbWFnbml0dWRlLXBlcmYuanMiPjwvc2NyaXB0PgorPHNjcmlwdD4K KwordmFyIGNvbnRhaW5lciA9IGRvY3VtZW50LmdldEVsZW1lbnRCeUlkKCdjb250YWluZXInKTsK KworZnVuY3Rpb24gc2V0dXBGdW5jdGlvbihtYWduaXR1ZGUpCit7CisgICAgY29udGFpbmVyLmlu bmVySFRNTCA9ICcnOworICAgIGZvciAodmFyIGkgPSAwOyBpIDwgbWFnbml0dWRlOyBpKyspCisg ICAgICAgIGNvbnRhaW5lci5hcHBlbmRDaGlsZChkb2N1bWVudC5jcmVhdGVFbGVtZW50KCdkaXYn KSk7Cit9CisKK2Z1bmN0aW9uIHRlc3QobWFnbml0dWRlKQoreworICAgIGNvbnRhaW5lci5jaGls ZHJlblswXS5jbGFzcyA9ICdmaXJzdCBpdGVtJzsKKyAgICBjb250YWluZXIuY2hpbGRyZW5bY29u dGFpbmVyLmNoaWxkcmVuLmxlbmd0aCAtIDFdLmNsYXNzID0gJ2xhc3QgaXRlbSc7Cit9CisKK01h Z25pdHVkZS5kZXNjcmlwdGlvbigiVGVzdHMgdGhhdCBhY2Nlc3NpbmcgdGhlIGxhc3QgaXRlbSBp biBjaGlsZHJlbiBIVE1MQ29sbGVjdGlvbiBpcyBhIGNvbnN0YW50IHRpbWUgb3BlcmF0aW9uLiIp OworTWFnbml0dWRlLnJ1bihzZXR1cEZ1bmN0aW9uLCB0ZXN0LCBNYWduaXR1ZGUuQ09OU1RBTlQp OworCis8L3NjcmlwdD4KKzwvYm9keT4KKzwvaHRtbD4K