Resolve the epsilon transitions for each state upfront instead of dynamically
authorbenjamin@webkit.org <benjamin@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 20 Jan 2015 20:43:33 +0000 (20:43 +0000)
committerbenjamin@webkit.org <benjamin@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 20 Jan 2015 20:43:33 +0000 (20:43 +0000)
commitee998111875ca1352f2c87fd6e857a7a3a987fcf
tree4948e610e4fa1a7bebe17aac78362acd260f0f4b
parent9d439a53cd01f9a4171ea86e32ca12f7eb6bfd21
Resolve the epsilon transitions for each state upfront instead of dynamically
https://bugs.webkit.org/show_bug.cgi?id=140654

Reviewed by Andreas Kling.

Instead of recomputing the epsilon-closure for each set, we compute the closure
of every element at the beginning of the transformation.

We then remove the epsilon transitions from the NFA to simplify populateTransitions().
The epsilon transitions are still there, but they are now in a separate graph we use
in parallel.

* contentextensions/NFAToDFA.cpp:
(WebCore::ContentExtensions::epsilonClosureExcludingSelf):
(WebCore::ContentExtensions::resolveEpsilonClosures):
(WebCore::ContentExtensions::extendSetWithClosure):
(WebCore::ContentExtensions::populateTransitions):
(WebCore::ContentExtensions::NFAToDFA::convert):
(WebCore::ContentExtensions::epsilonClosure): Deleted.
(WebCore::ContentExtensions::populateTransitionsExcludingEpsilon): Deleted.
* contentextensions/NFAToDFA.h:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@178739 268f45cc-cd09-0410-ab3c-d52691b4dbfc
Source/WebCore/ChangeLog
Source/WebCore/contentextensions/NFAToDFA.cpp
Source/WebCore/contentextensions/NFAToDFA.h