applied patch from Youri Golovanov fixing bug #316338 and adding a couple
* xmlregexp.c: applied patch from Youri Golovanov fixing bug
#316338 and adding a couple of optimizations in the regexp
compilation engine.
* test/regexp/bug316338 result/regexp/bug316338: added regression
tests based on the examples provided in the bug report.
Daniel
diff --git a/xmlregexp.c b/xmlregexp.c
index 8d7ee97..58f480d 100644
--- a/xmlregexp.c
+++ b/xmlregexp.c
@@ -1479,7 +1479,13 @@
switch (atom->quant) {
case XML_REGEXP_QUANT_OPT:
atom->quant = XML_REGEXP_QUANT_ONCE;
- xmlFAGenerateEpsilonTransition(ctxt, atom->start, atom->stop);
+ /*
+ * transition done to the state after end of atom.
+ * 1. set transition from atom start to new state
+ * 2. set transition from atom end to this state.
+ */
+ xmlFAGenerateEpsilonTransition(ctxt, atom->start, 0);
+ xmlFAGenerateEpsilonTransition(ctxt, atom->stop, ctxt->state);
break;
case XML_REGEXP_QUANT_MULT:
atom->quant = XML_REGEXP_QUANT_ONCE;
@@ -1522,8 +1528,6 @@
atom->min = 0;
atom->max = 0;
atom->quant = XML_REGEXP_QUANT_ONCE;
- xmlFAGenerateCountedEpsilonTransition(ctxt, atom->stop,
- atom->start, counter);
if (to != NULL) {
newstate = to;
} else {
@@ -1533,6 +1537,13 @@
ctxt->state = newstate;
xmlFAGenerateCountedTransition(ctxt, atom->stop,
newstate, counter);
+
+ /*
+ * first check count and if OK jump forward;
+ * if checking fail increment count and jump back
+ */
+ xmlFAGenerateCountedEpsilonTransition(ctxt, atom->stop,
+ atom->start, counter);
}
default:
break;
@@ -4299,6 +4310,15 @@
if (exec->state->nbTrans > exec->transno + 1) {
xmlFARegExecSave(exec);
}
+ /*
+ * restart count for expressions like this ((abc){2})*
+ */
+ if (trans->count >= 0) {
+#ifdef DEBUG_REGEXP_EXEC
+ printf("Reset count %d\n", trans->count);
+#endif
+ exec->counts[trans->count] = 0;
+ }
if (trans->counter >= 0) {
#ifdef DEBUG_REGEXP_EXEC
printf("Increasing count %d\n", trans->counter);
@@ -5112,19 +5132,23 @@
/**
* xmlFAParseBranch:
* @ctxt: a regexp parser context
+ * @to: optional target to the end of the branch
+ *
+ * @to is used to optimize by removing duplicate path in automata
+ * in expressions like (a|b)(c|d)
*
* [2] branch ::= piece*
- 8
*/
static int
-xmlFAParseBranch(xmlRegParserCtxtPtr ctxt) {
+xmlFAParseBranch(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr to) {
xmlRegStatePtr previous;
int ret;
previous = ctxt->state;
ret = xmlFAParsePiece(ctxt);
if (ret != 0) {
- if (xmlFAGenerateTransitions(ctxt, previous, NULL, ctxt->atom) < 0)
+ if (xmlFAGenerateTransitions(ctxt, previous,
+ (CUR=='|' || CUR==')') ? to : NULL, ctxt->atom) < 0)
return(-1);
previous = ctxt->state;
ctxt->atom = NULL;
@@ -5132,8 +5156,8 @@
while ((ret != 0) && (ctxt->error == 0)) {
ret = xmlFAParsePiece(ctxt);
if (ret != 0) {
- if (xmlFAGenerateTransitions(ctxt, previous, NULL,
- ctxt->atom) < 0)
+ if (xmlFAGenerateTransitions(ctxt, previous,
+ (CUR=='|' || CUR==')') ? to : NULL, ctxt->atom) < 0)
return(-1);
previous = ctxt->state;
ctxt->atom = NULL;
@@ -5156,7 +5180,7 @@
/* if not top start should have been generated by an epsilon trans */
start = ctxt->state;
ctxt->end = NULL;
- xmlFAParseBranch(ctxt);
+ xmlFAParseBranch(ctxt, NULL);
if (top) {
#ifdef DEBUG_REGEXP_GRAPH
printf("State %d is final\n", ctxt->state->no);
@@ -5172,15 +5196,7 @@
NEXT;
ctxt->state = start;
ctxt->end = NULL;
- xmlFAParseBranch(ctxt);
- if (top) {
- ctxt->state->type = XML_REGEXP_FINAL_STATE;
-#ifdef DEBUG_REGEXP_GRAPH
- printf("State %d is final\n", ctxt->state->no);
-#endif
- } else {
- xmlFAGenerateEpsilonTransition(ctxt, ctxt->state, end);
- }
+ xmlFAParseBranch(ctxt, end);
}
if (!top) {
ctxt->state = end;