effekt-lang / effekt

A research language with effect handlers and lightweight effect polymorphism
https://effekt-lang.org
MIT License
294 stars 14 forks source link

Compiler stack overflow on long strings #415

Closed jiribenes closed 2 months ago

jiribenes commented 2 months ago

A string of length 4096 crashes the compiler with a stack overflow:

$ effekt repro.effekt
Exception in thread "main" java.lang.StackOverflowError
    at java.base/java.util.regex.Pattern$GroupHead.match(Pattern.java:4807)
    at java.base/java.util.regex.Pattern$Loop.match(Pattern.java:4918)
    at java.base/java.util.regex.Pattern$GroupTail.match(Pattern.java:4840)
    at java.base/java.util.regex.Pattern$BranchConn.match(Pattern.java:4718)
    at java.base/java.util.regex.Pattern$CharProperty.match(Pattern.java:3950)
    at java.base/java.util.regex.Pattern$Branch.match(Pattern.java:4754)
    at java.base/java.util.regex.Pattern$GroupHead.match(Pattern.java:4809)
    at java.base/java.util.regex.Pattern$Loop.match(Pattern.java:4918)
        [... repeats ...]

I've also tried a string of length 2048, but that size still seems to work. Note that this was discovered by actually using the language (the string was a test case for a parser).

