130820 2014-03-26 22:30:53 -0700 HTMLConverter::_processText is slow because it walks up ancestor elements 2014-03-26 23:23:18 -0700 1 1 1 Unclassified WebKit HTML Editing 528+ (Nightly build) Unspecified Unspecified RESOLVED FIXED P2 Normal --- 130227 1 rniwa rniwa commit-queue darin enrica kling sam oldest_to_newest 994828 0 rniwa 2014-03-26 22:30:53 -0700 Right now HTMLConverter::_processText walks up the entire ancestor chain to merge their attributed strings. Doing that for every text node results in O(kn) runtime complexity where k is the depth of the tree and n is the number of text nodes in the tree. 994831 1 227922 rniwa 2014-03-26 22:35:46 -0700 Created attachment 227922 Adds a new cache 994838 2 227922 commit-queue 2014-03-26 23:23:15 -0700 Comment on attachment 227922 Adds a new cache Clearing flags on attachment: 227922 Committed r166347: <http://trac.webkit.org/changeset/166347> 994839 3 commit-queue 2014-03-26 23:23:18 -0700 All reviewed patches have been landed. Closing bug. 227922 2014-03-26 22:35:46 -0700 2014-03-26 23:23:14 -0700 Adds a new cache fix130820 text/plain 5105 rniwa SW5kZXg6IFNvdXJjZS9XZWJDb3JlL0NoYW5nZUxvZwo9PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0tLSBTb3VyY2UvV2Vi Q29yZS9DaGFuZ2VMb2cJKHJldmlzaW9uIDE2NjM0NSkKKysrIFNvdXJjZS9XZWJDb3JlL0NoYW5n ZUxvZwkod29ya2luZyBjb3B5KQpAQCAtMSwzICsxLDIxIEBACisyMDE0LTAzLTI2ICBSeW9zdWtl IE5pd2EgIDxybml3YUB3ZWJraXQub3JnPgorCisgICAgICAgIEhUTUxDb252ZXJ0ZXI6Ol9wcm9j ZXNzVGV4dCBpcyBzbG93IGJlY2F1c2UgaXQgd2Fsa3MgdXAgYW5jZXN0b3IgZWxlbWVudHMKKyAg ICAgICAgaHR0cHM6Ly9idWdzLndlYmtpdC5vcmcvc2hvd19idWcuY2dpP2lkPTEzMDgyMAorCisg ICAgICAgIFJldmlld2VkIGJ5IE5PQk9EWSAoT09QUyEpLgorCisgICAgICAgIEF2b2lkIHdhbGtp bmcgdXAgdGhlIHRyZWUgZnJvbSBlYWNoIHRleHQgbm9kZSBieSBjYWNoaW5nIHRoZSBhZ2dyZWdh dGVkIGF0dHJpYnV0ZWQgc3RyaW5ncyBmb3IgZWFjaCBlbGVtZW50LgorICAgICAgICBBbHNvIGNv bXB1dGUgdGhlIGF0dHJpYnV0ZWQgc3RyaW5ncyB0b3AtZG93biB0byBhdm9pZCBjYWxsaW5nIG11 dGFibGVDb3B5IGluIGV2ZXJ5IGl0ZXJhdGlvbi4gCisKKyAgICAgICAgVGhpcyByZWR1Y2VzIHRo ZSBydW50aW1lIG9mIEludGVyYWN0aXZlL0NvcHlBbGwuaHRtbCBmcm9tIDE1cyB0byAxM3MgKDE1 JSkuCisKKyAgICAgICAgKiBlZGl0aW5nL2NvY29hL0hUTUxDb252ZXJ0ZXIubW06CisgICAgICAg IChIVE1MQ29udmVydGVyOjpfYXR0cmlidXRlc0ZvckVsZW1lbnQpOgorICAgICAgICAoSFRNTENv bnZlcnRlcjo6YXR0cmlidXRlc0ZvckVsZW1lbnQpOgorICAgICAgICAoSFRNTENvbnZlcnRlcjo6 YWdncmVnYXRlZEF0dHJpYnV0ZXNGb3JBbmNlc3RvcnMpOgorICAgICAgICAoSFRNTENvbnZlcnRl cjo6X3Byb2Nlc3NUZXh0KToKKwogMjAxNC0wMy0yNiAgU2FtIFdlaW5pZyAgPHNhbUB3ZWJraXQu b3JnPgogCiAgICAgICAgIEZpeCBpT1MgYnVpbGQuCkluZGV4OiBTb3VyY2UvV2ViQ29yZS9lZGl0 aW5nL2NvY29hL0hUTUxDb252ZXJ0ZXIubW0KPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQotLS0gU291cmNlL1dlYkNvcmUv ZWRpdGluZy9jb2NvYS9IVE1MQ29udmVydGVyLm1tCShyZXZpc2lvbiAxNjYzNDIpCisrKyBTb3Vy Y2UvV2ViQ29yZS9lZGl0aW5nL2NvY29hL0hUTUxDb252ZXJ0ZXIubW0JKHdvcmtpbmcgY29weSkK QEAgLTQ1NCw3ICs0NTQsOCBAQAogICAgIAogcHJpdmF0ZToKICAgICBIYXNoTWFwPFJlZlB0cjxF bGVtZW50PiwgUmV0YWluUHRyPE5TRGljdGlvbmFyeT4+IG1fYXR0cmlidXRlc0ZvckVsZW1lbnRz OwotICAgIAorICAgIEhhc2hNYXA8UmVmUHRyPEVsZW1lbnQ+LCBSZXRhaW5QdHI8TlNNdXRhYmxl RGljdGlvbmFyeT4+IG1fYWdncmVnYXRlZEF0dHJpYnV0ZXNGb3JFbGVtZW50czsKKwogICAgIE5T TXV0YWJsZUF0dHJpYnV0ZWRTdHJpbmcgKl9hdHRyU3RyOwogICAgIE5TTXV0YWJsZURpY3Rpb25h cnkgKl9kb2N1bWVudEF0dHJzOwogICAgIE5TVVJMICpfYmFzZVVSTDsKQEAgLTQ5Nyw2ICs0OTgs OCBAQAogICAgIAogICAgIE5TRGljdGlvbmFyeSAqX2NvbXB1dGVkQXR0cmlidXRlc0ZvckVsZW1l bnQoRWxlbWVudCYpOwogICAgIE5TRGljdGlvbmFyeSAqX2F0dHJpYnV0ZXNGb3JFbGVtZW50KERP TUVsZW1lbnQgKik7CisgICAgTlNEaWN0aW9uYXJ5KiBhdHRyaWJ1dGVzRm9yRWxlbWVudChFbGVt ZW50JiBlbGVtZW50KTsKKyAgICBOU0RpY3Rpb25hcnkqIGFnZ3JlZ2F0ZWRBdHRyaWJ1dGVzRm9y QW5jZXN0b3JzKENoYXJhY3RlckRhdGEmKTsKICAgICAKICAgICBFbGVtZW50KiBfYmxvY2tMZXZl bEVsZW1lbnRGb3JOb2RlKE5vZGUqKTsKICAgICAKQEAgLTEzNTIsMTUgKzEzNTUsNDUgQEAKIHsK ICAgICBpZiAoIWVsZW1lbnQpCiAgICAgICAgIHJldHVybiBbTlNEaWN0aW9uYXJ5IGRpY3Rpb25h cnldOwotICAgIAotICAgIEVsZW1lbnQmIGNvcmVFbGVtZW50ID0gKmNvcmUoZWxlbWVudCk7Ci0g ICAgCi0gICAgYXV0byYgYXR0cmlidXRlcyA9IG1fYXR0cmlidXRlc0ZvckVsZW1lbnRzLmFkZCgm Y29yZUVsZW1lbnQsIG51bGxwdHIpLml0ZXJhdG9yLT52YWx1ZTsKKyAgICByZXR1cm4gYXR0cmli dXRlc0ZvckVsZW1lbnQoKmNvcmUoZWxlbWVudCkpOworfQorCitOU0RpY3Rpb25hcnkqIEhUTUxD b252ZXJ0ZXI6OmF0dHJpYnV0ZXNGb3JFbGVtZW50KEVsZW1lbnQmIGVsZW1lbnQpCit7CisgICAg YXV0byYgYXR0cmlidXRlcyA9IG1fYXR0cmlidXRlc0ZvckVsZW1lbnRzLmFkZCgmZWxlbWVudCwg bnVsbHB0cikuaXRlcmF0b3ItPnZhbHVlOwogICAgIGlmICghYXR0cmlidXRlcykKLSAgICAgICAg YXR0cmlidXRlcyA9IF9jb21wdXRlZEF0dHJpYnV0ZXNGb3JFbGVtZW50KGNvcmVFbGVtZW50KTsK KyAgICAgICAgYXR0cmlidXRlcyA9IF9jb21wdXRlZEF0dHJpYnV0ZXNGb3JFbGVtZW50KGVsZW1l bnQpOwogICAgIHJldHVybiBhdHRyaWJ1dGVzLmdldCgpOwogfQogCitOU0RpY3Rpb25hcnkqIEhU TUxDb252ZXJ0ZXI6OmFnZ3JlZ2F0ZWRBdHRyaWJ1dGVzRm9yQW5jZXN0b3JzKENoYXJhY3RlckRh dGEmIG5vZGUpCit7CisgICAgTm9kZSogYW5jZXN0b3IgPSBub2RlLnBhcmVudE5vZGUoKTsKKyAg ICB3aGlsZSAoYW5jZXN0b3IgJiYgIWFuY2VzdG9yLT5pc0VsZW1lbnROb2RlKCkpCisgICAgICAg IGFuY2VzdG9yID0gYW5jZXN0b3ItPnBhcmVudE5vZGUoKTsKKyAgICBpZiAoIWFuY2VzdG9yKQor ICAgICAgICByZXR1cm4gbnVsbHB0cjsKKworICAgIGF1dG8mIGF0dHJpYnV0ZXMgPSBtX2FnZ3Jl Z2F0ZWRBdHRyaWJ1dGVzRm9yRWxlbWVudHMuYWRkKHRvRWxlbWVudChhbmNlc3RvciksIG51bGxw dHIpLml0ZXJhdG9yLT52YWx1ZTsKKyAgICBpZiAoIWF0dHJpYnV0ZXMpIHsKKyAgICAgICAgVmVj dG9yPEVsZW1lbnQqLCAxNj4gYW5jZXN0b3JFbGVtZW50czsKKyAgICAgICAgYW5jZXN0b3JFbGVt ZW50cy5hcHBlbmQodG9FbGVtZW50KGFuY2VzdG9yKSk7CisgICAgICAgIGZvciAoOyBhbmNlc3Rv cjsgYW5jZXN0b3IgPSBhbmNlc3Rvci0+cGFyZW50Tm9kZSgpKSB7CisgICAgICAgICAgICBpZiAo YW5jZXN0b3ItPmlzRWxlbWVudE5vZGUoKSkKKyAgICAgICAgICAgICAgICBhbmNlc3RvckVsZW1l bnRzLmFwcGVuZCh0b0VsZW1lbnQoYW5jZXN0b3IpKTsKKyAgICAgICAgfQorCisgICAgICAgIGF0 dHJpYnV0ZXMgPSBbTlNNdXRhYmxlRGljdGlvbmFyeSBkaWN0aW9uYXJ5XTsKKyAgICAgICAgLy8g RmlsbCBhdHRycyBkaWN0aW9uYXJ5IHdpdGggYXR0cmlidXRlcyBmcm9tIHRoZSBoaWdoZXN0IHRv IHRoZSBsb3dlc3QsIG5vdCBvdmVyd3JpdGluZyBvbmVzIGRlZXBlciBpbiB0aGUgdHJlZQorICAg ICAgICBmb3IgKHVuc2lnbmVkIGluZGV4ID0gYW5jZXN0b3JFbGVtZW50cy5zaXplKCk7IGluZGV4 OykgeworICAgICAgICAgICAgaW5kZXgtLTsKKyAgICAgICAgICAgIFthdHRyaWJ1dGVzIGFkZEVu dHJpZXNGcm9tRGljdGlvbmFyeTphdHRyaWJ1dGVzRm9yRWxlbWVudCgqYW5jZXN0b3JFbGVtZW50 c1tpbmRleF0pXTsKKyAgICAgICAgfQorICAgIH0KKworICAgIHJldHVybiBhdHRyaWJ1dGVzLmdl dCgpOworfQorCiB2b2lkIEhUTUxDb252ZXJ0ZXI6Ol9uZXdQYXJhZ3JhcGhGb3JFbGVtZW50KERP TUVsZW1lbnQgKmVsZW1lbnQsIE5TU3RyaW5nICp0YWcsIEJPT0wgZmxhZywgQk9PTCBzdXBwcmVz c1RyYWlsaW5nU3BhY2UpCiB7CiAgICAgTlNVSW50ZWdlciB0ZXh0TGVuZ3RoID0gW19hdHRyU3Ry IGxlbmd0aF07CkBAIC0yMzMyLDIyICsyMzY1LDggQEAKIAogICAgICAgICBbX2F0dHJTdHIgcmVw bGFjZUNoYXJhY3RlcnNJblJhbmdlOnJhbmdlVG9SZXBsYWNlIHdpdGhTdHJpbmc6b3V0cHV0U3Ry aW5nXTsKICAgICAgICAgcmFuZ2VUb1JlcGxhY2UubGVuZ3RoID0gb3V0cHV0U3RyaW5nLmxlbmd0 aCgpOwotICAgICAgICBSZXRhaW5QdHI8TlNEaWN0aW9uYXJ5PiBhdHRyczsKLSAgICAgICAgTm9k ZSogYW5jZXN0b3IgPSBjaGFyYWN0ZXJEYXRhLnBhcmVudE5vZGUoKTsKLSAgICAgICAgd2hpbGUg KGFuY2VzdG9yKSB7Ci0gICAgICAgICAgICAvLyBGaWxsIGF0dHJzIGRpY3Rpb25hcnkgd2l0aCBh dHRyaWJ1dGVzIGZyb20gcGFyZW50IG5vZGVzLCBub3Qgb3ZlcndyaXRpbmcgb25lcyBkZWVwZXIg aW4gdGhlIHRyZWUKLSAgICAgICAgICAgIGlmKGFuY2VzdG9yLT5pc0VsZW1lbnROb2RlKCkpIHsK LSAgICAgICAgICAgICAgICBSZXRhaW5QdHI8TlNNdXRhYmxlRGljdGlvbmFyeT4gbmV3QXR0cnMg PSBhZG9wdE5TKFtfYXR0cmlidXRlc0ZvckVsZW1lbnQoa2l0KHRvRWxlbWVudChhbmNlc3Rvcikp KSBtdXRhYmxlQ29weV0pOwotICAgICAgICAgICAgICAgIGlmIChhdHRycykgewotICAgICAgICAg ICAgICAgICAgICAvLyBBbHJlYWR5LXNldCBhdHRyaWJ1dGVzIChmcm9tIGxvd2VyIGluIHRoZSB0 cmVlKSBvdmVyd3JpdGUgdGhlIGhpZ2hlciBvbmVzLgotICAgICAgICAgICAgICAgICAgICBbbmV3 QXR0cnMgYWRkRW50cmllc0Zyb21EaWN0aW9uYXJ5OmF0dHJzLmdldCgpXTsKLSAgICAgICAgICAg ICAgICB9Ci0gICAgICAgICAgICAgICAgYXR0cnMgPSBuZXdBdHRyczsKLSAgICAgICAgICAgIH0K LSAgICAgICAgICAgIGFuY2VzdG9yID0gYW5jZXN0b3ItPnBhcmVudE5vZGUoKTsKLSAgICAgICAg fQotICAgICAgICBpZiAocmFuZ2VUb1JlcGxhY2UubGVuZ3RoID4gMCkKLSAgICAgICAgICAgIFtf YXR0clN0ciBzZXRBdHRyaWJ1dGVzOmF0dHJzLmdldCgpIHJhbmdlOnJhbmdlVG9SZXBsYWNlXTsK KyAgICAgICAgaWYgKHJhbmdlVG9SZXBsYWNlLmxlbmd0aCkKKyAgICAgICAgICAgIFtfYXR0clN0 ciBzZXRBdHRyaWJ1dGVzOmFnZ3JlZ2F0ZWRBdHRyaWJ1dGVzRm9yQW5jZXN0b3JzKGNoYXJhY3Rl ckRhdGEpIHJhbmdlOnJhbmdlVG9SZXBsYWNlXTsKICAgICAgICAgX2ZsYWdzLmlzU29mdCA9IHdh c1NwYWNlOwogICAgIH0KICAgICBpZiAobXV0c3RyKQo=