You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "jpountz (via GitHub)" <gi...@apache.org> on 2024/09/04 14:44:08 UTC
[PR] Make Operations#repeat create simpler automata. [lucene]
jpountz opened a new pull request, #13714:
URL: https://github.com/apache/lucene/pull/13714
`Operations#repeat` currently creates an automaton that has one more final state, and 2x more transitions for each of the final states. With this change, the returned automaton has a single final state and only 2x more transitions for state 0.
Currently a draft as I'm still looking into whether this new logic is correct.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Make Operations#repeat create simpler automata. [lucene]
Posted by "rmuir (via GitHub)" <gi...@apache.org>.
rmuir commented on PR #13714:
URL: https://github.com/apache/lucene/pull/13714#issuecomment-2329385040
> Do we have good randomized testing of this method? Maybe we could add a random test that makes a random regexp, build the A from that (minimized or determinized or not or so), calls repeat, then goes back to the original regexp and compiles `(<original-regexp>)*` and asserts `sameLanguage`?
When optimizing a scary method, a previous approach we have taken is to take existing implementation unmodified, move it to `AutomatonTestUtil.foobarSimple()`, and then generate random automata and assert that optimized method and unoptimized method accept the same language.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Make Operations#repeat create simpler automata. [lucene]
Posted by "rmuir (via GitHub)" <gi...@apache.org>.
rmuir commented on PR #13714:
URL: https://github.com/apache/lucene/pull/13714#issuecomment-2331355806
thanks for adding comments to the new repeat code.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Make Operations#repeat create simpler automata. [lucene]
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz merged PR #13714:
URL: https://github.com/apache/lucene/pull/13714
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Make Operations#repeat create simpler automata. [lucene]
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #13714:
URL: https://github.com/apache/lucene/pull/13714#issuecomment-2329331978
I just pushed a commit that avoids creating dead states if the input automaton doesn't have dead states itself. So the automaton created by `.*` would now have a single state.
For context, I started looking into optimizing the single-transition case only (hence the branch name) but as I started looking deeper into it, it looked like improving the general case wouldn't be much harder, as the algorithm boils down to renumbering final states to 0 and other states to `state + 1`.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Make Operations#repeat create simpler automata. [lucene]
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #13714:
URL: https://github.com/apache/lucene/pull/13714#issuecomment-2329268077
A practical side-effect of this change is that `.*` now gets parsed to the below automaton:
while our main branch currently parses it to the below automaton:
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Make Operations#repeat create simpler automata. [lucene]
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #13714:
URL: https://github.com/apache/lucene/pull/13714#issuecomment-2329450444
Good ideas, I'll look into it.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Make Operations#repeat create simpler automata. [lucene]
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #13714:
URL: https://github.com/apache/lucene/pull/13714#issuecomment-2330771175
Thanks for the test idea, it found interesting test failures in the case when accept states had transitions, as these transitions would then become transitions on the initial state, which is not expected.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Make Operations#repeat create simpler automata. [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on code in PR #13714:
URL: https://github.com/apache/lucene/pull/13714#discussion_r1743958059
##########
lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java:
##########
@@ -182,26 +182,44 @@ public static Automaton repeat(Automaton a) {
// Repeating the empty automata will still only accept the empty automata.
return a;
}
+
+ if (a.isAccept(0) && a.getAcceptStates().nextSetBit(1) == -1) {
Review Comment:
I guess it is allowed to pass `1` to `nextSetBit` even if the `BitSet` is length 1? Javadoc seems to say it only throws `IndexOutOfBoundsException` if you pass a negative index, and the example `for` loop would do what you are doing here on a length 1 `BitSet` so I think it's OK.
##########
lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java:
##########
@@ -182,26 +182,44 @@ public static Automaton repeat(Automaton a) {
// Repeating the empty automata will still only accept the empty automata.
return a;
}
+
+ if (a.isAccept(0) && a.getAcceptStates().nextSetBit(1) == -1) {
+ // If the only accept state is 0, then this automaton already repeats itself. Automata
+ // returned by this function only accept state 0, so this makes this function idempotent.
+ return a;
Review Comment:
This is quite a cool observation (both sentences, separately)!
Maybe swap the words `only accept` to make it more accurate (`only` is referring to `state 0`, not really `accept`). Proper `only` placement is tricky!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Make Operations#repeat create simpler automata. [lucene]
Posted by "rmuir (via GitHub)" <gi...@apache.org>.
rmuir commented on PR #13714:
URL: https://github.com/apache/lucene/pull/13714#issuecomment-2329517580
Was thinking something similar to this test but for `repeat`: https://github.com/apache/lucene/blob/main/lucene/core/src/test/org/apache/lucene/util/automaton/TestMinimize.java#L39-L45
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org