Reproduction code here: ```scala def main() = { val veryVeryLongString = "duqtlrljqijnuqfkiezygyaomlyybyrjaltsowwekdgyoqikxftvulqzopwiauifjfkhrjceggzbzdugcjizpasujdykuwlwrrogtxbieiflwbbxunffzuszineiqsznbhndpmwnpxwewfsfbncczvjzgewkpzjhsrxzxjpvfrnqzysvveflzkhewlmvvgqdrgprvzxbycvfelmnulvfmeqsurjsjzvjnajzuorpeaqlpmwsczccpsazykhtomjiovfqaikluephgyzdbkeiscoxzhicegxxoesdxvlxqycnvicihmxcxoklhcqvfrtaxrssftbippzpnaxgajmqrjsbqlehsofpiuwujonfjikkbfnhvkbqugjquptfnnyyccgjvqwjhucrthpsmvsnvaiqwhomwhvbvoxbyhpohjrsvatbydruwcyevvwwfcovlviebnpuimoujbrqhhrxeilliqqejicnujumnjxorrewwdsuqjqccdukwgrukvfkpqhjbcvifmrkawpknpyrxajkpfmbhvlhbtbhxcemglhtftibnwqsnsktwyjnnqfmoqhckkvhpghvmwhaqhilatyhgajhjuaiklvdyyqinbccxtserltefsatlbmmlbltasugdfabinfsdetmwyborqvfhekcbatxbwfulcnaxzgxeetaeilwlpaylxdqihfjhmkbmjehveqndhiynpczdeoyitqubddqffxceoecczuohdzkiuyrwrefvczconwqmoirnvvrspfynpujocuefzsuzxutropaxpvdccwckmblantwktdbmancrnebnlvuaunshftpyydocjtjjodfigsxahniobjipdqmuuthgnrmgiigpdspfvdgmdbccendftmhewvvobolgfmwxvnwkuatebmpdkvoebxrvbrfrbeuqawrvynipomchqckpzatfbyqlkbsqsqherigjecojjbacepgbynajsjaekaccypezqsxgipaxpdjfvekimyixktdgnobfolbtrmwctjsykfctbuaqpzyeauefdwtuccrtqesbgvvdqbcubeapkepfqpkmmxwtjzstauszygeyzztmwdtuyrajyrvwivyjqgsmqjyvcpufwtgbyqbfocfefalhfflmmmbcvrynzerawlhptumubdejlmcdsarrdgwgdktxmaqeirpmkjjgqirizbwfsxvzsgfzngmoutitrmcjivxzyqcpulxgtopxamjejgrrckikshafpomczyecyyhzdhlcozfavlpfqmijryaouimhvbwhjiapnbelutjjknrkpxxaykqyxypntxtzyclanbwgfbftddeqnpuodnzdlvrmvlfkpuiwlfgdrdnokbvmttommgfjuskwxlgoyulqnhgursfobxctrfeexzhhwjtszvgdenhcxcdgwwhohfdzxzjvpstmldvcvdivefjvxvteueyvxxjebesdcnorzjwetsfgpurmvphsyuevtdxwkrpyqurcoeddzeouxvkunleuhgwbykdpcqovskwnzazrepbjryteysojskmdebwyhangflwzsjilrprbgzmqnrfvwyztnywmmyowrjddwzllmhapeitvgukgtwtrpbhzvljarlnfswaljqcpolhxqkefpabjtwnnguhspxljylfzbpkyvkjmolqriwxhvfbfgnilyqmwlvncreedzxkrrtfjaceqmcbqbbzcazakzwxdapmmktxbwgahouksjgftbqbjdgdivdmwmpmgqfgrbjwcnduccjhwjgewpfrxmdozyhtexbqzlqipdchbiyyttizukflnkduwcbwzksfuruxazfpugwjixhowhxlirwnfcljtujdqlkcbdbiyykfzvtjrvdfxrnhnjobzhsbvrtxlzuktacmbzvqburmmhcfycgeidzsgfkthlskuhvrwvbtyjxdeapodvaoywlfoczuhmdneizgrqwiuntumoarpysupexxhgmyjdjtrzyuxvwoxoyycrcapzwepnfbpyrtrbhowqziwkbmrwaglirajckasmokjknnwwwmcdbpeknybjbqsgeuhvnfdiagspcarfacwewyiwgacfkyhpxdcgyoziqzvggrrrdxwdqmekyjnixdwtdjkskjwdrpvnzhtynrrhhqvooyrhnfyhgeinvskbjkvhmjjwlubpcrirzmfkqwxwcsqerwnptzmkgwxiykcbhshawqwkictjwfbxwpjzlqyibmqigoizcaaawspvrkrnkvkeagrkdmthcewyxfzwjyhtlgyaevdzwrwvorycxbartgjahwbmcubctmtzjechvwegpmkoiqfovebfzloxqrlnpjouiycpziafhlvmscjflnhkauivnlosrjwqpyudvtcpjkocjfhwcpnmbupydpbghwseecrzgnvyijpsyudpnkywrbqixzkzuabveaznbiensnfpjlfwnfoobifkmxugbdrbkqwwmclgyweefialhzetocrnsrbdmrqupfwjjqtowgohhcdpijjmmopbpvzuywcuieelrttieuglxfyqvrcrneabifubjkwezarnoxooanvjdtvtzmjcusmpjmiqfpkmzacdcacnvqbaoetxypyfnyixkfjfvzajwxqslzhuppfjnulzlzyerticwbybzlqtorrbokojupvqraijjzgvhjwrsaqoasypruswrrvvllfrwzgdriduuhsoglwkbalyngssdgtcjzcntrfvkuomcptvgxxgyhnztcpmsuentdcgobnpjcobuhdkshvvvyyqtqaxvdhtwmcayivwwzlrtgctgkmnjzzgugegfdkmmkywpskytxuxmljoimepzdzvmehdjujazmswmhfupidrusmpvessixfeowhorjpwkbrygepiaelgcbnykcasxakampqfegyclzbxdggpsgbvsgdzutnquylgucnzqfafavobenpojpnzrrnhnlgjjciqzlctyiqgsvkghtrrqcletpxzvonhhtgqgonuxqdjbtzprclvofaznocaxaixosjbqjwmztbxqactluvekbxrdzqaehouarimpxuxkejovwbfyqyhdblyaknerjfgchmozhvwdnllrazqnnxnosxempabxrjvrjxccdsqitqyqvopetmlvadohsgeyzxjqyunpmigiqyisqwvauyndbliiogqtylbobmunnpelsuroopwgsufxnotzhnrymjjgpgjcfujqpkuhvlikhjtrjqvgaywxekrkarjzwhgoeuvnhcfnkcwudanravxvzivsoghamildvkhsthcaalngquhgdstlhdfhnrrmifaanhpjbkxhnzcpsefikqibkmprlihdsvxyumgrijqpgyexsxyvtkipiukksjivhrpzrucenfskjrgobctbzqgpjhlftjqhjagritbrbxozzocvikkgpnygnkobuadsshkmzhrmynjqmzicnvugjphsjznmpumdunaiztjfglqqgyhxxerxorsjvulgqdsttznqbyudxpgfxjebflicuwhnbtllvmilfvpotkkmlrbzbwkndcloszokuxydovexbdhseeavariowjgpbzntndqqonxnjbtkokmyrgmivfyimjqelakkdozohowxpshutarlkevvexkmvrhfurbbilfcyzoqpugwiqvpkwnyoxqxssxlykwormbzfopyamjiutwzizmlaaipvmtldvzzpxkbchxnomzwaqwlaptvajqfwetxcboqytadljtfrhcmjarrjbfroduvgftcjeamdnhsdhfshkzbvvbznztjffooksiryixpexkgzwtdvmrzhtljaeaejetbrgjogirvxgectvgomhejmvbbdmvxnomkrwhsjrfmgnkfnrezciccogccfdlrkcvxjpvmpjmiycyuavhfzlpwbjjwmryruxlctacgkctxtbhyaewzuelaymyqujpeghlajqxqpoihaeygibiurvmsggkyhndvuubmmlhowppemyhstkopsildrgyioihwa" println(veryVeryLongString) } ```