94429 2012-08-19 10:35:15 -0700 TextIterator takes O(n^2) to iterate over n empty blocks 2012-08-21 09:44:07 -0700 1 1 1 Unclassified WebKit HTML Editing 528+ (Nightly build) Unspecified Unspecified RESOLVED FIXED InRadar P2 Normal --- 1 mitz webkit-unassigned enrica mifenton webkit.review.bot oldest_to_newest 699048 0 mitz 2012-08-19 10:35:15 -0700 <rdar://problem/12104508> Iterating over a structure like <div> <div></div> <div></div> ⋮ <div></div> </div> using TextIterator takes O(n^2) in the number of blocks, since shouldRepresentNodeOffsetZero() creates a VisiblePosition for each block, which in turn requires iterating over all successive blocks. 699049 1 159299 mitz 2012-08-19 10:39:22 -0700 Created attachment 159299 Improve shouldRepresentNodeOffsetZero()’s check for nodes that cannot contain a VisiblePosition 699114 2 159299 sam 2012-08-19 16:09:17 -0700 Comment on attachment 159299 Improve shouldRepresentNodeOffsetZero()’s check for nodes that cannot contain a VisiblePosition Looks good. Is this a case where making a performance test that can detect n vs n^2 would be a good idea? 700840 3 mitz 2012-08-21 09:44:07 -0700 Fixed in <http://trac.webkit.org/r126164>. 159299 2012-08-19 10:39:22 -0700 2012-08-19 16:09:17 -0700 Improve shouldRepresentNodeOffsetZero()’s check for nodes that cannot contain a VisiblePosition 12104508_r1.diff text/plain 2352 mitz SW5kZXg6IFNvdXJjZS9XZWJDb3JlL0NoYW5nZUxvZwo9PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0tLSBTb3VyY2UvV2Vi Q29yZS9DaGFuZ2VMb2cJKHJldmlzaW9uIDEyNTk3NikKKysrIFNvdXJjZS9XZWJDb3JlL0NoYW5n ZUxvZwkod29ya2luZyBjb3B5KQpAQCAtMSwzICsxLDE2IEBACisyMDEyLTA4LTE5ICBEYW4gQmVy bnN0ZWluICA8bWl0ekBhcHBsZS5jb20+CisKKyAgICAgICAgPHJkYXI6Ly9wcm9ibGVtLzEyMTA0 NTA4PiBUZXh0SXRlcmF0b3IgdGFrZXMgTyhuXjIpIHRvIGl0ZXJhdGUgb3ZlciBuIGVtcHR5IGJs b2NrcworICAgICAgICBodHRwczovL2J1Z3Mud2Via2l0Lm9yZy9zaG93X2J1Zy5jZ2k/aWQ9OTQ0 MjkKKworICAgICAgICBSZXZpZXdlZCBieSBOT0JPRFkgKE9PUFMhKS4KKworICAgICAgICBObyBu ZXcgdGVzdHMsIGJlY2F1c2UgYmVoYXZpb3IgaXMgdW5jaGFuZ2VkLgorCisgICAgICAgICogZWRp dGluZy9UZXh0SXRlcmF0b3IuY3BwOgorICAgICAgICAoV2ViQ29yZTo6VGV4dEl0ZXJhdG9yOjpz aG91bGRSZXByZXNlbnROb2RlT2Zmc2V0WmVybyk6IEVuaGFuY2VkIHRoZSBjaGVjayBmb3Igbm9k ZXMgdGhhdAorICAgICAgICBjYW5ub3QgY29udGFpbiBWaXNpYmxlUG9zaXRpb24gdG8gYWxzbyBj aGVjayBmb3IgemVyby1oZWlnaHQgYmxvY2tzLgorCiAyMDEyLTA4LTE5ICBDYXJsb3MgR2FyY2lh IENhbXBvcyAgPGNnYXJjaWFAaWdhbGlhLmNvbT4KIAogICAgICAgICBVbnJldmlld2VkLiBGaXgg bWFrZSBkaXN0Y2hlY2suCkluZGV4OiBTb3VyY2UvV2ViQ29yZS9lZGl0aW5nL1RleHRJdGVyYXRv ci5jcHAKPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PQotLS0gU291cmNlL1dlYkNvcmUvZWRpdGluZy9UZXh0SXRlcmF0b3Iu Y3BwCShyZXZpc2lvbiAxMjU5NzEpCisrKyBTb3VyY2UvV2ViQ29yZS9lZGl0aW5nL1RleHRJdGVy YXRvci5jcHAJKHdvcmtpbmcgY29weSkKQEAgLTEsNSArMSw1IEBACiAvKgotICogQ29weXJpZ2h0 IChDKSAyMDA0LCAyMDA1LCAyMDA2LCAyMDA3LCAyMDA4LCAyMDA5LCAyMDEwIEFwcGxlIEluYy4g QWxsIHJpZ2h0cyByZXNlcnZlZC4KKyAqIENvcHlyaWdodCAoQykgMjAwNCwgMjAwNSwgMjAwNiwg MjAwNywgMjAwOCwgMjAwOSwgMjAxMCwgMjAxMiBBcHBsZSBJbmMuIEFsbCByaWdodHMgcmVzZXJ2 ZWQuCiAgKiBDb3B5cmlnaHQgKEMpIDIwMDUgQWxleGV5IFByb3NrdXJ5YWtvdi4KICAqCiAgKiBS ZWRpc3RyaWJ1dGlvbiBhbmQgdXNlIGluIHNvdXJjZSBhbmQgYmluYXJ5IGZvcm1zLCB3aXRoIG9y IHdpdGhvdXQKQEAgLTg5Myw5ICs4OTMsMTAgQEAgYm9vbCBUZXh0SXRlcmF0b3I6OnNob3VsZFJl cHJlc2VudE5vZGVPZgogICAgIC8vIElmIHRoaXMgbm9kZSBpcyB1bnJlbmRlcmVkIG9yIGludmlz aWJsZSB0aGUgVmlzaWJsZVBvc2l0aW9uIGNoZWNrcyBiZWxvdyB3b24ndCBoYXZlIG11Y2ggbWVh bmluZy4KICAgICAvLyBBZGRpdGlvbmFsbHksIGlmIHRoZSByYW5nZSB3ZSBhcmUgaXRlcmF0aW5n IG92ZXIgY29udGFpbnMgaHVnZSBzZWN0aW9ucyBvZiB1bnJlbmRlcmVkIGNvbnRlbnQsIAogICAg IC8vIHdlIHdvdWxkIGNyZWF0ZSBWaXNpYmxlUG9zaXRpb25zIG9uIGV2ZXJ5IGNhbGwgdG8gdGhp cyBmdW5jdGlvbiB3aXRob3V0IHRoaXMgY2hlY2suCi0gICAgaWYgKCFtX25vZGUtPnJlbmRlcmVy KCkgfHwgbV9ub2RlLT5yZW5kZXJlcigpLT5zdHlsZSgpLT52aXNpYmlsaXR5KCkgIT0gVklTSUJM RSkKKyAgICBpZiAoIW1fbm9kZS0+cmVuZGVyZXIoKSB8fCBtX25vZGUtPnJlbmRlcmVyKCktPnN0 eWxlKCktPnZpc2liaWxpdHkoKSAhPSBWSVNJQkxFCisgICAgICAgIHx8IChtX25vZGUtPnJlbmRl cmVyKCktPmlzQmxvY2tGbG93KCkgJiYgIXRvUmVuZGVyQmxvY2sobV9ub2RlLT5yZW5kZXJlcigp KS0+aGVpZ2h0KCkgJiYgIW1fbm9kZS0+aGFzVGFnTmFtZShib2R5VGFnKSkpCiAgICAgICAgIHJl dHVybiBmYWxzZTsKLSAgICAKKwogICAgIC8vIFRoZSBzdGFydFBvcy5pc05vdE51bGwoKSBjaGVj ayBpcyBuZWVkZWQgYmVjYXVzZSB0aGUgc3RhcnQgY291bGQgYmUgYmVmb3JlIHRoZSBib2R5LAog ICAgIC8vIGFuZCBpbiB0aGF0IGNhc2Ugd2UnbGwgZ2V0IG51bGwuIFdlIGRvbid0IHdhbnQgdG8g cHV0IGluIG5ld2xpbmVzIGF0IHRoZSBzdGFydCBpbiB0aGF0IGNhc2UuCiAgICAgLy8gVGhlIGN1 cnJQb3MuaXNOb3ROdWxsKCkgY2hlY2sgaXMgbmVlZGVkIGJlY2F1c2UgcG9zaXRpb25zIGluIG5v bi1IVE1MIGNvbnRlbnQK