* [PATCH 1/2] dfa: use backward set in removal of epsilon closure
@ 2020-09-13 1:54 Paul Eggert
2020-09-13 1:54 ` [PATCH 2/2] dfa: epsilon-closure tweaks (Bug#40634) Paul Eggert
0 siblings, 1 reply; 2+ messages in thread
From: Paul Eggert @ 2020-09-13 1:54 UTC (permalink / raw)
To: bug-gnulib; +Cc: Norihiro Tanaka
From: Norihiro Tanaka <noritnk@kcn.ne.jp>
When removing in epsilon closure, the code searched all nodes
sequentially, and this was slow for some cases. Build a backward
set before search, and only check previous position with the set.
Problem reported in <https://bugs.gnu.org/40634>.
* lib/dfa.c (struct dfa): New member 'epsilon'.
(addtok_mb): Check whether a pattern has epsilon node or not.
(epsclosure): New arg BACKWORD; caller changed. When removing
epsilon node and reconnecting, check only previous positions.
Treat BEG as if it were character.
(dfaanalyze): Build backward set.
---
lib/dfa.c | 65 +++++++++++++++++++++++++++++++++++++++++++------------
1 file changed, 51 insertions(+), 14 deletions(-)
diff --git a/lib/dfa.c b/lib/dfa.c
index 1f0587a7a..7c8eb6685 100644
--- a/lib/dfa.c
+++ b/lib/dfa.c
@@ -488,6 +488,7 @@ struct dfa
bool fast; /* The DFA is fast. */
token utf8_anychar_classes[9]; /* To lower ANYCHAR in UTF-8 locales. */
mbstate_t mbs; /* Multibyte conversion state. */
+ bool epsilon;
/* The following are valid only if MB_CUR_MAX > 1. */
@@ -1615,13 +1616,21 @@ addtok_mb (struct dfa *dfa, token t, char mbprop)
dfa->parse.depth--;
break;
- case BACKREF:
- dfa->fast = false;
+ case BEGLINE:
+ case ENDLINE:
+ case BEGWORD:
+ case ENDWORD:
+ case LIMWORD:
+ case NOTLIMWORD:
+ case EMPTY:
+ dfa->epsilon = true;
FALLTHROUGH;
+
default:
- dfa->nleaves++;
- FALLTHROUGH;
- case EMPTY:
+ if (t == BACKREF)
+ dfa->fast = false;
+ if (t != EMPTY)
+ dfa->nleaves++;
dfa->parse.depth++;
break;
}
@@ -2297,14 +2306,15 @@ state_index (struct dfa *d, position_set const *s, int context)
constraint. Repeat exhaustively until no funny positions are left.
S->elems must be large enough to hold the result. */
static void
-epsclosure (struct dfa const *d)
+epsclosure (struct dfa const *d, position_set *backword)
{
position_set tmp;
alloc_position_set (&tmp, d->nleaves);
for (idx_t i = 0; i < d->tindex; i++)
if (d->follows[i].nelem > 0 && d->tokens[i] >= NOTCHAR
&& d->tokens[i] != BACKREF && d->tokens[i] != ANYCHAR
- && d->tokens[i] != MBCSET && d->tokens[i] < CSET)
+ && d->tokens[i] != MBCSET && d->tokens[i] < CSET
+ && d->tokens[i] != BEG)
{
unsigned int constraint;
switch (d->tokens[i])
@@ -2327,16 +2337,21 @@ epsclosure (struct dfa const *d)
case NOTLIMWORD:
constraint = NOTLIMWORD_CONSTRAINT;
break;
- default:
+ case EMPTY:
constraint = NO_CONSTRAINT;
break;
+ default:
+ abort ();
}
delete (i, &d->follows[i]);
- for (idx_t j = 0; j < d->tindex; j++)
- if (i != j && d->follows[j].nelem > 0)
- replace (&d->follows[j], i, &d->follows[i], constraint, &tmp);
+ for (idx_t j = 0; j < backword[i].nelem; j++)
+ replace (&d->follows[backword[i].elems[j].index], i, &d->follows[i],
+ constraint, &tmp);
+ for (idx_t j = 0; j < d->follows[i].nelem; j++)
+ replace (&backword[d->follows[i].elems[j].index], i, &backword[i],
+ NO_CONSTRAINT, &tmp);
}
free (tmp.elems);
}
@@ -2643,6 +2658,7 @@ dfaanalyze (struct dfa *d, bool searchflag)
/* Firstpos and lastpos elements. */
position *firstpos = posalloc;
position *lastpos = firstpos + d->nleaves;
+ position_set *backword = NULL;
position pos;
position_set tmp;
@@ -2675,6 +2691,9 @@ dfaanalyze (struct dfa *d, bool searchflag)
alloc_position_set (&merged, d->nleaves);
d->follows = xcalloc (d->tindex, sizeof *d->follows);
+ if (d->epsilon)
+ backword = xcalloc (d->tindex, sizeof *backword);
+
for (idx_t i = 0; i < d->tindex; i++)
{
switch (d->tokens[i])
@@ -2712,6 +2731,17 @@ dfaanalyze (struct dfa *d, bool searchflag)
case CAT:
/* Every element in the firstpos of the second argument is in the
follow of every element in the lastpos of the first argument. */
+ if (d->epsilon)
+ {
+ tmp.nelem = stk[-2].nlastpos;
+ tmp.elems = lastpos - stk[-1].nlastpos - stk[-2].nlastpos;
+ position *p = firstpos - stk[-1].nfirstpos;
+ for (idx_t j = 0; j < stk[-1].nfirstpos; j++)
+ {
+ merge (&tmp, &backword[p[j].index], &merged);
+ copy (&merged, &backword[p[j].index]);
+ }
+ }
{
tmp.nelem = stk[-1].nfirstpos;
tmp.elems = firstpos - stk[-1].nfirstpos;
@@ -2801,9 +2831,15 @@ dfaanalyze (struct dfa *d, bool searchflag)
#endif
}
- /* For each follow set that is the follow set of a real position, replace
- it with its epsilon closure. */
- epsclosure (d);
+ if (d->epsilon)
+ {
+ /* For each follow set that is the follow set of a real position,
+ replace it with its epsilon closure. */
+ epsclosure (d, backword);
+
+ for (idx_t i = 0; i < d->tindex; i++)
+ free (backword[i].elems);
+ }
dfaoptimize (d);
@@ -2865,6 +2901,7 @@ dfaanalyze (struct dfa *d, bool searchflag)
d->min_trcount++;
d->trcount = 0;
+ free (backword);
free (posalloc);
free (stkalloc);
free (merged.elems);
--
2.17.1
^ permalink raw reply related [flat|nested] 2+ messages in thread
* [PATCH 2/2] dfa: epsilon-closure tweaks (Bug#40634)
2020-09-13 1:54 [PATCH 1/2] dfa: use backward set in removal of epsilon closure Paul Eggert
@ 2020-09-13 1:54 ` Paul Eggert
0 siblings, 0 replies; 2+ messages in thread
From: Paul Eggert @ 2020-09-13 1:54 UTC (permalink / raw)
To: bug-gnulib; +Cc: Paul Eggert
Rename BACKWORD to BACKWARD consistently.
* lib/dfa.c (struct dfa): Reorder members to reduce fragmentation.
(addtok_mb): Redo slightly to make it act more like a state machine.
Check depth only when it increases.
(epsclosure): Let the switch test the tokens.
(dfaanalyze): Cache tindex. Simplify position loops.
Prefer xcalloc to xnmalloc + explicit zeroing. Free BACKWARD
only if it is not null, since we're testing that anyway.
(dfaanalyze, build_state): Use merge2 instead of doing it by hand.
---
ChangeLog | 27 ++++++++++++
lib/dfa.c | 124 ++++++++++++++++++++++++++----------------------------
2 files changed, 87 insertions(+), 64 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index bf39cc512..66aec61cb 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,30 @@
+2020-09-12 Paul Eggert <eggert@cs.ucla.edu>
+
+ dfa: epsilon-closure tweaks (Bug#40634)
+ Rename BACKWORD to BACKWARD consistently.
+ * lib/dfa.c (struct dfa): Reorder members to reduce fragmentation.
+ (addtok_mb): Redo slightly to make it act more like a state machine.
+ Check depth only when it increases.
+ (epsclosure): Let the switch test the tokens.
+ (dfaanalyze): Cache tindex. Simplify position loops.
+ Prefer xcalloc to xnmalloc + explicit zeroing. Free BACKWARD
+ only if it is not null, since we're testing that anyway.
+ (dfaanalyze, build_state): Use merge2 instead of doing it by hand.
+
+2020-09-12 Norihiro Tanaka <noritnk@kcn.ne.jp>
+
+ dfa: use backward set in removal of epsilon closure
+ When removing in epsilon closure, the code searched all nodes
+ sequentially, and this was slow for some cases. Build a backward
+ set before search, and only check previous position with the set.
+ Problem reported in <https://bugs.gnu.org/40634>.
+ * lib/dfa.c (struct dfa): New member 'epsilon'.
+ (addtok_mb): Check whether a pattern has epsilon node or not.
+ (epsclosure): New arg BACKWORD; caller changed. When removing
+ epsilon node and reconnecting, check only previous positions.
+ Treat BEG as if it were character.
+ (dfaanalyze): Build backward set.
+
2020-09-10 Paul Eggert <eggert@cs.ucla.edu>
canonicalize: fix pointer indexing bugs
diff --git a/lib/dfa.c b/lib/dfa.c
index 7c8eb6685..0f0764887 100644
--- a/lib/dfa.c
+++ b/lib/dfa.c
@@ -482,13 +482,14 @@ struct dfa
idx_t depth; /* Depth required of an evaluation stack
used for depth-first traversal of the
parse tree. */
- idx_t nleaves; /* Number of leaves on the parse tree. */
+ idx_t nleaves; /* Number of non-EMPTY leaves
+ in the parse tree. */
idx_t nregexps; /* Count of parallel regexps being built
with dfaparse. */
bool fast; /* The DFA is fast. */
+ bool epsilon; /* Does a token match only the empty string? */
token utf8_anychar_classes[9]; /* To lower ANYCHAR in UTF-8 locales. */
mbstate_t mbs; /* Multibyte conversion state. */
- bool epsilon;
/* The following are valid only if MB_CUR_MAX > 1. */
@@ -1616,26 +1617,31 @@ addtok_mb (struct dfa *dfa, token t, char mbprop)
dfa->parse.depth--;
break;
+ case EMPTY:
+ dfa->epsilon = true;
+ goto increment_depth;
+
+ case BACKREF:
+ dfa->fast = false;
+ goto increment_nleaves;
+
case BEGLINE:
case ENDLINE:
case BEGWORD:
case ENDWORD:
case LIMWORD:
case NOTLIMWORD:
- case EMPTY:
dfa->epsilon = true;
FALLTHROUGH;
-
default:
- if (t == BACKREF)
- dfa->fast = false;
- if (t != EMPTY)
- dfa->nleaves++;
+ increment_nleaves:
+ dfa->nleaves++;
+ increment_depth:
dfa->parse.depth++;
+ if (dfa->depth < dfa->parse.depth)
+ dfa->depth = dfa->parse.depth;
break;
}
- if (dfa->parse.depth > dfa->depth)
- dfa->depth = dfa->parse.depth;
}
static void addtok_wc (struct dfa *dfa, wint_t wc);
@@ -2156,6 +2162,8 @@ merge (position_set const *s1, position_set const *s2, position_set *m)
merge_constrained (s1, s2, -1, m);
}
+/* Merge into DST all the elements of SRC, possibly destroying
+ the contents of the temporary M. */
static void
merge2 (position_set *dst, position_set const *src, position_set *m)
{
@@ -2300,25 +2308,26 @@ state_index (struct dfa *d, position_set const *s, int context)
return i;
}
-/* Find the epsilon closure of a set of positions. If any position of the set
+/* Find the epsilon closure of D's set of positions. If any position of the set
contains a symbol that matches the empty string in some context, replace
that position with the elements of its follow labeled with an appropriate
constraint. Repeat exhaustively until no funny positions are left.
- S->elems must be large enough to hold the result. */
+ S->elems must be large enough to hold the result. BACKWARD is D's
+ backward set; use and update it too. */
static void
-epsclosure (struct dfa const *d, position_set *backword)
+epsclosure (struct dfa const *d, position_set *backward)
{
position_set tmp;
alloc_position_set (&tmp, d->nleaves);
for (idx_t i = 0; i < d->tindex; i++)
- if (d->follows[i].nelem > 0 && d->tokens[i] >= NOTCHAR
- && d->tokens[i] != BACKREF && d->tokens[i] != ANYCHAR
- && d->tokens[i] != MBCSET && d->tokens[i] < CSET
- && d->tokens[i] != BEG)
+ if (0 < d->follows[i].nelem)
{
unsigned int constraint;
switch (d->tokens[i])
{
+ default:
+ continue;
+
case BEGLINE:
constraint = BEGLINE_CONSTRAINT;
break;
@@ -2340,17 +2349,15 @@ epsclosure (struct dfa const *d, position_set *backword)
case EMPTY:
constraint = NO_CONSTRAINT;
break;
- default:
- abort ();
}
delete (i, &d->follows[i]);
- for (idx_t j = 0; j < backword[i].nelem; j++)
- replace (&d->follows[backword[i].elems[j].index], i, &d->follows[i],
+ for (idx_t j = 0; j < backward[i].nelem; j++)
+ replace (&d->follows[backward[i].elems[j].index], i, &d->follows[i],
constraint, &tmp);
for (idx_t j = 0; j < d->follows[i].nelem; j++)
- replace (&backword[d->follows[i].elems[j].index], i, &backword[i],
+ replace (&backward[d->follows[i].elems[j].index], i, &backward[i],
NO_CONSTRAINT, &tmp);
}
free (tmp.elems);
@@ -2658,7 +2665,6 @@ dfaanalyze (struct dfa *d, bool searchflag)
/* Firstpos and lastpos elements. */
position *firstpos = posalloc;
position *lastpos = firstpos + d->nleaves;
- position_set *backword = NULL;
position pos;
position_set tmp;
@@ -2676,10 +2682,11 @@ dfaanalyze (struct dfa *d, bool searchflag)
position_set merged; /* Result of merging sets. */
addtok (d, CAT);
+ idx_t tindex = d->tindex;
#ifdef DEBUG
fprintf (stderr, "dfaanalyze:\n");
- for (idx_t i = 0; i < d->tindex; i++)
+ for (idx_t i = 0; i < tindex; i++)
{
fprintf (stderr, " %td:", i);
prtok (d->tokens[i]);
@@ -2689,12 +2696,11 @@ dfaanalyze (struct dfa *d, bool searchflag)
d->searchflag = searchflag;
alloc_position_set (&merged, d->nleaves);
- d->follows = xcalloc (d->tindex, sizeof *d->follows);
-
- if (d->epsilon)
- backword = xcalloc (d->tindex, sizeof *backword);
+ d->follows = xcalloc (tindex, sizeof *d->follows);
+ position_set *backward
+ = d->epsilon ? xcalloc (tindex, sizeof *backward) : NULL;
- for (idx_t i = 0; i < d->tindex; i++)
+ for (idx_t i = 0; i < tindex; i++)
{
switch (d->tokens[i])
{
@@ -2714,12 +2720,8 @@ dfaanalyze (struct dfa *d, bool searchflag)
{
tmp.elems = firstpos - stk[-1].nfirstpos;
tmp.nelem = stk[-1].nfirstpos;
- position *p = lastpos - stk[-1].nlastpos;
- for (idx_t j = 0; j < stk[-1].nlastpos; j++)
- {
- merge (&tmp, &d->follows[p[j].index], &merged);
- copy (&merged, &d->follows[p[j].index]);
- }
+ for (position *p = lastpos - stk[-1].nlastpos; p < lastpos; p++)
+ merge2 (&d->follows[p->index], &tmp, &merged);
}
FALLTHROUGH;
case QMARK:
@@ -2729,28 +2731,27 @@ dfaanalyze (struct dfa *d, bool searchflag)
break;
case CAT:
- /* Every element in the firstpos of the second argument is in the
- follow of every element in the lastpos of the first argument. */
- if (d->epsilon)
+ /* Every element in the lastpos of the first argument is in
+ the backward set of every element in the firstpos of the
+ second argument. */
+ if (backward)
{
tmp.nelem = stk[-2].nlastpos;
tmp.elems = lastpos - stk[-1].nlastpos - stk[-2].nlastpos;
- position *p = firstpos - stk[-1].nfirstpos;
- for (idx_t j = 0; j < stk[-1].nfirstpos; j++)
- {
- merge (&tmp, &backword[p[j].index], &merged);
- copy (&merged, &backword[p[j].index]);
- }
+ for (position *p = firstpos - stk[-1].nfirstpos;
+ p < firstpos; p++)
+ merge2 (&backward[p->index], &tmp, &merged);
}
+
+ /* Every element in the firstpos of the second argument is in the
+ follow of every element in the lastpos of the first argument. */
{
tmp.nelem = stk[-1].nfirstpos;
tmp.elems = firstpos - stk[-1].nfirstpos;
- position *p = lastpos - stk[-1].nlastpos - stk[-2].nlastpos;
- for (idx_t j = 0; j < stk[-2].nlastpos; j++)
- {
- merge (&tmp, &d->follows[p[j].index], &merged);
- copy (&merged, &d->follows[p[j].index]);
- }
+ for (position *plim = lastpos - stk[-1].nlastpos,
+ *p = plim - stk[-2].nlastpos;
+ p < plim; p++)
+ merge2 (&d->follows[p->index], &tmp, &merged);
}
/* The firstpos of a CAT node is the firstpos of the first argument,
@@ -2831,20 +2832,21 @@ dfaanalyze (struct dfa *d, bool searchflag)
#endif
}
- if (d->epsilon)
+ if (backward)
{
/* For each follow set that is the follow set of a real position,
replace it with its epsilon closure. */
- epsclosure (d, backword);
+ epsclosure (d, backward);
- for (idx_t i = 0; i < d->tindex; i++)
- free (backword[i].elems);
+ for (idx_t i = 0; i < tindex; i++)
+ free (backward[i].elems);
+ free (backward);
}
dfaoptimize (d);
#ifdef DEBUG
- for (idx_t i = 0; i < d->tindex; i++)
+ for (idx_t i = 0; i < tindex; i++)
if (d->tokens[i] == BEG || d->tokens[i] < NOTCHAR
|| d->tokens[i] == BACKREF || d->tokens[i] == ANYCHAR
|| d->tokens[i] == MBCSET || d->tokens[i] >= CSET)
@@ -2868,12 +2870,10 @@ dfaanalyze (struct dfa *d, bool searchflag)
append (pos, &tmp);
- d->separates = xnmalloc (d->tindex, sizeof *d->separates);
+ d->separates = xcalloc (tindex, sizeof *d->separates);
- for (idx_t i = 0; i < d->tindex; i++)
+ for (idx_t i = 0; i < tindex; i++)
{
- d->separates[i] = 0;
-
if (prev_newline_dependent (d->constraints[i]))
d->separates[i] |= CTX_NEWLINE;
if (prev_letter_dependent (d->constraints[i]))
@@ -2901,7 +2901,6 @@ dfaanalyze (struct dfa *d, bool searchflag)
d->min_trcount++;
d->trcount = 0;
- free (backword);
free (posalloc);
free (stkalloc);
free (merged.elems);
@@ -3172,10 +3171,7 @@ build_state (state_num s, struct dfa *d, unsigned char uc)
mergeit &= d->multibyte_prop[group.elems[j].index];
}
if (mergeit)
- {
- merge (&d->states[0].elems, &group, &tmp);
- copy (&tmp, &group);
- }
+ merge2 (&group, &d->states[0].elems, &tmp);
}
/* Find out if the new state will want any context information,
--
2.17.1
^ permalink raw reply related [flat|nested] 2+ messages in thread
end of thread, other threads:[~2020-09-13 1:55 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-09-13 1:54 [PATCH 1/2] dfa: use backward set in removal of epsilon closure Paul Eggert
2020-09-13 1:54 ` [PATCH 2/2] dfa: epsilon-closure tweaks (Bug#40634) Paul Eggert
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).