[
https://issues.apache.org/jira/browse/FLINK-10470?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16633874#comment-16633874
]
ASF GitHub Bot commented on FLINK-10470:
----------------------------------------
pnowojski commented on a change in pull request #6781: [FLINK-10470] Add method
to check if pattern can produce empty matches
URL: https://github.com/apache/flink/pull/6781#discussion_r221577049
##########
File path:
flink-libraries/flink-cep/src/main/java/org/apache/flink/cep/nfa/compiler/NFACompiler.java
##########
@@ -74,6 +77,36 @@
}
}
+ /**
+ * Verifies if the provided pattern can possibly generate empty match.
Example of patterns that can possibly
+ * generate empty matches are: A*, A?, A* B? etc.
+ *
+ * @param pattern pattern to check
+ * @return true if empty match could potentially match the pattern,
false otherwise
+ */
+ public static boolean canProduceEmptyMatches(final Pattern<?, ?>
pattern) {
+ NFAFactoryCompiler<?> compiler = new
NFAFactoryCompiler<>(checkNotNull(pattern));
+ compiler.compileFactory();
+ State<?> startState =
compiler.getStates().stream().filter(State::isStart).findFirst().get();
+
+ final Stack<State<?>> statesToCheck = new Stack<>();
+ statesToCheck.push(startState);
+ while (!statesToCheck.isEmpty()) {
+ final State<?> currentState = statesToCheck.pop();
+ for (StateTransition<?> transition :
currentState.getStateTransitions()) {
+ if (transition.getAction() ==
StateTransitionAction.PROCEED) {
+ if
(transition.getTargetState().isFinal()) {
+ return true;
+ } else {
+
statesToCheck.push(transition.getTargetState());
Review comment:
Can we loop here forever if `PROCEED` takes us to already visited node?
Shouldn't we check for already visited states?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
> Add method to check if pattern can produce empty matches
> --------------------------------------------------------
>
> Key: FLINK-10470
> URL: https://issues.apache.org/jira/browse/FLINK-10470
> Project: Flink
> Issue Type: Sub-task
> Components: CEP
> Reporter: Dawid Wysakowicz
> Assignee: Dawid Wysakowicz
> Priority: Major
> Labels: pull-request-available
>
> There is couple of inconsistencies how CEP library handles greedy and
> reluctant operators at the beginning at end of pattern. This results in
> subtle problems how empty matches should be generated for patterns like e.g.
> A? or A*?, where one is greedy and the other one is reluctant. In order to
> provide first version of MATCH_RECOGNIZE function we should have a
> possibility to disable patterns which can produce empty matches.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
