lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Dawid Weiss (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (LUCENE-4111) More spinning/endless loop problems with random regex in org.apache.lucene.analysis.pattern.TestPatternReplaceCharFilter.testRandomStrings
Date Tue, 05 Jun 2012 20:08:23 GMT

    [ https://issues.apache.org/jira/browse/LUCENE-4111?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13289676#comment-13289676
] 

Dawid Weiss commented on LUCENE-4111:
-------------------------------------

It isn't broken, these patterns will send any backtracking regexp implementation into (nearly
endless) recursion. Russ Cox has a nice article about this here:

http://swtch.com/~rsc/regexp/regexp1.html

A super-cool task (for a SoC student?) would be to port re2 library to Java:
http://code.google.com/p/re2/

I don't think there is any alternative implementation in Java that is not backtracking-based
and at the same time common feature-complete (the one in brics is simplistic).
                
> More spinning/endless loop problems with random regex in org.apache.lucene.analysis.pattern.TestPatternReplaceCharFilter.testRandomStrings
> ------------------------------------------------------------------------------------------------------------------------------------------
>
>                 Key: LUCENE-4111
>                 URL: https://issues.apache.org/jira/browse/LUCENE-4111
>             Project: Lucene - Java
>          Issue Type: Bug
>          Components: modules/analysis
>    Affects Versions: 4.0
>            Reporter: Uwe Schindler
>            Assignee: Dawid Weiss
>
> The Linux Jenkins server (and also the windows one while I was on vacation) were hanging
almost infinite:
> Stack trace (including seeks):
> {noformat}
> Full thread dump Java HotSpot(TM) 64-Bit Server VM (20.7-b02 mixed mode):
> "TEST-TestScope-org.apache.lucene.analysis.pattern.TestPatternReplaceCharFilter.testRandomStrings-seed#[A1E6315575F637C6]"
prio=6 ti
> d=0x0000000006cda000 nid=0x1e34 runnable [0x0000000006bab000]
>    java.lang.Thread.State: RUNNABLE
>         at java.util.regex.Pattern$Branch.match(Pattern.java:4114)
>         at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
>         at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4357)
>         at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
>         at java.util.regex.Pattern$BranchConn.match(Pattern.java:4078)
>         at java.util.regex.Pattern$CharProperty.match(Pattern.java:3345)
>         at java.util.regex.Pattern$Branch.match(Pattern.java:4114)
>         at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
>         at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4357)
>         at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
>         at java.util.regex.Pattern$BranchConn.match(Pattern.java:4078)
>         at java.util.regex.Pattern$CharProperty.match(Pattern.java:3345)
>         at java.util.regex.Pattern$Branch.match(Pattern.java:4114)
>         at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
>         at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4357)
>         at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
>         at java.util.regex.Pattern$BranchConn.match(Pattern.java:4078)
>         at java.util.regex.Pattern$Curly.match0(Pattern.java:3789)
>         at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
>         at java.util.regex.Pattern$Ques.match(Pattern.java:3691)
>         at java.util.regex.Pattern$Branch.match(Pattern.java:4114)
>         at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
>         at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4357)
>         at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
>         at java.util.regex.Pattern$BranchConn.match(Pattern.java:4078)
>         at java.util.regex.Pattern$CharProperty.match(Pattern.java:3345)
>         at java.util.regex.Pattern$Branch.match(Pattern.java:4114)
>         at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
>         at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4357)
>         at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
>         at java.util.regex.Pattern$BranchConn.match(Pattern.java:4078)
>         at java.util.regex.Pattern$CharProperty.match(Pattern.java:3345)
>         at java.util.regex.Pattern$Branch.match(Pattern.java:4114)
>         at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
>         at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4357)
>         at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
>         at java.util.regex.Pattern$BranchConn.match(Pattern.java:4078)
>         at java.util.regex.Pattern$Curly.match0(Pattern.java:3789)
>         at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
>         at java.util.regex.Pattern$Ques.match(Pattern.java:3691)
>         at java.util.regex.Pattern$Branch.match(Pattern.java:4114)
>         at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
>         at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4357)
>         at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
>         at java.util.regex.Pattern$BranchConn.match(Pattern.java:4078)
>         at java.util.regex.Pattern$CharProperty.match(Pattern.java:3345)
>         at java.util.regex.Pattern$Branch.match(Pattern.java:4114)
>         at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
>         at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4357)
>         at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
>         at java.util.regex.Pattern$BranchConn.match(Pattern.java:4078)
>         at java.util.regex.Pattern$CharProperty.match(Pattern.java:3345)
>         at java.util.regex.Pattern$Branch.match(Pattern.java:4114)
>         at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
>         at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4357)
>         at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
>         at java.util.regex.Pattern$BranchConn.match(Pattern.java:4078)
>         at java.util.regex.Pattern$Curly.match0(Pattern.java:3789)
>         at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
>         at java.util.regex.Pattern$Ques.match(Pattern.java:3691)
>         at java.util.regex.Pattern$Branch.match(Pattern.java:4114)
>         at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
>         at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4357)
>         at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
>         at java.util.regex.Pattern$BranchConn.match(Pattern.java:4078)
>         at java.util.regex.Pattern$Curly.match0(Pattern.java:3789)
>         at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
>         at java.util.regex.Pattern$Ques.match(Pattern.java:3691)
>         at java.util.regex.Pattern$Branch.match(Pattern.java:4114)
>         at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
>         at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4357)
>         at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
>         at java.util.regex.Pattern$BranchConn.match(Pattern.java:4078)
>         at java.util.regex.Pattern$Curly.match0(Pattern.java:3789)
>         at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
>         at java.util.regex.Pattern$Ques.match(Pattern.java:3691)
>         at java.util.regex.Pattern$Branch.match(Pattern.java:4114)
>         at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
>         at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4357)
>         at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
>         at java.util.regex.Pattern$BranchConn.match(Pattern.java:4078)
>         at java.util.regex.Pattern$Curly.match0(Pattern.java:3789)
>         at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
>         at java.util.regex.Pattern$Ques.match(Pattern.java:3691)
>         at java.util.regex.Pattern$Branch.match(Pattern.java:4114)
>         at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
>         at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4357)
>         at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
>         at java.util.regex.Pattern$BranchConn.match(Pattern.java:4078)
>         at java.util.regex.Pattern$Curly.match0(Pattern.java:3789)
>         at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
>         at java.util.regex.Pattern$Ques.match(Pattern.java:3691)
>         at java.util.regex.Pattern$Branch.match(Pattern.java:4114)
>         at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
>         at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4357)
>         at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
>         at java.util.regex.Pattern$BranchConn.match(Pattern.java:4078)
>         at java.util.regex.Pattern$Curly.match0(Pattern.java:3789)
>         at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
>         at java.util.regex.Pattern$Ques.match(Pattern.java:3691)
>         at java.util.regex.Pattern$Branch.match(Pattern.java:4114)
>         at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
>         at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4357)
>         at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
>         at java.util.regex.Pattern$BranchConn.match(Pattern.java:4078)
>         at java.util.regex.Pattern$Curly.match0(Pattern.java:3789)
>         at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
>         at java.util.regex.Pattern$Ques.match(Pattern.java:3691)
>         at java.util.regex.Pattern$Branch.match(Pattern.java:4114)
>         at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
>         at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4357)
>         at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
>         at java.util.regex.Pattern$BranchConn.match(Pattern.java:4078)
>         at java.util.regex.Pattern$Curly.match0(Pattern.java:3789)
>         at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
>         at java.util.regex.Pattern$Ques.match(Pattern.java:3691)
>         at java.util.regex.Pattern$Branch.match(Pattern.java:4114)
>         at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
>         at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4357)
>         at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
>         at java.util.regex.Pattern$BranchConn.match(Pattern.java:4078)
>         at java.util.regex.Pattern$CharProperty.match(Pattern.java:3345)
>         at java.util.regex.Pattern$Branch.match(Pattern.java:4114)
>         at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
>         at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4357)
>         at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
>         at java.util.regex.Pattern$BranchConn.match(Pattern.java:4078)
>         at java.util.regex.Pattern$CharProperty.match(Pattern.java:3345)
>         at java.util.regex.Pattern$Branch.match(Pattern.java:4114)
>         at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
>         at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4357)
>         at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
>         at java.util.regex.Pattern$BranchConn.match(Pattern.java:4078)
>         at java.util.regex.Pattern$CharProperty.match(Pattern.java:3345)
>         at java.util.regex.Pattern$Branch.match(Pattern.java:4114)
>         at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
>         at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4357)
>         at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
>         at java.util.regex.Pattern$BranchConn.match(Pattern.java:4078)
>         at java.util.regex.Pattern$Curly.match0(Pattern.java:3789)
>         at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
>         at java.util.regex.Pattern$Ques.match(Pattern.java:3691)
>         at java.util.regex.Pattern$Branch.match(Pattern.java:4114)
>         at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
>         at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4357)
>         at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
>         at java.util.regex.Pattern$BranchConn.match(Pattern.java:4078)
>         at java.util.regex.Pattern$CharProperty.match(Pattern.java:3345)
>         at java.util.regex.Pattern$Branch.match(Pattern.java:4114)
>         at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
>         at java.util.regex.Pattern$LazyLoop.matchInit(Pattern.java:4378)
>         at java.util.regex.Pattern$Prolog.match(Pattern.java:4251)
>         at java.util.regex.Pattern$Start.match(Pattern.java:3055)
>         at java.util.regex.Matcher.search(Matcher.java:1105)
>         at java.util.regex.Matcher.find(Matcher.java:535)
>         at org.apache.lucene.analysis.pattern.PatternReplaceCharFilter.processPattern(PatternReplaceCharFilter.java:92)
>         at org.apache.lucene.analysis.pattern.PatternReplaceCharFilter.read(PatternReplaceCharFilter.java:72)
>         at java.io.Reader.read(Reader.java:104)
>         at org.apache.lucene.analysis.MockTokenizer.readCodePoint(MockTokenizer.java:142)
>         at org.apache.lucene.analysis.MockTokenizer.incrementToken(MockTokenizer.java:109)
>         at org.apache.lucene.analysis.BaseTokenStreamTestCase.checkAnalysisConsistency(BaseTokenStreamTestCase.java:558)
>         at org.apache.lucene.analysis.BaseTokenStreamTestCase.checkRandomData(BaseTokenStreamTestCase.java:488)
>         at org.apache.lucene.analysis.BaseTokenStreamTestCase.checkRandomData(BaseTokenStreamTestCase.java:430)
>         at org.apache.lucene.analysis.BaseTokenStreamTestCase.checkRandomData(BaseTokenStreamTestCase.java:424)
>         at org.apache.lucene.analysis.pattern.TestPatternReplaceCharFilter.testRandomStrings(TestPatternReplaceCharFilter.java:322)
>         at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
>         at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
>         at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
>         at java.lang.reflect.Method.invoke(Method.java:597)
>         at com.carrotsearch.randomizedtesting.RandomizedRunner.invoke(RandomizedRunner.java:1969)
>         at com.carrotsearch.randomizedtesting.RandomizedRunner.access$1100(RandomizedRunner.java:132)
>         at com.carrotsearch.randomizedtesting.RandomizedRunner$6.evaluate(RandomizedRunner.java:814)
>         at com.carrotsearch.randomizedtesting.RandomizedRunner$7.evaluate(RandomizedRunner.java:875)
>         at com.carrotsearch.randomizedtesting.RandomizedRunner$8.evaluate(RandomizedRunner.java:889)
>         at org.apache.lucene.util.TestRuleSetupTeardownChained$1.evaluate(TestRuleSetupTeardownChained.java:50)
>         at org.apache.lucene.util.TestRuleFieldCacheSanity$1.evaluate(TestRuleFieldCacheSanity.java:32)
>         at org.apache.lucene.util.AbstractBeforeAfterRule$1.evaluate(AbstractBeforeAfterRule.java:45)
>         at com.carrotsearch.randomizedtesting.rules.SystemPropertiesInvariantRule$1.evaluate(SystemPropertiesInvariantRule.java:55)
>         at org.apache.lucene.util.TestRuleReportUncaughtExceptions$1.evaluate(TestRuleReportUncaughtExceptions.java:68)
>         at org.apache.lucene.util.TestRuleThreadAndTestName$1.evaluate(TestRuleThreadAndTestName.java:48)
>         at org.apache.lucene.util.TestRuleMarkFailure$1.evaluate(TestRuleMarkFailure.java:48)
>         at com.carrotsearch.randomizedtesting.RandomizedRunner.runSingleTest(RandomizedRunner.java:821)
>         at com.carrotsearch.randomizedtesting.RandomizedRunner.access$700(RandomizedRunner.java:132)
>         at com.carrotsearch.randomizedtesting.RandomizedRunner$3$1.run(RandomizedRunner.java:669)
>         at com.carrotsearch.randomizedtesting.RandomizedRunner$3.evaluate(RandomizedRunner.java:695)
>         at com.carrotsearch.randomizedtesting.RandomizedRunner$4.evaluate(RandomizedRunner.java:734)
>         at com.carrotsearch.randomizedtesting.RandomizedRunner$5.evaluate(RandomizedRunner.java:745)
>         at org.apache.lucene.util.AbstractBeforeAfterRule$1.evaluate(AbstractBeforeAfterRule.java:45)
>         at org.apache.lucene.util.TestRuleReportUncaughtExceptions$1.evaluate(TestRuleReportUncaughtExceptions.java:68)
>         at org.apache.lucene.util.TestRuleStoreClassName$1.evaluate(TestRuleStoreClassName.java:38)
>         at org.apache.lucene.util.TestRuleIcuHack$1.evaluate(TestRuleIcuHack.java:51)
>         at com.carrotsearch.randomizedtesting.rules.SystemPropertiesInvariantRule$1.evaluate(SystemPropertiesInvariantRule.java:55)
>         at org.apache.lucene.util.TestRuleNoInstanceHooksOverrides$1.evaluate(TestRuleNoInstanceHooksOverrides.java:53)
>         at org.apache.lucene.util.TestRuleNoStaticHooksShadowing$1.evaluate(TestRuleNoStaticHooksShadowing.java:52)
>         at org.apache.lucene.util.TestRuleAssertionsRequired$1.evaluate(TestRuleAssertionsRequired.java:36)
>         at org.apache.lucene.util.TestRuleMarkFailure$1.evaluate(TestRuleMarkFailure.java:48)
>         at org.apache.lucene.util.TestRuleIgnoreTestSuites$1.evaluate(TestRuleIgnoreTestSuites.java:56)
>         at com.carrotsearch.randomizedtesting.RandomizedRunner.runSuite(RandomizedRunner.java:605)
>         at com.carrotsearch.randomizedtesting.RandomizedRunner.access$400(RandomizedRunner.java:132)
>         at com.carrotsearch.randomizedtesting.RandomizedRunner$2.run(RandomizedRunner.java:551)
> {noformat}

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

        

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org


Mime
View raw message