Draft: Fix graph regex unique
Context
This merge request is a correction indirectly related to issue #91 (closed). It has become apparent that the definition of the unique node was incorrect because it should have one parent and one child.
The problem identified in the issue is due to :
- 'A*' Query given the folowing FSM:
graph LR;
classDef ref fill:#f96
classDef start fill:#096
s1(("q0")):::start
q10(("q1")):::ref
s1 --"is(A)"-->q10
s1 --"E" --> q10
q10 --"E" --> s1
where E are empty edge, (transition whith out test).
- The use of rejected nodes.
Originally, rejected nodes are used to verify that we are matching all possible traversable structures with the corresponding FSMs of the query. The basic principle is that when a traversal context encounters a common or unique node that does not validate, it is recorded in a common variable. To ensure that the regex match does not correspond to a sub-structure of a larger structure, all rejected nodes must be validated by at least one FSM from a query.
- the probleme
graph LR;
s1(("A"))
q10(("B"))
s1 -->q10
The problem is that for this example graph, starting from node A, the preceding FSM will validate node A and arrive in state Q1 on node B. In theory, the match is finished, but because there is transition E, we return to Q0 on node B. We attempt to make the unique transition, and node B is added to the rejected nodes. Since it's impossible to validate B, the match has no solution. Therefore, there is an issue with the definition of rejected nodes.
Modified files
-
FsmEdge.cpp
correction of the unique node , correction of the definition of rejected nodes -
RemoveFlatten.cpp
FuseMulAdd.cpp
Test_examples.cpp
correctif due to the fix of unique node to add the Producer W,B in the query -
FsmRunTimeContext.hpp
, add a static clear to the rejected node to optimise the memory use
Detailed major modifications
The two main modifications are:
- The correction of the unique edge to verify if there are no multiple parents and to impose a clear definition of the producer.
- The correction of the definition of unique nodes necessitates manually defining the end of sequence.
TODO
-
Fix unique edge -
Fix rejected nodes -
Add $ end sequence