156570 2016-04-14 01:42:12 -0700 Collapsed border cache invalidation can lead to O(n^2) during style resolve 2016-04-14 14:09:13 -0700 1 1 1 Unclassified WebKit Tables WebKit Nightly Build Unspecified Unspecified RESOLVED FIXED InRadar P2 Normal --- 1 koivisto webkit-unassigned commit-queue esprehn+autocc glenn kling kondapallykalyan webkit-bug-importer oldest_to_newest 1183661 0 koivisto 2016-04-14 01:42:12 -0700 RenderTable::invalidateCollapsedBorders traverses all cells. It is called when table cell border changes. This can result in O(n^2) during style resolve. 1183662 1 276381 koivisto 2016-04-14 01:46:43 -0700 Created attachment 276381 patch 1183663 2 webkit-bug-importer 2016-04-14 01:47:15 -0700 <rdar://problem/25722976> 1183847 3 276381 commit-queue 2016-04-14 14:09:10 -0700 Comment on attachment 276381 patch Clearing flags on attachment: 276381 Committed r199552: <http://trac.webkit.org/changeset/199552> 1183848 4 commit-queue 2016-04-14 14:09:13 -0700 All reviewed patches have been landed. Closing bug. 276381 2016-04-14 01:46:43 -0700 2016-04-14 14:09:10 -0700 patch collapsed-border-style-change-2.patch text/plain 4558 koivisto SW5kZXg6IFNvdXJjZS9XZWJDb3JlL0NoYW5nZUxvZwo9PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0tLSBTb3VyY2UvV2Vi Q29yZS9DaGFuZ2VMb2cJKHJldmlzaW9uIDE5OTUzMikKKysrIFNvdXJjZS9XZWJDb3JlL0NoYW5n ZUxvZwkod29ya2luZyBjb3B5KQpAQCAtMSwzICsxLDI3IEBACisyMDE2LTA0LTE0ICBBbnR0aSBL b2l2aXN0byAgPGFudHRpQGFwcGxlLmNvbT4KKworICAgICAgICBDb2xsYXBzZWQgYm9yZGVyIGNh Y2hlIGludmFsaWRhdGlvbiBjYW4gbGVhZCB0byBPKG5eMikgZHVyaW5nIHN0eWxlIHJlc29sdmUK KyAgICAgICAgaHR0cHM6Ly9idWdzLndlYmtpdC5vcmcvc2hvd19idWcuY2dpP2lkPTE1NjU3MAor CisgICAgICAgIFJldmlld2VkIGJ5IE5PQk9EWSAoT09QUyEpLgorCisgICAgICAgIFJlbmRlclRh YmxlOjppbnZhbGlkYXRlQ29sbGFwc2VkQm9yZGVycyB0cmF2ZXJzZXMgYWxsIGNlbGxzLiBJdCBp cyBjYWxsZWQgd2hlbiB0YWJsZSBjZWxsIGJvcmRlciBjaGFuZ2VzLgorICAgICAgICBUaGlzIGNh biByZXN1bHQgaW4gTyhuXjIpIGR1cmluZyBzdHlsZSByZXNvbHZlLgorCisgICAgICAgICogcmVu ZGVyaW5nL1JlbmRlclRhYmxlLmNwcDoKKyAgICAgICAgKFdlYkNvcmU6OlJlbmRlclRhYmxlOjps YXlvdXQpOgorICAgICAgICAoV2ViQ29yZTo6UmVuZGVyVGFibGU6OmludmFsaWRhdGVDb2xsYXBz ZWRCb3JkZXJzKToKKworICAgICAgICAgICAgRm9yIGNlbGwgYm9yZGVyIHN0eWxlIGNoYW5nZSBp bnZhbGlkYXRlIHRoZSBoYXNFbXB0eUNvbGxhcHNlZEJvcmRlciBiaXRzIG9ubHkgZm9yIHRoZSBu ZWlnaGJvdXJpbmcgY2VsbHMuCisgICAgICAgICAgICBUaGV5IGFyZSB0aGUgb25seSBvbmVzIHRo YXQgY2FuIGJlIGFmZmVjdGVkLgorCisgICAgICAgICogcmVuZGVyaW5nL1JlbmRlclRhYmxlLmg6 CisgICAgICAgIChXZWJDb3JlOjpSZW5kZXJUYWJsZTo6Y29sbGFwc2VkQm9yZGVyc0FyZVZhbGlk KToKKyAgICAgICAgKFdlYkNvcmU6OlJlbmRlclRhYmxlOjpjb2xsYXBzZWRFbXB0eUJvcmRlcklz UHJlc2VudCk6CisgICAgICAgIChXZWJDb3JlOjpSZW5kZXJUYWJsZTo6Y3VycmVudEJvcmRlclZh bHVlKToKKyAgICAgICAgKiByZW5kZXJpbmcvUmVuZGVyVGFibGVDZWxsLmNwcDoKKyAgICAgICAg KFdlYkNvcmU6OlJlbmRlclRhYmxlQ2VsbDo6c3R5bGVEaWRDaGFuZ2UpOgorCiAyMDE2LTA0LTEz ICBDYXJsb3MgR2FyY2lhIENhbXBvcyAgPGNnYXJjaWFAaWdhbGlhLmNvbT4KIAogICAgICAgICBV bnJldmlld2VkLiBGaXggR09iamVjdCBET00gYmluZGluZ3MgQVBJIGJyZWFrIGFmdGVyIHIxOTkz OTIuCkluZGV4OiBTb3VyY2UvV2ViQ29yZS9yZW5kZXJpbmcvUmVuZGVyVGFibGUuY3BwCj09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT0KLS0tIFNvdXJjZS9XZWJDb3JlL3JlbmRlcmluZy9SZW5kZXJUYWJsZS5jcHAJKHJldmlz aW9uIDE5OTQxNikKKysrIFNvdXJjZS9XZWJDb3JlL3JlbmRlcmluZy9SZW5kZXJUYWJsZS5jcHAJ KHdvcmtpbmcgY29weSkKQEAgLTU4NiwxNCArNTg2LDMyIEBAIHZvaWQgUmVuZGVyVGFibGU6Omxh eW91dCgpCiAgICAgY2xlYXJOZWVkc0xheW91dCgpOwogfQogCi12b2lkIFJlbmRlclRhYmxlOjpp bnZhbGlkYXRlQ29sbGFwc2VkQm9yZGVycygpCit2b2lkIFJlbmRlclRhYmxlOjppbnZhbGlkYXRl Q29sbGFwc2VkQm9yZGVycyhSZW5kZXJUYWJsZUNlbGwqIGNlbGxXaXRoU3R5bGVDaGFuZ2UpCiB7 CiAgICAgbV9jb2xsYXBzZWRCb3JkZXJzVmFsaWQgPSBmYWxzZTsKICAgICBtX2NvbGxhcHNlZEJv cmRlcnMuY2xlYXIoKTsKLSAgICBmb3IgKGF1dG8mIHNlY3Rpb24gOiBjaGlsZHJlbk9mVHlwZTxS ZW5kZXJUYWJsZVNlY3Rpb24+KCp0aGlzKSkgeworCisgICAgZm9yIChhdXRvJiBzZWN0aW9uIDog Y2hpbGRyZW5PZlR5cGU8UmVuZGVyVGFibGVTZWN0aW9uPigqdGhpcykpCiAgICAgICAgIHNlY3Rp b24uY2xlYXJDYWNoZWRDb2xsYXBzZWRCb3JkZXJzKCk7Ci0gICAgICAgIGlmICghbV9jb2xsYXBz ZWRFbXB0eUJvcmRlcklzUHJlc2VudCkKLSAgICAgICAgICAgIGNvbnRpbnVlOworCisgICAgaWYg KCFtX2NvbGxhcHNlZEVtcHR5Qm9yZGVySXNQcmVzZW50KQorICAgICAgICByZXR1cm47CisKKyAg ICBpZiAoY2VsbFdpdGhTdHlsZUNoYW5nZSkgeworICAgICAgICAvLyBJdCBpcyBlbm91Z2ggdG8g aW52YWxpZGF0ZSBqdXN0IHRoZSBzdXJyb3VuZGluZyBjZWxscyB3aGVuIGNlbGwgYm9yZGVyIHN0 eWxlIGNoYW5nZXMuCisgICAgICAgIGNlbGxXaXRoU3R5bGVDaGFuZ2UtPmludmFsaWRhdGVIYXNF bXB0eUNvbGxhcHNlZEJvcmRlcnMoKTsKKyAgICAgICAgaWYgKGF1dG8qIGJlbG93ID0gY2VsbEJl bG93KGNlbGxXaXRoU3R5bGVDaGFuZ2UpKQorICAgICAgICAgICAgYmVsb3ctPmludmFsaWRhdGVI YXNFbXB0eUNvbGxhcHNlZEJvcmRlcnMoKTsKKyAgICAgICAgaWYgKGF1dG8qIGFib3ZlID0gY2Vs bEFib3ZlKGNlbGxXaXRoU3R5bGVDaGFuZ2UpKQorICAgICAgICAgICAgYWJvdmUtPmludmFsaWRh dGVIYXNFbXB0eUNvbGxhcHNlZEJvcmRlcnMoKTsKKyAgICAgICAgaWYgKGF1dG8qIGJlZm9yZSA9 IGNlbGxCZWZvcmUoY2VsbFdpdGhTdHlsZUNoYW5nZSkpCisgICAgICAgICAgICBiZWZvcmUtPmlu dmFsaWRhdGVIYXNFbXB0eUNvbGxhcHNlZEJvcmRlcnMoKTsKKyAgICAgICAgaWYgKGF1dG8qIGFm dGVyID0gY2VsbEFmdGVyKGNlbGxXaXRoU3R5bGVDaGFuZ2UpKQorICAgICAgICAgICAgYWZ0ZXIt PmludmFsaWRhdGVIYXNFbXB0eUNvbGxhcHNlZEJvcmRlcnMoKTsKKyAgICAgICAgcmV0dXJuOwor ICAgIH0KKworICAgIGZvciAoYXV0byYgc2VjdGlvbiA6IGNoaWxkcmVuT2ZUeXBlPFJlbmRlclRh YmxlU2VjdGlvbj4oKnRoaXMpKSB7CiAgICAgICAgIGZvciAoYXV0byogcm93ID0gc2VjdGlvbi5m aXJzdFJvdygpOyByb3c7IHJvdyA9IHJvdy0+bmV4dFJvdygpKSB7CiAgICAgICAgICAgICBmb3Ig KGF1dG8qIGNlbGwgPSByb3ctPmZpcnN0Q2VsbCgpOyBjZWxsOyBjZWxsID0gY2VsbC0+bmV4dENl bGwoKSkgewogICAgICAgICAgICAgICAgIEFTU0VSVChjZWxsLT50YWJsZSgpID09IHRoaXMpOwpJ bmRleDogU291cmNlL1dlYkNvcmUvcmVuZGVyaW5nL1JlbmRlclRhYmxlLmgKPT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQot LS0gU291cmNlL1dlYkNvcmUvcmVuZGVyaW5nL1JlbmRlclRhYmxlLmgJKHJldmlzaW9uIDE5OTQx NikKKysrIFNvdXJjZS9XZWJDb3JlL3JlbmRlcmluZy9SZW5kZXJUYWJsZS5oCSh3b3JraW5nIGNv cHkpCkBAIC0yMzksNyArMjM5LDcgQEAgcHVibGljOgogIAogICAgIHR5cGVkZWYgVmVjdG9yPENv bGxhcHNlZEJvcmRlclZhbHVlPiBDb2xsYXBzZWRCb3JkZXJWYWx1ZXM7CiAgICAgYm9vbCBjb2xs YXBzZWRCb3JkZXJzQXJlVmFsaWQoKSBjb25zdCB7IHJldHVybiBtX2NvbGxhcHNlZEJvcmRlcnNW YWxpZDsgfQotICAgIHZvaWQgaW52YWxpZGF0ZUNvbGxhcHNlZEJvcmRlcnMoKTsKKyAgICB2b2lk IGludmFsaWRhdGVDb2xsYXBzZWRCb3JkZXJzKFJlbmRlclRhYmxlQ2VsbCogY2VsbFdpdGhTdHls ZUNoYW5nZSA9IG51bGxwdHIpOwogICAgIHZvaWQgY29sbGFwc2VkRW1wdHlCb3JkZXJJc1ByZXNl bnQoKSB7IG1fY29sbGFwc2VkRW1wdHlCb3JkZXJJc1ByZXNlbnQgPSB0cnVlOyB9CiAgICAgY29u c3QgQ29sbGFwc2VkQm9yZGVyVmFsdWUqIGN1cnJlbnRCb3JkZXJWYWx1ZSgpIGNvbnN0IHsgcmV0 dXJuIG1fY3VycmVudEJvcmRlcjsgfQogICAgIApJbmRleDogU291cmNlL1dlYkNvcmUvcmVuZGVy aW5nL1JlbmRlclRhYmxlQ2VsbC5jcHAKPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQotLS0gU291cmNlL1dlYkNvcmUvcmVu ZGVyaW5nL1JlbmRlclRhYmxlQ2VsbC5jcHAJKHJldmlzaW9uIDE5OTQxNikKKysrIFNvdXJjZS9X ZWJDb3JlL3JlbmRlcmluZy9SZW5kZXJUYWJsZUNlbGwuY3BwCSh3b3JraW5nIGNvcHkpCkBAIC00 MjMsNyArNDIzLDcgQEAgdm9pZCBSZW5kZXJUYWJsZUNlbGw6OnN0eWxlRGlkQ2hhbmdlKFN0eQog ICAgIC8vIElmIGJvcmRlciB3YXMgY2hhbmdlZCwgbm90aWZ5IHRhYmxlLgogICAgIFJlbmRlclRh YmxlKiB0YWJsZSA9IHRoaXMtPnRhYmxlKCk7CiAgICAgaWYgKHRhYmxlICYmIG9sZFN0eWxlICYm IG9sZFN0eWxlLT5ib3JkZXIoKSAhPSBzdHlsZSgpLmJvcmRlcigpKQotICAgICAgICB0YWJsZS0+ aW52YWxpZGF0ZUNvbGxhcHNlZEJvcmRlcnMoKTsKKyAgICAgICAgdGFibGUtPmludmFsaWRhdGVD b2xsYXBzZWRCb3JkZXJzKHRoaXMpOwogfQogCiAvLyBUaGUgZm9sbG93aW5nIHJ1bGVzIGFwcGx5 IGZvciByZXNvbHZpbmcgY29uZmxpY3RzIGFuZCBmaWd1cmluZyBvdXQgd2hpY2ggYm9yZGVyCg==