Fix exponential runtime in xmlFARecurseDeterminism
In order to prevent visiting a state twice, states must be marked as
visited for the whole duration of graph traversal because states might
be reached by different paths. Otherwise state graphs like the
following can lead to exponential runtime:
->O-->O-->O-->O-->O->
\ / \ / \ / \ /
O O O O
Reset the "visited" flag only after the graph was traversed.
xmlFAComputesDeterminism still has massive performance problems when
handling fuzzed input. By design, it has quadratic time complexity in
the number of reachable states. Some issues might also stem from
redundant epsilon transitions. With this fix, fuzzing regexes with a
maximum length of 100 becomes feasible at least.
Found with libFuzzer.
1 file changed
