51395 2010-12-21 07:07:23 -0800 Optimize regex patterns which contain empty alternatives 2011-05-15 19:29:51 -0700 1 1 1 Unclassified WebKit JavaScriptCore 528+ (Nightly build) All All RESOLVED INVALID P2 Normal --- 0 pvarga webkit-unassigned abecsi barraclough commit-queue msaboff oldest_to_newest 324990 0 pvarga 2010-12-21 07:07:23 -0800 The time of matching those patterns wich contain empty alternatives can exponentially increase when we attempt to match the pattern in an iterative way. Eg.: /(a|b||){30}/ The fast/regex/slow.html tests this particular problem. The exponential increase of matching time can be avoided with a simple transformation: The empty alternatives should be removed from the pattern and the remaining alternatives should be grouped by a non-capturing parentheses which has a '?' quantifier. Eg.: /(a|b||)/ -> /((?:a|b)?)/ This conversion doesn't change the result of matching and the YARR generates simpler code (native or bytecode) to perform the matching. 324993 1 77110 pvarga 2010-12-21 07:11:05 -0800 Created attachment 77110 proposed patch 337738 2 77110 oliver 2011-01-20 17:06:02 -0800 Comment on attachment 77110 proposed patch r=me, sorry for the delay in review. Let's see if this still merges + compiles. 337754 3 77110 commit-queue 2011-01-20 17:23:43 -0800 Comment on attachment 77110 proposed patch Rejecting attachment 77110 from commit-queue. Failed to run "['./Tools/Scripts/webkit-patch', '--status-host=queues.webkit.org', '--bot-id=eseidel-cq-sl', 'ap..." exit_code: 2 Last 500 characters of output: 0644 |--- Source/JavaScriptCore/yarr/RegexCompiler.cpp |+++ Source/JavaScriptCore/yarr/RegexCompiler.cpp -------------------------- No file to patch. Skipping patch. 1 out of 1 hunk ignored patching file LayoutTests/ChangeLog Hunk #1 succeeded at 1 with fuzz 3. patching file LayoutTests/fast/regex/script-tests/slow.js patching file LayoutTests/fast/regex/slow-expected.txt Failed to run "[u'/Projects/CommitQueue/Tools/Scripts/svn-apply', u'--reviewer', u'Oliver Hunt', u'--force']" exit_code: 1 Full output: http://queues.webkit.org/results/7613267 338941 4 pvarga 2011-01-24 04:16:47 -0800 Landed in r76502. 404250 5 barraclough 2011-05-15 19:29:51 -0700 This optimization is unsafe any will be reverted per: https://bugs.webkit.org/show_bug.cgi?id=60866 77110 2010-12-21 07:11:05 -0800 2011-01-20 17:23:43 -0800 proposed patch 0001-remove-empty-alternatives-v1.patch text/plain 6201 pvarga RnJvbSA0NWZiMDQ0NWUyNDA1ODEzOWFjY2VjZjVhMWU1NWE4ZWFlYmFjNjMzIE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBQZXRlciBWYXJnYSA8cHZhcmdhQGluZi51LXN6ZWdlZC5odT4K RGF0ZTogVHVlLCAyMSBEZWMgMjAxMCAwNzoxMDo1OSAtMDgwMApTdWJqZWN0OiBbUEFUQ0hdIHJl bW92ZSBlbXB0eSBhbHRlcm5hdGl2ZXMgdjEKCi0tLQogSmF2YVNjcmlwdENvcmUvQ2hhbmdlTG9n ICAgICAgICAgICAgICAgICAgICB8ICAgMTMgKysrKysrKysrCiBKYXZhU2NyaXB0Q29yZS95YXJy L1JlZ2V4Q29tcGlsZXIuY3BwICAgICAgIHwgICA0MCArKysrKysrKysrKysrKysrKysrKysrKyst LS0KIExheW91dFRlc3RzL0NoYW5nZUxvZyAgICAgICAgICAgICAgICAgICAgICAgfCAgIDEzICsr KysrKysrKwogTGF5b3V0VGVzdHMvZmFzdC9yZWdleC9zY3JpcHQtdGVzdHMvc2xvdy5qcyB8ICAg IDIgKy0KIExheW91dFRlc3RzL2Zhc3QvcmVnZXgvc2xvdy1leHBlY3RlZC50eHQgICAgfCAgICAy ICstCiA1IGZpbGVzIGNoYW5nZWQsIDY0IGluc2VydGlvbnMoKyksIDYgZGVsZXRpb25zKC0pCgpk aWZmIC0tZ2l0IGEvSmF2YVNjcmlwdENvcmUvQ2hhbmdlTG9nIGIvSmF2YVNjcmlwdENvcmUvQ2hh bmdlTG9nCmluZGV4IGI3YTEwMGUuLjZhMTZmNjQgMTAwNjQ0Ci0tLSBhL0phdmFTY3JpcHRDb3Jl L0NoYW5nZUxvZworKysgYi9KYXZhU2NyaXB0Q29yZS9DaGFuZ2VMb2cKQEAgLTEsNSArMSwxOCBA QAogMjAxMC0xMi0yMSAgUGV0ZXIgVmFyZ2EgIDxwdmFyZ2FAaW5mLnUtc3plZ2VkLmh1PgogCisg ICAgICAgIFJldmlld2VkIGJ5IE5PQk9EWSAoT09QUyEpLgorCisgICAgICAgIE9wdGltaXplIHJl Z2V4IHBhdHRlcm5zIHdoaWNoIGNvbnRhaW4gZW1wdHkgYWx0ZXJuYXRpdmVzCisgICAgICAgIGh0 dHBzOi8vYnVncy53ZWJraXQub3JnL3Nob3dfYnVnLmNnaT9pZD01MTM5NQorCisgICAgICAgIEVs aW1pbmF0ZSB0aGUgZW1wdHkgYWx0ZXJuYXRpdmVzIGZyb20gdGhlIHJlZ2V4IHBhdHRlcm4gYW5k IGNvbnZlcnQgaXQgdG8gZG8KKyAgICAgICAgdGhlIG1hdGNoaW5nIGluIGFuIGVhc2llciB3YXku CisKKyAgICAgICAgKiB5YXJyL1JlZ2V4Q29tcGlsZXIuY3BwOgorICAgICAgICAoSlNDOjpZYXJy OjpSZWdleFBhdHRlcm5Db25zdHJ1Y3Rvcjo6YXRvbVBhcmVudGhlc2VzRW5kKToKKworMjAxMC0x Mi0yMSAgUGV0ZXIgVmFyZ2EgIDxwdmFyZ2FAaW5mLnUtc3plZ2VkLmh1PgorCiAgICAgICAgIFJl dmlld2VkIGJ5IENzYWJhIE9zenRyb2dvbsOhYy4KIAogICAgICAgICBVbmlmeSB0aGUgbmFtZSBv ZiBwYXJlbnRoZXNlcyBpbiBZQVJSOiByZW5hbWUgcGFyZW50aGVzaXMgdG8KZGlmZiAtLWdpdCBh L0phdmFTY3JpcHRDb3JlL3lhcnIvUmVnZXhDb21waWxlci5jcHAgYi9KYXZhU2NyaXB0Q29yZS95 YXJyL1JlZ2V4Q29tcGlsZXIuY3BwCmluZGV4IDkwNjMzNTkuLmE2MDQxZGYgMTAwNjQ0Ci0tLSBh L0phdmFTY3JpcHRDb3JlL3lhcnIvUmVnZXhDb21waWxlci5jcHAKKysrIGIvSmF2YVNjcmlwdENv cmUveWFyci9SZWdleENvbXBpbGVyLmNwcApAQCAtNDgxLDI0ICs0ODEsNTYgQEAgcHVibGljOgog ICAgICAgICBtX2FsdGVybmF0aXZlID0gbV9hbHRlcm5hdGl2ZS0+bV9wYXJlbnQtPm1fcGFyZW50 OwogCiAgICAgICAgIFBhdHRlcm5UZXJtJiBsYXN0VGVybSA9IG1fYWx0ZXJuYXRpdmUtPmxhc3RU ZXJtKCk7Ci0gICAgICAgIAorCiAgICAgICAgIHVuc2lnbmVkIG51bVBhcmVuQWx0ZXJuYXRpdmVz ID0gcGFyZW50aGVzZXNEaXNqdW5jdGlvbi0+bV9hbHRlcm5hdGl2ZXMuc2l6ZSgpOwogICAgICAg ICB1bnNpZ25lZCBudW1CT0xBbmNob3JlZEFsdHMgPSAwOwotICAgICAgICAvLyBCdWJibGUgdXAg Qk9MIGZsYWdzCisgICAgICAgIGJvb2wgY29udGFpbnNFbXB0eUFsdGVybmF0aXZlID0gZmFsc2U7 CisKICAgICAgICAgZm9yICh1bnNpZ25lZCBpID0gMDsgaSA8IG51bVBhcmVuQWx0ZXJuYXRpdmVz OyBpKyspIHsKKyAgICAgICAgICAgIGlmICghcGFyZW50aGVzZXNEaXNqdW5jdGlvbi0+bV9hbHRl cm5hdGl2ZXNbaV0tPm1fdGVybXMuc2l6ZSgpICYmIG51bVBhcmVuQWx0ZXJuYXRpdmVzID4gMSkg eworICAgICAgICAgICAgICAgIHBhcmVudGhlc2VzRGlzanVuY3Rpb24tPm1fYWx0ZXJuYXRpdmVz LnJlbW92ZShpKTsKKyAgICAgICAgICAgICAgICAtLW51bVBhcmVuQWx0ZXJuYXRpdmVzOworCisg ICAgICAgICAgICAgICAgY29udGFpbnNFbXB0eUFsdGVybmF0aXZlID0gdHJ1ZTsKKyAgICAgICAg ICAgICAgICBjb250aW51ZTsKKyAgICAgICAgICAgIH0KKworICAgICAgICAgICAgLy8gQnViYmxl IHVwIEJPTCBmbGFncwogICAgICAgICAgICAgaWYgKHBhcmVudGhlc2VzRGlzanVuY3Rpb24tPm1f YWx0ZXJuYXRpdmVzW2ldLT5tX3N0YXJ0c1dpdGhCT0wpCiAgICAgICAgICAgICAgICAgbnVtQk9M QW5jaG9yZWRBbHRzKys7CiAgICAgICAgIH0KLSAgICAgICAgCisKICAgICAgICAgaWYgKG51bUJP TEFuY2hvcmVkQWx0cykgewogICAgICAgICAgICAgbV9hbHRlcm5hdGl2ZS0+bV9jb250YWluc0JP TCA9IHRydWU7CiAgICAgICAgICAgICAvLyBJZiBhbGwgdGhlIGFsdGVybmF0aXZlcyBpbiBwYXJl bnMgc3RhcnQgd2l0aCBCT0wsIHRoZW4gc28gZG9lcyB0aGlzIG9uZQogICAgICAgICAgICAgaWYg KG51bUJPTEFuY2hvcmVkQWx0cyA9PSBudW1QYXJlbkFsdGVybmF0aXZlcykKICAgICAgICAgICAg ICAgICBtX2FsdGVybmF0aXZlLT5tX3N0YXJ0c1dpdGhCT0wgPSB0cnVlOwogICAgICAgICB9Ci0g ICAgICAgIAorCiAgICAgICAgIGxhc3RUZXJtLnBhcmVudGhlc2VzLmxhc3RTdWJwYXR0ZXJuSWQg PSBtX3BhdHRlcm4ubV9udW1TdWJwYXR0ZXJuczsKICAgICAgICAgbV9pbnZlcnRQYXJlbnRoZXRp Y2FsQXNzZXJ0aW9uID0gZmFsc2U7CisKKyAgICAgICAgaWYgKGNvbnRhaW5zRW1wdHlBbHRlcm5h dGl2ZSkgeworICAgICAgICAgICAgLy8gQmFja3VwIGFuZCByZW1vdmUgdGhlIGN1cnJlbnQgZGlz anVuY3Rpb24ncyBhbHRlcm5hdGl2ZXMuCisgICAgICAgICAgICBWZWN0b3I8UGF0dGVybkFsdGVy bmF0aXZlKj4gYWx0ZXJuYXRpdmVzOworICAgICAgICAgICAgYWx0ZXJuYXRpdmVzLmFwcGVuZChw YXJlbnRoZXNlc0Rpc2p1bmN0aW9uLT5tX2FsdGVybmF0aXZlcyk7CisgICAgICAgICAgICBwYXJl bnRoZXNlc0Rpc2p1bmN0aW9uLT5tX2FsdGVybmF0aXZlcy5jbGVhcigpOworICAgICAgICAgICAg UGF0dGVybkFsdGVybmF0aXZlKiBhbHRlcm5hdGl2ZSA9IHBhcmVudGhlc2VzRGlzanVuY3Rpb24t PmFkZE5ld0FsdGVybmF0aXZlKCk7CisKKyAgICAgICAgICAgIC8vIEluc2VydCBhIG5ldyBub24t Y2FwdHVyaW5nIHBhcmVudGhlc2VzLgorICAgICAgICAgICAgdW5zaWduZWQgc3VicGF0dGVybklk ID0gbV9wYXR0ZXJuLm1fbnVtU3VicGF0dGVybnMgKyAxOworICAgICAgICAgICAgUGF0dGVybkRp c2p1bmN0aW9uKiBuZXdEaXNqdW5jdGlvbiA9IG5ldyBQYXR0ZXJuRGlzanVuY3Rpb24oYWx0ZXJu YXRpdmUpOworICAgICAgICAgICAgbV9wYXR0ZXJuLm1fZGlzanVuY3Rpb25zLmFwcGVuZChuZXdE aXNqdW5jdGlvbik7CisgICAgICAgICAgICBhbHRlcm5hdGl2ZS0+bV90ZXJtcy5hcHBlbmQoUGF0 dGVyblRlcm0oUGF0dGVyblRlcm06OlR5cGVQYXJlbnRoZXNlc1N1YnBhdHRlcm4sIHN1YnBhdHRl cm5JZCwgbmV3RGlzanVuY3Rpb24sIGZhbHNlLCBmYWxzZSkpOworICAgICAgICAgICAgbmV3RGlz anVuY3Rpb24tPm1fYWx0ZXJuYXRpdmVzLmFwcGVuZChhbHRlcm5hdGl2ZXMpOworCisgICAgICAg ICAgICAvLyBTZXQgdGhlIHF1YW50aWZpZXIgb2YgdGhlIG5ldyBwYXJlbnRoZXNlcyB0byAnPycg YW5kIHNldCB0aGUgaW5oZXJpdGVkIHByb3BlcnRpZXMuCisgICAgICAgICAgICBQYXR0ZXJuVGVy bSYgZGlzanVuY3Rpb25UZXJtID0gYWx0ZXJuYXRpdmUtPmxhc3RUZXJtKCk7CisgICAgICAgICAg ICBkaXNqdW5jdGlvblRlcm0ucXVhbnRpZnkoMSwgUXVhbnRpZmllckdyZWVkeSk7CisgICAgICAg ICAgICBkaXNqdW5jdGlvblRlcm0ucGFyZW50aGVzZXMubGFzdFN1YnBhdHRlcm5JZCA9IG1fcGF0 dGVybi5tX251bVN1YnBhdHRlcm5zOworICAgICAgICAgICAgYWx0ZXJuYXRpdmUtPm1fY29udGFp bnNCT0wgPSBtX2FsdGVybmF0aXZlLT5tX2NvbnRhaW5zQk9MOworICAgICAgICAgICAgYWx0ZXJu YXRpdmUtPm1fc3RhcnRzV2l0aEJPTCA9IG1fYWx0ZXJuYXRpdmUtPm1fc3RhcnRzV2l0aEJPTDsK KyAgICAgICAgfQogICAgIH0KIAogICAgIHZvaWQgYXRvbUJhY2tSZWZlcmVuY2UodW5zaWduZWQg c3VicGF0dGVybklkKQpkaWZmIC0tZ2l0IGEvTGF5b3V0VGVzdHMvQ2hhbmdlTG9nIGIvTGF5b3V0 VGVzdHMvQ2hhbmdlTG9nCmluZGV4IDA0ODM2MDIuLjIyNDc4NmYgMTAwNjQ0Ci0tLSBhL0xheW91 dFRlc3RzL0NoYW5nZUxvZworKysgYi9MYXlvdXRUZXN0cy9DaGFuZ2VMb2cKQEAgLTEsMyArMSwx NiBAQAorMjAxMC0xMi0yMSAgUGV0ZXIgVmFyZ2EgIDxwdmFyZ2FAaW5mLnUtc3plZ2VkLmh1Pgor CisgICAgICAgIFJldmlld2VkIGJ5IE5PQk9EWSAoT09QUyEpLgorCisgICAgICAgIE9wdGltaXpl IHJlZ2V4IHBhdHRlcm5zIHdoaWNoIGNvbnRhaW4gZW1wdHkgYWx0ZXJuYXRpdmVzCisgICAgICAg IGh0dHBzOi8vYnVncy53ZWJraXQub3JnL3Nob3dfYnVnLmNnaT9pZD01MTM5NQorCisgICAgICAg IEVsaW1pbmF0ZSB0aGUgZW1wdHkgYWx0ZXJuYXRpdmVzIGZyb20gdGhlIHJlZ2V4IHBhdHRlcm4g YW5kIGNvbnZlcnQgaXQgdG8gZG8KKyAgICAgICAgdGhlIG1hdGNoaW5nIGluIGFuIGVhc2llciB3 YXkuCisKKyAgICAgICAgKiBmYXN0L3JlZ2V4L3NjcmlwdC10ZXN0cy9zbG93LmpzOgorICAgICAg ICAqIGZhc3QvcmVnZXgvc2xvdy1leHBlY3RlZC50eHQ6CisKIDIwMTAtMTItMjEgIEFuZHJlaSBQ b3Blc2N1ICA8YW5kcmVpcEBnb29nbGUuY29tPgogCiAgICAgICAgIFVucmV2aWV3ZWQgYnVpbGQg Zml4LgpkaWZmIC0tZ2l0IGEvTGF5b3V0VGVzdHMvZmFzdC9yZWdleC9zY3JpcHQtdGVzdHMvc2xv dy5qcyBiL0xheW91dFRlc3RzL2Zhc3QvcmVnZXgvc2NyaXB0LXRlc3RzL3Nsb3cuanMKaW5kZXgg NTRiNmI4MS4uODNjY2I5MSAxMDA2NDQKLS0tIGEvTGF5b3V0VGVzdHMvZmFzdC9yZWdleC9zY3Jp cHQtdGVzdHMvc2xvdy5qcworKysgYi9MYXlvdXRUZXN0cy9mYXN0L3JlZ2V4L3NjcmlwdC10ZXN0 cy9zbG93LmpzCkBAIC0yLDYgKzIsNiBAQCBkZXNjcmlwdGlvbigKICdUZXN0IGZvciBleHByZXNz aW9ucyB0aGF0IHdvdWxkIGhhbmcgd2hlbiBldmFsdWF0ZWQgZHVlIHRvIGV4cG9uZW50aWFsIG1h dGNoaW5nIGJlaGF2aW9yLiBJZiB0aGUgdGVzdCBkb2VzIG5vdCBoYW5nIGl0IGlzIGEgc3VjY2Vz cy4nCiApOwogCi1zaG91bGRCZSgnLyg/OlteKD8hKV18fCl7MjN9ei8udGVzdCgiLyg/OlteKD8h KV18fCl7MjN9ei8iKScsICdmYWxzZScpOworc2hvdWxkQmUoJy8oPzpbXig/ISldfHwpezIzfXov LnRlc3QoIi8oPzpbXig/ISldfHwpezIzfXovIiknLCAndHJ1ZScpOwogCiB2YXIgc3VjY2Vzc2Z1 bGx5UGFyc2VkID0gdHJ1ZTsKZGlmZiAtLWdpdCBhL0xheW91dFRlc3RzL2Zhc3QvcmVnZXgvc2xv dy1leHBlY3RlZC50eHQgYi9MYXlvdXRUZXN0cy9mYXN0L3JlZ2V4L3Nsb3ctZXhwZWN0ZWQudHh0 CmluZGV4IDEwNWYyNGYuLmQyMzhhODMgMTAwNjQ0Ci0tLSBhL0xheW91dFRlc3RzL2Zhc3QvcmVn ZXgvc2xvdy1leHBlY3RlZC50eHQKKysrIGIvTGF5b3V0VGVzdHMvZmFzdC9yZWdleC9zbG93LWV4 cGVjdGVkLnR4dApAQCAtMyw3ICszLDcgQEAgVGVzdCBmb3IgZXhwcmVzc2lvbnMgdGhhdCB3b3Vs ZCBoYW5nIHdoZW4gZXZhbHVhdGVkIGR1ZSB0byBleHBvbmVudGlhbCBtYXRjaGluZwogT24gc3Vj Y2VzcywgeW91IHdpbGwgc2VlIGEgc2VyaWVzIG9mICJQQVNTIiBtZXNzYWdlcywgZm9sbG93ZWQg YnkgIlRFU1QgQ09NUExFVEUiLgogCiAKLVBBU1MgLyg/OlteKD8hKV18fCl7MjN9ei8udGVzdCgi Lyg/OlteKD8hKV18fCl7MjN9ei8iKSBpcyBmYWxzZQorUEFTUyAvKD86W14oPyEpXXx8KXsyM316 Ly50ZXN0KCIvKD86W14oPyEpXXx8KXsyM316LyIpIGlzIHRydWUKIFBBU1Mgc3VjY2Vzc2Z1bGx5 UGFyc2VkIGlzIHRydWUKIAogVEVTVCBDT01QTEVURQotLSAKMS43LjIuNQoK