summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authordgp <dgp@users.sourceforge.net>2016-02-03 19:08:54 (GMT)
committerdgp <dgp@users.sourceforge.net>2016-02-03 19:08:54 (GMT)
commitf2f80791afb9f9a8a3a8da207691dd4bcf2f4da6 (patch)
tree4c1332674af659ee343f9bfb2c4e7b998fc99280
parent413c14a38212f4a842d28cf9aaa9d82c9c7f71bf (diff)
parent05a77f3559bff860de052d23fb8cdefdadd53b3c (diff)
downloadtcl-f2f80791afb9f9a8a3a8da207691dd4bcf2f4da6.zip
tcl-f2f80791afb9f9a8a3a8da207691dd4bcf2f4da6.tar.gz
tcl-f2f80791afb9f9a8a3a8da207691dd4bcf2f4da6.tar.bz2
merge 8.5
-rw-r--r--generic/regc_nfa.c84
-rw-r--r--generic/regcomp.c2
-rw-r--r--generic/regerrs.h2
-rw-r--r--generic/regex.h2
-rw-r--r--generic/regguts.h16
-rw-r--r--tests/regexp.test2
6 files changed, 80 insertions, 28 deletions
diff --git a/generic/regc_nfa.c b/generic/regc_nfa.c
index 6280e5e..d155b23 100644
--- a/generic/regc_nfa.c
+++ b/generic/regc_nfa.c
@@ -62,6 +62,7 @@ newnfa(
nfa->nstates = 0;
nfa->cm = cm;
nfa->v = v;
+ nfa->size = 0;
nfa->bos[0] = nfa->bos[1] = COLORLESS;
nfa->eos[0] = nfa->eos[1] = COLORLESS;
nfa->parent = parent; /* Precedes newfstate so parent is valid. */
@@ -89,6 +90,61 @@ newnfa(
}
/*
+ - TooManyStates - checks if the max states exceeds the compile-time value
+ ^ static int TooManyStates(struct nfa *);
+ */
+static int
+TooManyStates(
+ struct nfa *nfa)
+{
+ struct nfa *parent = nfa->parent;
+ size_t sz = nfa->size;
+
+ while (parent != NULL) {
+ sz = parent->size;
+ parent = parent->parent;
+ }
+ if (sz > REG_MAX_STATES) {
+ return 1;
+ }
+ return 0;
+}
+
+/*
+ - IncrementSize - increases the tracked size of the NFA and its parents.
+ ^ static void IncrementSize(struct nfa *);
+ */
+static void
+IncrementSize(
+ struct nfa *nfa)
+{
+ struct nfa *parent = nfa->parent;
+
+ nfa->size++;
+ while (parent != NULL) {
+ parent->size++;
+ parent = parent->parent;
+ }
+}
+
+/*
+ - DecrementSize - increases the tracked size of the NFA and its parents.
+ ^ static void DecrementSize(struct nfa *);
+ */
+static void
+DecrementSize(
+ struct nfa *nfa)
+{
+ struct nfa *parent = nfa->parent;
+
+ nfa->size--;
+ while (parent != NULL) {
+ parent->size--;
+ parent = parent->parent;
+ }
+}
+
+/*
- freenfa - free an entire NFA
^ static VOID freenfa(struct nfa *);
*/
@@ -124,20 +180,20 @@ newstate(
{
struct state *s;
+ if (TooManyStates(nfa)) {
+ /* XXX: add specific error for this */
+ NERR(REG_ETOOBIG);
+ return NULL;
+ }
if (nfa->free != NULL) {
s = nfa->free;
nfa->free = s->next;
} else {
- if (nfa->v->spaceused >= REG_MAX_COMPILE_SPACE) {
- NERR(REG_ETOOBIG);
- return NULL;
- }
s = (struct state *) MALLOC(sizeof(struct state));
if (s == NULL) {
NERR(REG_ESPACE);
return NULL;
}
- nfa->v->spaceused += sizeof(struct state);
s->oas.next = NULL;
s->free = NULL;
s->noas = 0;
@@ -161,6 +217,12 @@ newstate(
}
s->prev = nfa->slast;
nfa->slast = s;
+
+ /*
+ * Track the current size and the parent size.
+ */
+
+ IncrementSize(nfa);
return s;
}
@@ -231,6 +293,7 @@ freestate(
s->prev = NULL;
s->next = nfa->free; /* don't delete it, put it on the free list */
nfa->free = s;
+ DecrementSize(nfa);
}
/*
@@ -249,13 +312,11 @@ destroystate(
for (ab=s->oas.next ; ab!=NULL ; ab=abnext) {
abnext = ab->next;
FREE(ab);
- nfa->v->spaceused -= sizeof(struct arcbatch);
}
s->ins = NULL;
s->outs = NULL;
s->next = NULL;
FREE(s);
- nfa->v->spaceused -= sizeof(struct state);
}
/*
@@ -378,19 +439,14 @@ allocarc(
*/
if (s->free == NULL) {
- struct arcbatch *newAb;
+ struct arcbatch *newAb = (struct arcbatch *)
+ MALLOC(sizeof(struct arcbatch));
int i;
- if (nfa->v->spaceused >= REG_MAX_COMPILE_SPACE) {
- NERR(REG_ETOOBIG);
- return NULL;
- }
- newAb = (struct arcbatch *) MALLOC(sizeof(struct arcbatch));
if (newAb == NULL) {
NERR(REG_ESPACE);
return NULL;
}
- nfa->v->spaceused += sizeof(struct arcbatch);
newAb->next = s->oas.next;
s->oas.next = newAb;
diff --git a/generic/regcomp.c b/generic/regcomp.c
index 8287b7e..fda40e0 100644
--- a/generic/regcomp.c
+++ b/generic/regcomp.c
@@ -227,7 +227,6 @@ struct vars {
struct cvec *cv2; /* utility cvec */
struct subre *lacons; /* lookahead-constraint vector */
int nlacons; /* size of lacons */
- size_t spaceused; /* approx. space used for compilation */
};
/* parsing macros; most know that `v' is the struct vars pointer */
@@ -337,7 +336,6 @@ compile(
v->cv2 = NULL;
v->lacons = NULL;
v->nlacons = 0;
- v->spaceused = 0;
re->re_magic = REMAGIC;
re->re_info = 0; /* bits get set during parse */
re->re_csize = sizeof(chr);
diff --git a/generic/regerrs.h b/generic/regerrs.h
index ee203d5..72548ff 100644
--- a/generic/regerrs.h
+++ b/generic/regerrs.h
@@ -16,5 +16,5 @@
{ REG_INVARG, "REG_INVARG", "invalid argument to regex function" },
{ REG_MIXED, "REG_MIXED", "character widths of regex and string differ" },
{ REG_BADOPT, "REG_BADOPT", "invalid embedded option" },
-{ REG_ETOOBIG, "REG_ETOOBIG", "regular expression is too complex" },
+{ REG_ETOOBIG, "REG_ETOOBIG", "nfa has too many states" },
{ REG_ECOLORS, "REG_ECOLORS", "too many colors" },
diff --git a/generic/regex.h b/generic/regex.h
index b5b11bd..b5dce50 100644
--- a/generic/regex.h
+++ b/generic/regex.h
@@ -277,7 +277,7 @@ typedef struct {
#define REG_INVARG 16 /* invalid argument to regex function */
#define REG_MIXED 17 /* character widths of regex and string differ */
#define REG_BADOPT 18 /* invalid embedded option */
-#define REG_ETOOBIG 19 /* regular expression is too complex */
+#define REG_ETOOBIG 19 /* nfa has too many states */
#define REG_ECOLORS 20 /* too many colors */
/* two specials for debugging and testing */
#define REG_ATOI 101 /* convert error-code name to number */
diff --git a/generic/regguts.h b/generic/regguts.h
index 72bdcb3..7ed8ec1 100644
--- a/generic/regguts.h
+++ b/generic/regguts.h
@@ -307,6 +307,9 @@ struct nfa {
struct colormap *cm; /* the color map */
color bos[2]; /* colors, if any, assigned to BOS and BOL */
color eos[2]; /* colors, if any, assigned to EOS and EOL */
+ size_t size; /* Current NFA size; differs from nstates as
+ * it also counts the number of states created
+ * by children of this state. */
struct vars *v; /* simplifies compile error reporting */
struct nfa *parent; /* parent NFA, if any */
};
@@ -336,16 +339,11 @@ struct cnfa {
#define NULLCNFA(cnfa) ((cnfa).nstates == 0)
/*
- * This symbol limits the transient heap space used by the regex compiler,
- * and thereby also the maximum complexity of NFAs that we'll deal with.
- * Currently we only count NFA states and arcs against this; the other
- * transient data is generally not large enough to notice compared to those.
- * Note that we do not charge anything for the final output data structures
- * (the compacted NFA and the colormap).
+ * Used to limit the maximum NFA size to something sane. [Bug 1810264]
*/
-#ifndef REG_MAX_COMPILE_SPACE
-#define REG_MAX_COMPILE_SPACE \
- (100000 * sizeof(struct state) + 100000 * sizeof(struct arcbatch))
+
+#ifndef REG_MAX_STATES
+# define REG_MAX_STATES 100000
#endif
/*
diff --git a/tests/regexp.test b/tests/regexp.test
index 7878d41..362f425 100644
--- a/tests/regexp.test
+++ b/tests/regexp.test
@@ -716,7 +716,7 @@ test regexp-22.4 {Bug 3606139} -setup {
[a 668]([a 55])[a 668]([a 55])[a 668]([a 55])[a 511]] {}] a
} -cleanup {
rename a {}
-} -returnCodes 1 -match glob -result {couldn't compile regular expression pattern: *}
+} -returnCodes 1 -result {couldn't compile regular expression pattern: nfa has too many states}
test regexp-22.5 {Bug 3610026} -setup {
set e {}
set cp 99