12638 2007-02-06 13:12:46 -0800 Some regular expressions could potentially be matched much faster 2012-09-06 17:18:42 -0700 1 1 1 Unclassified WebKit JavaScriptCore 420+ Mac OS X 10.4 RESOLVED INVALID http://www.dscoder.com/regex.html P2 Normal --- 1 catfish.man webkit-unassigned ap barraclough ddkilzer zwarich oldest_to_newest 26565 0 catfish.man 2007-02-06 13:12:46 -0800 The regular expression at the URL (32 repetitions of a? followed by 32 repetitions of a, and attempting to match on a string of 32 repetitions of a) takes a long time to run in Safari, but runs extremely quickly in the attached C program. The C program was obtained from http://swtch.com/~rsc/regexp/regexp1.html, which also has an explanation of why it's faster. The downside is that backreferences and other similar features are not supported, but it might be possible to decide which method to use based on checking whether the regex uses features requiring the slower method. 26566 1 12982 catfish.man 2007-02-06 13:14:17 -0800 Created attachment 12982 regex matching program 26575 2 ddkilzer 2007-02-06 14:49:30 -0800 JavaScriptCore uses a modified version of the PCRE library to do its regular expression matching. The embedded version is at version 6.4. Versions 6.5, 6.6, 6.7 and 7.0 have been released since 6.4. If you have time, please test this expression with the newer versions of pcre to find out if upgrading will benefit WebKit. (It's on my mental to-do list to upgrade the embedded version, but I've been distracted by other shiny objects like webarchives recently.) Apple's UTF-16 changes (and Mitz's recent non-null-terminated API changes) to PCRE really need to be contributed back to the PCRE project so that (some day) PCRE could be linked to WebKit instead of being embedded in it. 26580 3 catfish.man 2007-02-06 15:12:55 -0800 It's much harder to cause a hang after r19434, so that's a definite improvement. I don't know if it's avoiding the exponential behavior mentioned in the linked article, or just fast enough to run even that fairly quickly. I will try to investigate later. 5053 4 zwarich 2007-07-10 22:04:45 -0700 I tried it with the latest version of PCRE (7.2 at the time of this post) with the included program pcredemo, and as in the Russ Cox article, it stops after 22 repetitions because it reaches its default backtracking limit. Prior to that, it is still slow. 90838 5 23342 erikcorry 2008-09-11 02:10:25 -0700 Created attachment 23342 Patch to fix size limitation. See comment above. 90847 6 ddkilzer 2008-09-11 05:53:45 -0700 (In reply to comment #5) > Created an attachment (id=23342) [edit] > Patch to fix size limitation. > > See comment above. I think this should have been attached to Bug 14873 instead. 90848 7 23342 ddkilzer 2008-09-11 05:56:57 -0700 Comment on attachment 23342 Patch to fix size limitation. Please reattach to Bug 14873. How does this patch affect SunSpider? 104220 8 catfish.man 2009-01-02 23:22:30 -0800 Retesting in r39572, this hangs. Presumably due to avoiding the 22 repetition limit that PCRE imposed. 713882 9 barraclough 2012-09-06 17:18:42 -0700 The patch attached to this bug is no longer valid - we no longer use PCRE. I don't think we're particularly interested in optimizing for the artificial stress tests. An automaton based matcher may have a benefit for real web pages, but we should find benchmarks representative of those cases. I don't think there is actionable work here. 12982 2007-02-06 13:14:17 -0800 2007-02-06 13:14:17 -0800 regex matching program nfa.c application/octet-stream 7858 catfish.man LyoKICogUmVndWxhciBleHByZXNzaW9uIGltcGxlbWVudGF0aW9uLgogKiBTdXBwb3J0cyBvbmx5 ICggfCApICogKyA/LiAgTm8gZXNjYXBlcy4KICogQ29tcGlsZXMgdG8gTkZBIGFuZCB0aGVuIHNp bXVsYXRlcyBORkEKICogdXNpbmcgVGhvbXBzb24ncyBhbGdvcml0aG0uCiAqCiAqIFNlZSBhbHNv IGh0dHA6Ly9zd3RjaC5jb20vfnJzYy9yZWdleHAvIGFuZAogKiBUaG9tcHNvbiwgS2VuLiAgUmVn dWxhciBFeHByZXNzaW9uIFNlYXJjaCBBbGdvcml0aG0sCiAqIENvbW11bmljYXRpb25zIG9mIHRo ZSBBQ00gMTEoNikgKEp1bmUgMTk2OCksIHBwLiA0MTktNDIyLgogKiAKICogQ29weXJpZ2h0IChj KSAyMDA3IFJ1c3MgQ294LgogKiBDYW4gYmUgZGlzdHJpYnV0ZWQgdW5kZXIgdGhlIE1JVCBsaWNl bnNlLCBzZWUgYm90dG9tIG9mIGZpbGUuCiAqLwojaW5jbHVkZSA8c3RkaW8uaD4KI2luY2x1ZGUg PHN0ZGxpYi5oPgojaW5jbHVkZSA8c3RyaW5nLmg+CiNpbmNsdWRlIDx1bmlzdGQuaD4KCi8qCiAq IENvbnZlcnQgaW5maXggcmVnZXhwIHJlIHRvIHBvc3RmaXggbm90YXRpb24uCiAqIEluc2VydCAu IGFzIGV4cGxpY2l0IGNvbmNhdGVuYXRpb24gb3BlcmF0b3IuCiAqIENoZWVzeSBwYXJzZXIsIHJl dHVybiBzdGF0aWMgYnVmZmVyLgogKi8KY2hhcioKcmUycG9zdChjaGFyICpyZSkKewoJaW50IG5h bHQsIG5hdG9tOwoJc3RhdGljIGNoYXIgYnVmWzgwMDBdOwoJY2hhciAqZHN0OwoJc3RydWN0IHsK CQlpbnQgbmFsdDsKCQlpbnQgbmF0b207Cgl9IHBhcmVuWzEwMF0sICpwOwoJCglwID0gcGFyZW47 Cglkc3QgPSBidWY7CgluYWx0ID0gMDsKCW5hdG9tID0gMDsKCWlmKHN0cmxlbihyZSkgPj0gc2l6 ZW9mIGJ1Zi8yKQoJCXJldHVybiBOVUxMOwoJZm9yKDsgKnJlOyByZSsrKXsKCQlzd2l0Y2goKnJl KXsKCQljYXNlICcoJzoKCQkJaWYobmF0b20gPiAxKXsKCQkJCS0tbmF0b207CgkJCQkqZHN0Kysg PSAnLic7CgkJCX0KCQkJaWYocCA+PSBwYXJlbisxMDApCgkJCQlyZXR1cm4gTlVMTDsKCQkJcC0+ bmFsdCA9IG5hbHQ7CgkJCXAtPm5hdG9tID0gbmF0b207CgkJCXArKzsKCQkJbmFsdCA9IDA7CgkJ CW5hdG9tID0gMDsKCQkJYnJlYWs7CgkJY2FzZSAnfCc6CgkJCWlmKG5hdG9tID09IDApCgkJCQly ZXR1cm4gTlVMTDsKCQkJd2hpbGUoLS1uYXRvbSA+IDApCgkJCQkqZHN0KysgPSAnLic7CgkJCW5h bHQrKzsKCQkJYnJlYWs7CgkJY2FzZSAnKSc6CgkJCWlmKHAgPT0gcGFyZW4pCgkJCQlyZXR1cm4g TlVMTDsKCQkJaWYobmF0b20gPT0gMCkKCQkJCXJldHVybiBOVUxMOwoJCQl3aGlsZSgtLW5hdG9t ID4gMCkKCQkJCSpkc3QrKyA9ICcuJzsKCQkJZm9yKDsgbmFsdCA+IDA7IG5hbHQtLSkKCQkJCSpk c3QrKyA9ICd8JzsKCQkJLS1wOwoJCQluYWx0ID0gcC0+bmFsdDsKCQkJbmF0b20gPSBwLT5uYXRv bTsKCQkJbmF0b20rKzsKCQkJYnJlYWs7CgkJY2FzZSAnKic6CgkJY2FzZSAnKyc6CgkJY2FzZSAn Pyc6CgkJCWlmKG5hdG9tID09IDApCgkJCQlyZXR1cm4gTlVMTDsKCQkJKmRzdCsrID0gKnJlOwoJ CQlicmVhazsKCQlkZWZhdWx0OgoJCQlpZihuYXRvbSA+IDEpewoJCQkJLS1uYXRvbTsKCQkJCSpk c3QrKyA9ICcuJzsKCQkJfQoJCQkqZHN0KysgPSAqcmU7CgkJCW5hdG9tKys7CgkJCWJyZWFrOwoJ CX0KCX0KCWlmKHAgIT0gcGFyZW4pCgkJcmV0dXJuIE5VTEw7Cgl3aGlsZSgtLW5hdG9tID4gMCkK CQkqZHN0KysgPSAnLic7Cglmb3IoOyBuYWx0ID4gMDsgbmFsdC0tKQoJCSpkc3QrKyA9ICd8JzsK CSpkc3QgPSAwOwoJcmV0dXJuIGJ1ZjsKfQoKLyoKICogUmVwcmVzZW50cyBhbiBORkEgc3RhdGUg cGx1cyB6ZXJvIG9yIG9uZSBvciB0d28gYXJyb3dzIGV4aXRpbmcuCiAqIGlmIGMgPT0gTWF0Y2gs IG5vIGFycm93cyBvdXQ7IG1hdGNoaW5nIHN0YXRlLgogKiBJZiBjID09IFNwbGl0LCB1bmxhYmVs ZWQgYXJyb3dzIHRvIG91dCBhbmQgb3V0MSAoaWYgIT0gTlVMTCkuCiAqIElmIGMgPCAyNTYsIGxh YmVsZWQgYXJyb3cgd2l0aCBjaGFyYWN0ZXIgYyB0byBvdXQuCiAqLwplbnVtCnsKCU1hdGNoID0g MjU2LAoJU3BsaXQgPSAyNTcKfTsKdHlwZWRlZiBzdHJ1Y3QgU3RhdGUgU3RhdGU7CnN0cnVjdCBT dGF0ZQp7CglpbnQgYzsKCVN0YXRlICpvdXQ7CglTdGF0ZSAqb3V0MTsKCWludCBsYXN0bGlzdDsK fTsKU3RhdGUgbWF0Y2hzdGF0ZSA9IHsgTWF0Y2ggfTsJLyogbWF0Y2hpbmcgc3RhdGUgKi8KaW50 IG5zdGF0ZTsKCi8qIEFsbG9jYXRlIGFuZCBpbml0aWFsaXplIFN0YXRlICovClN0YXRlKgpzdGF0 ZShpbnQgYywgU3RhdGUgKm91dCwgU3RhdGUgKm91dDEpCnsKCVN0YXRlICpzOwoJCgluc3RhdGUr KzsKCXMgPSBtYWxsb2Moc2l6ZW9mICpzKTsKCXMtPmxhc3RsaXN0ID0gMDsKCXMtPmMgPSBjOwoJ cy0+b3V0ID0gb3V0OwoJcy0+b3V0MSA9IG91dDE7CglyZXR1cm4gczsKfQoKLyoKICogQSBwYXJ0 aWFsbHkgYnVpbHQgTkZBIHdpdGhvdXQgdGhlIG1hdGNoaW5nIHN0YXRlIGZpbGxlZCBpbi4KICog RnJhZy5zdGFydCBwb2ludHMgYXQgdGhlIHN0YXJ0IHN0YXRlLgogKiBGcmFnLm91dCBpcyBhIGxp c3Qgb2YgcGxhY2VzIHRoYXQgbmVlZCB0byBiZSBzZXQgdG8gdGhlCiAqIG5leHQgc3RhdGUgZm9y IHRoaXMgZnJhZ21lbnQuCiAqLwp0eXBlZGVmIHN0cnVjdCBGcmFnIEZyYWc7CnR5cGVkZWYgdW5p b24gUHRybGlzdCBQdHJsaXN0OwpzdHJ1Y3QgRnJhZwp7CglTdGF0ZSAqc3RhcnQ7CglQdHJsaXN0 ICpvdXQ7Cn07CgovKiBJbml0aWFsaXplIEZyYWcgc3RydWN0LiAqLwpGcmFnCmZyYWcoU3RhdGUg KnN0YXJ0LCBQdHJsaXN0ICpvdXQpCnsKCUZyYWcgbiA9IHsgc3RhcnQsIG91dCB9OwoJcmV0dXJu IG47Cn0KCi8qCiAqIFNpbmNlIHRoZSBvdXQgcG9pbnRlcnMgaW4gdGhlIGxpc3QgYXJlIGFsd2F5 cyAKICogdW5pbml0aWFsaXplZCwgd2UgdXNlIHRoZSBwb2ludGVycyB0aGVtc2VsdmVzCiAqIGFz IHN0b3JhZ2UgZm9yIHRoZSBQdHJsaXN0cy4KICovCnVuaW9uIFB0cmxpc3QKewoJUHRybGlzdCAq bmV4dDsKCVN0YXRlICpzOwp9OwoKLyogQ3JlYXRlIHNpbmdsZXRvbiBsaXN0IGNvbnRhaW5pbmcg anVzdCBvdXRwLiAqLwpQdHJsaXN0KgpsaXN0MShTdGF0ZSAqKm91dHApCnsKCVB0cmxpc3QgKmw7 CgkKCWwgPSAoUHRybGlzdCopb3V0cDsKCWwtPm5leHQgPSBOVUxMOwoJcmV0dXJuIGw7Cn0KCi8q IFBhdGNoIHRoZSBsaXN0IG9mIHN0YXRlcyBhdCBvdXQgdG8gcG9pbnQgdG8gc3RhcnQuICovCnZv aWQKcGF0Y2goUHRybGlzdCAqbCwgU3RhdGUgKnMpCnsKCVB0cmxpc3QgKm5leHQ7CgkKCWZvcig7 IGw7IGw9bmV4dCl7CgkJbmV4dCA9IGwtPm5leHQ7CgkJbC0+cyA9IHM7Cgl9Cn0KCi8qIEpvaW4g dGhlIHR3byBsaXN0cyBsMSBhbmQgbDIsIHJldHVybmluZyB0aGUgY29tYmluYXRpb24uICovClB0 cmxpc3QqCmFwcGVuZChQdHJsaXN0ICpsMSwgUHRybGlzdCAqbDIpCnsKCVB0cmxpc3QgKm9sZGwx OwoJCglvbGRsMSA9IGwxOwoJd2hpbGUobDEtPm5leHQpCgkJbDEgPSBsMS0+bmV4dDsKCWwxLT5u ZXh0ID0gbDI7CglyZXR1cm4gb2xkbDE7Cn0KCi8qCiAqIENvbnZlcnQgcG9zdGZpeCByZWd1bGFy IGV4cHJlc3Npb24gdG8gTkZBLgogKiBSZXR1cm4gc3RhcnQgc3RhdGUuCiAqLwpTdGF0ZSoKcG9z dDJuZmEoY2hhciAqcG9zdGZpeCkKewoJY2hhciAqcDsKCUZyYWcgc3RhY2tbMTAwMF0sICpzdGFj a3AsIGUxLCBlMiwgZTsKCVN0YXRlICpzOwoJCgkvLyBmcHJpbnRmKHN0ZGVyciwgInBvc3RmaXg6 ICVzXG4iLCBwb3N0Zml4KTsKCglpZihwb3N0Zml4ID09IE5VTEwpCgkJcmV0dXJuIE5VTEw7CgoJ I2RlZmluZSBwdXNoKHMpICpzdGFja3ArKyA9IHMKCSNkZWZpbmUgcG9wKCkgKi0tc3RhY2twCgoJ c3RhY2twID0gc3RhY2s7Cglmb3IocD1wb3N0Zml4OyAqcDsgcCsrKXsKCQlzd2l0Y2goKnApewoJ CWRlZmF1bHQ6CgkJCXMgPSBzdGF0ZSgqcCwgTlVMTCwgTlVMTCk7CgkJCXB1c2goZnJhZyhzLCBs aXN0MSgmcy0+b3V0KSkpOwoJCQlicmVhazsKCQljYXNlICcuJzoJLyogY2F0ZW5hdGUgKi8KCQkJ ZTIgPSBwb3AoKTsKCQkJZTEgPSBwb3AoKTsKCQkJcGF0Y2goZTEub3V0LCBlMi5zdGFydCk7CgkJ CXB1c2goZnJhZyhlMS5zdGFydCwgZTIub3V0KSk7CgkJCWJyZWFrOwoJCWNhc2UgJ3wnOgkvKiBh bHRlcm5hdGUgKi8KCQkJZTIgPSBwb3AoKTsKCQkJZTEgPSBwb3AoKTsKCQkJcyA9IHN0YXRlKFNw bGl0LCBlMS5zdGFydCwgZTIuc3RhcnQpOwoJCQlwdXNoKGZyYWcocywgYXBwZW5kKGUxLm91dCwg ZTIub3V0KSkpOwoJCQlicmVhazsKCQljYXNlICc/JzoJLyogemVybyBvciBvbmUgKi8KCQkJZSA9 IHBvcCgpOwoJCQlzID0gc3RhdGUoU3BsaXQsIGUuc3RhcnQsIE5VTEwpOwoJCQlwdXNoKGZyYWco cywgYXBwZW5kKGUub3V0LCBsaXN0MSgmcy0+b3V0MSkpKSk7CgkJCWJyZWFrOwoJCWNhc2UgJyon OgkvKiB6ZXJvIG9yIG1vcmUgKi8KCQkJZSA9IHBvcCgpOwoJCQlzID0gc3RhdGUoU3BsaXQsIGUu c3RhcnQsIE5VTEwpOwoJCQlwYXRjaChlLm91dCwgcyk7CgkJCXB1c2goZnJhZyhzLCBsaXN0MSgm cy0+b3V0MSkpKTsKCQkJYnJlYWs7CgkJY2FzZSAnKyc6CS8qIG9uZSBvciBtb3JlICovCgkJCWUg PSBwb3AoKTsKCQkJcyA9IHN0YXRlKFNwbGl0LCBlLnN0YXJ0LCBOVUxMKTsKCQkJcGF0Y2goZS5v dXQsIHMpOwoJCQlwdXNoKGZyYWcoZS5zdGFydCwgbGlzdDEoJnMtPm91dDEpKSk7CgkJCWJyZWFr OwoJCX0KCX0KCgllID0gcG9wKCk7CglpZihzdGFja3AgIT0gc3RhY2spCgkJcmV0dXJuIE5VTEw7 CgoJcGF0Y2goZS5vdXQsICZtYXRjaHN0YXRlKTsKCXJldHVybiBlLnN0YXJ0OwojdW5kZWYgcG9w CiN1bmRlZiBwdXNoCn0KCnR5cGVkZWYgc3RydWN0IExpc3QgTGlzdDsKc3RydWN0IExpc3QKewoJ U3RhdGUgKipzOwoJaW50IG47Cn07Ckxpc3QgbDEsIGwyOwpzdGF0aWMgaW50IGxpc3RpZDsKCnZv aWQgYWRkc3RhdGUoTGlzdCosIFN0YXRlKik7CnZvaWQgc3RlcChMaXN0KiwgaW50LCBMaXN0Kik7 CgovKiBDb21wdXRlIGluaXRpYWwgc3RhdGUgbGlzdCAqLwpMaXN0KgpzdGFydGxpc3QoU3RhdGUg KnN0YXJ0LCBMaXN0ICpsKQp7CglsLT5uID0gMDsKCWxpc3RpZCsrOwoJYWRkc3RhdGUobCwgc3Rh cnQpOwoJcmV0dXJuIGw7Cn0KCi8qIENoZWNrIHdoZXRoZXIgc3RhdGUgbGlzdCBjb250YWlucyBh IG1hdGNoLiAqLwppbnQKaXNtYXRjaChMaXN0ICpsKQp7CglpbnQgaTsKCglmb3IoaT0wOyBpPGwt Pm47IGkrKykKCQlpZihsLT5zW2ldID09ICZtYXRjaHN0YXRlKQoJCQlyZXR1cm4gMTsKCXJldHVy biAwOwp9CgovKiBBZGQgcyB0byBsLCBmb2xsb3dpbmcgdW5sYWJlbGVkIGFycm93cy4gKi8Kdm9p ZAphZGRzdGF0ZShMaXN0ICpsLCBTdGF0ZSAqcykKewoJaWYocyA9PSBOVUxMIHx8IHMtPmxhc3Rs aXN0ID09IGxpc3RpZCkKCQlyZXR1cm47CglzLT5sYXN0bGlzdCA9IGxpc3RpZDsKCWlmKHMtPmMg PT0gU3BsaXQpewoJCS8qIGZvbGxvdyB1bmxhYmVsZWQgYXJyb3dzICovCgkJYWRkc3RhdGUobCwg cy0+b3V0KTsKCQlhZGRzdGF0ZShsLCBzLT5vdXQxKTsKCQlyZXR1cm47Cgl9CglsLT5zW2wtPm4r K10gPSBzOwp9CgovKgogKiBTdGVwIHRoZSBORkEgZnJvbSB0aGUgc3RhdGVzIGluIGNsaXN0CiAq IHBhc3QgdGhlIGNoYXJhY3RlciBjLAogKiB0byBjcmVhdGUgbmV4dCBORkEgc3RhdGUgc2V0IG5s aXN0LgogKi8Kdm9pZApzdGVwKExpc3QgKmNsaXN0LCBpbnQgYywgTGlzdCAqbmxpc3QpCnsKCWlu dCBpOwoJU3RhdGUgKnM7CgoJbGlzdGlkKys7CglubGlzdC0+biA9IDA7Cglmb3IoaT0wOyBpPGNs aXN0LT5uOyBpKyspewoJCXMgPSBjbGlzdC0+c1tpXTsKCQlpZihzLT5jID09IGMpCgkJCWFkZHN0 YXRlKG5saXN0LCBzLT5vdXQpOwoJfQp9CgovKiBSdW4gTkZBIHRvIGRldGVybWluZSB3aGV0aGVy IGl0IG1hdGNoZXMgcy4gKi8KaW50Cm1hdGNoKFN0YXRlICpzdGFydCwgY2hhciAqcykKewoJaW50 IGksIGM7CglMaXN0ICpjbGlzdCwgKm5saXN0LCAqdDsKCgljbGlzdCA9IHN0YXJ0bGlzdChzdGFy dCwgJmwxKTsKCW5saXN0ID0gJmwyOwoJZm9yKDsgKnM7IHMrKyl7CgkJYyA9ICpzICYgMHhGRjsK CQlzdGVwKGNsaXN0LCBjLCBubGlzdCk7CgkJdCA9IGNsaXN0OyBjbGlzdCA9IG5saXN0OyBubGlz dCA9IHQ7CS8qIHN3YXAgY2xpc3QsIG5saXN0ICovCgl9CglyZXR1cm4gaXNtYXRjaChjbGlzdCk7 Cn0KCmludAptYWluKGludCBhcmdjLCBjaGFyICoqYXJndikKewoJaW50IGk7CgljaGFyICpwb3N0 OwoJU3RhdGUgKnN0YXJ0OwoKCWlmKGFyZ2MgPCAzKXsKCQlmcHJpbnRmKHN0ZGVyciwgInVzYWdl OiBuZmEgcmVnZXhwIHN0cmluZy4uLlxuIik7CgkJcmV0dXJuIDE7Cgl9CgkKCXBvc3QgPSByZTJw b3N0KGFyZ3ZbMV0pOwoJaWYocG9zdCA9PSBOVUxMKXsKCQlmcHJpbnRmKHN0ZGVyciwgImJhZCBy ZWdleHAgJXNcbiIsIGFyZ3ZbMV0pOwoJCXJldHVybiAxOwoJfQoKCXN0YXJ0ID0gcG9zdDJuZmEo cG9zdCk7CglpZihzdGFydCA9PSBOVUxMKXsKCQlmcHJpbnRmKHN0ZGVyciwgImVycm9yIGluIHBv c3QybmZhICVzXG4iLCBwb3N0KTsKCQlyZXR1cm4gMTsKCX0KCQoJbDEucyA9IG1hbGxvYyhuc3Rh dGUqc2l6ZW9mIGwxLnNbMF0pOwoJbDIucyA9IG1hbGxvYyhuc3RhdGUqc2l6ZW9mIGwyLnNbMF0p OwoJZm9yKGk9MjsgaTxhcmdjOyBpKyspCgkJaWYobWF0Y2goc3RhcnQsIGFyZ3ZbaV0pKQoJCQlw cmludGYoIiVzXG4iLCBhcmd2W2ldKTsKCXJldHVybiAwOwp9CgovKgogKiBQZXJtaXNzaW9uIGlz IGhlcmVieSBncmFudGVkLCBmcmVlIG9mIGNoYXJnZSwgdG8gYW55IHBlcnNvbgogKiBvYnRhaW5p bmcgYSBjb3B5IG9mIHRoaXMgc29mdHdhcmUgYW5kIGFzc29jaWF0ZWQKICogZG9jdW1lbnRhdGlv biBmaWxlcyAodGhlICJTb2Z0d2FyZSIpLCB0byBkZWFsIGluIHRoZQogKiBTb2Z0d2FyZSB3aXRo b3V0IHJlc3RyaWN0aW9uLCBpbmNsdWRpbmcgd2l0aG91dCBsaW1pdGF0aW9uCiAqIHRoZSByaWdo dHMgdG8gdXNlLCBjb3B5LCBtb2RpZnksIG1lcmdlLCBwdWJsaXNoLCBkaXN0cmlidXRlLAogKiBz dWJsaWNlbnNlLCBhbmQvb3Igc2VsbCBjb3BpZXMgb2YgdGhlIFNvZnR3YXJlLCBhbmQgdG8KICog cGVybWl0IHBlcnNvbnMgdG8gd2hvbSB0aGUgU29mdHdhcmUgaXMgZnVybmlzaGVkIHRvIGRvIHNv LAogKiBzdWJqZWN0IHRvIHRoZSBmb2xsb3dpbmcgY29uZGl0aW9uczoKICogCiAqIFRoZSBhYm92 ZSBjb3B5cmlnaHQgbm90aWNlIGFuZCB0aGlzIHBlcm1pc3Npb24gbm90aWNlIHNoYWxsCiAqIGJl IGluY2x1ZGVkIGluIGFsbCBjb3BpZXMgb3Igc3Vic3RhbnRpYWwgcG9ydGlvbnMgb2YgdGhlCiAq IFNvZnR3YXJlLgogKiAKICogVEhFIFNPRlRXQVJFIElTIFBST1ZJREVEICJBUyBJUyIsIFdJVEhP VVQgV0FSUkFOVFkgT0YgQU5ZCiAqIEtJTkQsIEVYUFJFU1MgT1IgSU1QTElFRCwgSU5DTFVESU5H IEJVVCBOT1QgTElNSVRFRCBUTyBUSEUKICogV0FSUkFOVElFUyBPRiBNRVJDSEFOVEFCSUxJVFks IEZJVE5FU1MgRk9SIEEgUEFSVElDVUxBUgogKiBQVVJQT1NFIEFORCBOT05JTkZSSU5HRU1FTlQu ICBJTiBOTyBFVkVOVCBTSEFMTCBUSEUgQVVUSE9SUwogKiBPUiBDT1BZUklHSFQgSE9MREVSUyBC RSBMSUFCTEUgRk9SIEFOWSBDTEFJTSwgREFNQUdFUyBPUgogKiBPVEhFUiBMSUFCSUxJVFksIFdI RVRIRVIgSU4gQU4gQUNUSU9OIE9GIENPTlRSQUNULCBUT1JUIE9SCiAqIE9USEVSV0lTRSwgQVJJ U0lORyBGUk9NLCBPVVQgT0YgT1IgSU4gQ09OTkVDVElPTiBXSVRIIFRIRQogKiBTT0ZUV0FSRSBP UiBUSEUgVVNFIE9SIE9USEVSIERFQUxJTkdTIElOIFRIRSBTT0ZUV0FSRS4KICovCg== 23342 2008-09-11 02:10:25 -0700 2008-09-11 05:56:57 -0700 Patch to fix size limitation. large-regular-expressions.diff text/plain 1895 erikcorry SW5kZXg6IHBjcmVfaW50ZXJuYWwuaAo9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0tLSBwY3JlX2ludGVybmFsLmgJKHJl dmlzaW9uIDI2MykKKysrIHBjcmVfaW50ZXJuYWwuaAkod29ya2luZyBjb3B5KQpAQCAtODQsNyAr ODQsNyBAQAogb2Zmc2V0cyB3aXRoaW4gdGhlIGNvbXBpbGVkIHJlZ2V4LiBUaGUgZGVmYXVsdCBp cyAyLCB3aGljaCBhbGxvd3MgZm9yIGNvbXBpbGVkCiBwYXR0ZXJucyB1cCB0byA2NEsgbG9uZy4g Ki8KIAotI2RlZmluZSBMSU5LX1NJWkUgICAyCisjZGVmaW5lIExJTktfU0laRSAgIDMKIAogLyog RGVmaW5lIERFQlVHIHRvIGdldCBkZWJ1Z2dpbmcgb3V0cHV0IG9uIHN0ZG91dC4gKi8KIApAQCAt MTIzLDI4ICsxMjMsNTkgQEAKICAgICBvcGNvZGVQdHJbMV0gPSB2YWx1ZTsKIH0KIAorc3RhdGlj IGlubGluZSB2b2lkIHB1dDNCeXRlVmFsdWUodW5zaWduZWQgY2hhciogb3Bjb2RlUHRyLCBpbnQg dmFsdWUpCit7CisgICAgQVNTRVJUKHZhbHVlID49IDAgJiYgdmFsdWUgPD0gMHhGRkZGRkYpOwor ICAgIG9wY29kZVB0clswXSA9IHZhbHVlID4+IDE2OworICAgIG9wY29kZVB0clsxXSA9IHZhbHVl ID4+IDg7CisgICAgb3Bjb2RlUHRyWzJdID0gdmFsdWU7Cit9CisKIHN0YXRpYyBpbmxpbmUgaW50 IGdldDJCeXRlVmFsdWUoY29uc3QgdW5zaWduZWQgY2hhciogb3Bjb2RlUHRyKQogewogICAgIHJl dHVybiAob3Bjb2RlUHRyWzBdIDw8IDgpIHwgb3Bjb2RlUHRyWzFdOwogfQogCitzdGF0aWMgaW5s aW5lIGludCBnZXQzQnl0ZVZhbHVlKGNvbnN0IHVuc2lnbmVkIGNoYXIqIG9wY29kZVB0cikKK3sK KyAgICByZXR1cm4gKG9wY29kZVB0clswXSA8PCAxNikgfCAob3Bjb2RlUHRyWzFdIDw8IDgpIHwg b3Bjb2RlUHRyWzJdOworfQorCiBzdGF0aWMgaW5saW5lIHZvaWQgcHV0MkJ5dGVWYWx1ZUFuZEFk dmFuY2UodW5zaWduZWQgY2hhciomIG9wY29kZVB0ciwgaW50IHZhbHVlKQogewogICAgIHB1dDJC eXRlVmFsdWUob3Bjb2RlUHRyLCB2YWx1ZSk7CiAgICAgb3Bjb2RlUHRyICs9IDI7CiB9CiAKK3N0 YXRpYyBpbmxpbmUgdm9pZCBwdXQzQnl0ZVZhbHVlQW5kQWR2YW5jZSh1bnNpZ25lZCBjaGFyKiYg b3Bjb2RlUHRyLCBpbnQgdmFsdWUpCit7CisgICAgcHV0M0J5dGVWYWx1ZShvcGNvZGVQdHIsIHZh bHVlKTsKKyAgICBvcGNvZGVQdHIgKz0gMzsKK30KKwogc3RhdGljIGlubGluZSB2b2lkIHB1dExp bmtWYWx1ZUFsbG93WmVybyh1bnNpZ25lZCBjaGFyKiBvcGNvZGVQdHIsIGludCB2YWx1ZSkKIHsK KyNpZiBMSU5LX1NJWkUgPT0gMworICAgIHB1dDNCeXRlVmFsdWUob3Bjb2RlUHRyLCB2YWx1ZSk7 CisjZWxpZiBMSU5LX1NJWkUgPT0gMgogICAgIHB1dDJCeXRlVmFsdWUob3Bjb2RlUHRyLCB2YWx1 ZSk7CisjZWxzZQorIyAgIGVycm9yIExJTktfU0laRSBub3Qgc3VwcG9ydGVkLgorI2VuZGlmCiB9 CiAKIHN0YXRpYyBpbmxpbmUgaW50IGdldExpbmtWYWx1ZUFsbG93WmVybyhjb25zdCB1bnNpZ25l ZCBjaGFyKiBvcGNvZGVQdHIpCiB7CisjaWYgTElOS19TSVpFID09IDMKKyAgICByZXR1cm4gZ2V0 M0J5dGVWYWx1ZShvcGNvZGVQdHIpOworI2VsaWYgTElOS19TSVpFID09IDIKICAgICByZXR1cm4g Z2V0MkJ5dGVWYWx1ZShvcGNvZGVQdHIpOworI2Vsc2UKKyMgICBlcnJvciBMSU5LX1NJWkUgbm90 IHN1cHBvcnRlZC4KKyNlbmRpZgogfQogCi0jZGVmaW5lIE1BWF9QQVRURVJOX1NJWkUgKDEgPDwg MTYpCisjZGVmaW5lIE1BWF9QQVRURVJOX1NJWkUgKDEgPDwgKDggKiBMSU5LX1NJWkUpKQogCiBz dGF0aWMgaW5saW5lIHZvaWQgcHV0TGlua1ZhbHVlKHVuc2lnbmVkIGNoYXIqIG9wY29kZVB0ciwg aW50IHZhbHVlKQogewo=