[RFC/RFA] redesign construction of the automaton for a regex

[Paolo Bonzini]

This is a very big patch that redesigns regcomp.c's automaton creation. 
  The patch makes the parse tree a substantially autonomous entity, and 
delays the creation of the automaton until after the parsing is complete.

I was careful to limit recursion, since the parse tree is completely 
unbalanced.  It could be possible to balance trees because CONCAT and 
OP_ALT are associative.  However, the parse tree has parent pointers so 
recursion on CONCAT nodes can be completely removed from regcomp.c.  My 
regcomp.c includes two generic preorder and postorder visitors and uses 
them to perform the various phases of building the automaton.  I also 
rewrote duplicate_tree to avoid recursion, since using the generic 
visitors was unnecessarily complicated in that case.

As an example of the cleanups that are enabled by this representation, 
Jakub's subexpression elimination optimization can be done in 20 lines 
of code using the visitors and the new parse tree design.  Now, 
subexpressions are represented as a single SUBEXP node in the parse 
tree, and are lowered later to concatenations with OP_OPEN_SUBEXP and 
OP_CLOSE_SUBEXP.

More efficient construction of the NFA automaton is also possible.  An 
example of a pass that can be implemented (I did not do this yet) is 
"star-normal form", eliminating cycles made entirely of epsilon 
transitions which are handled specially in regexec.c.

While I was working on automaton construction, I removed OP_DUP_QUESTION 
from trees and automata, since "A?" and "A|" are actually the same 
regular expression and they were being treated equivalently by regcomp.c.

This patch relies on the "speed up OP_PERIOD patch", because it included 
a cleanup that is very useful now (avoiding to muck with already created 
DFA nodes).  I can backport that part, but would of course prefer that 
that patch be included in the master version.

This patch is pretty hard to split, also because it has a lot of code 
that is written from scratch.  I've tested it on powerpc-linux 
(glibc+sed testsuites) and powerpc-darwin (sed only).  I can test it on 
i686-linux and sparc-solaris if you want.

Please comment on the possibility that this patch is applied, as the 
possibility of contributing to glibc some of my (paid) work on regex 
depends on this.

Regards,

Paolo

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: 12-separate-parsing.patch
URL: <http://sourceware.org/pipermail/libc-alpha/attachments/20041213/5440ec70/attachment.ksh>