Tcl

reduced to use {100}{100} for 8.4

reg-33.14's commit to 8.4 segfaults. Should the test be removed, or the
core corrected?

Backported to 8.4 branch.

An enormous number of thanks to all three of you, especially for putting
up with us, the issue tracker we use, and for producing the patches. We now
explicitly check each of those cases to ensure that they do not cause
problems.

Those nail it. Excellent! HEAD fixed; will backport.

Tom and I have both created different patches for the expensive
expression. Tom's patch modifies the color chains to be doubly linked
making the clean-up time O(N) instead of O(N^2). My patch changes the
actual behavior -- it uses a compile-time-specified (REG_MAX_STATES)
maximum number of total NFA states (at a given time) and enforces this
during nfa construction.

Also, it would be greatly appreciated if this bug could be made private
(again) for a couple of weeks. That's when more distros/etc will be ready
to patch their users.

My patch against tcl8.5b3 is attached, and Tom's patch is here:

Index: src/include/regex/regguts.h
===================================================================
RCS file: /cvsroot/pgsql/src/include/regex/regguts.h,v
retrieving revision 1.5
diff -c -r1.5 regguts.h
*** src/include/regex/regguts.h 15 Oct 2005 02:49:46 -0000 1.5
--- src/include/regex/regguts.h 15 Dec 2007 03:56:44 -0000
***************
*** 272,277 ****
--- 272,278 ----
#define freechain outchain
struct arc *inchain; /* *to's ins chain */
struct arc *colorchain; /* color's arc chain */
+ struct arc *colorchain_rev; /* back-link in color's arc chain
*/
};

struct arcbatch
Index: src/backend/regex/regc_color.c
===================================================================
RCS file: /cvsroot/pgsql/src/backend/regex/regc_color.c,v
retrieving revision 1.7
diff -c -r1.7 regc_color.c
*** src/backend/regex/regc_color.c 15 Nov 2007 21:14:37 -0000
1.7
--- src/backend/regex/regc_color.c 15 Dec 2007 03:56:43 -0000
***************
*** 569,580 ****
while ((a = cd->arcs) != NULL)
{
assert(a->co == co);
! /* uncolorchain(cm, a); */
! cd->arcs = a->colorchain;
a->co = sco;
! /* colorchain(cm, a); */
! a->colorchain = scd->arcs;
! scd->arcs = a;
}
freecolor(cm, co);
}
--- 569,577 ----
while ((a = cd->arcs) != NULL)
{
assert(a->co == co);
! uncolorchain(cm, a);
a->co = sco;
! colorchain(cm, a);
}
freecolor(cm, co);
}
***************
*** 604,610 ****
--- 601,610 ----
{
struct colordesc *cd = &cm->cd[a->co];

+ if (cd->arcs)
+ cd->arcs->colorchain_rev = a;
a->colorchain = cd->arcs;
+ a->colorchain_rev = NULL;
cd->arcs = a;
}

***************
*** 616,634 ****
struct arc * a)
{
struct colordesc *cd = &cm->cd[a->co];
! struct arc *aa;

! aa = cd->arcs;
! if (aa == a) /* easy case */
cd->arcs = a->colorchain;
else
{
! for (; aa != NULL && aa->colorchain != a; aa =
aa->colorchain)
! continue;
! assert(aa != NULL);
aa->colorchain = a->colorchain;
}
a->colorchain = NULL; /* paranoia */
}

/*
--- 616,637 ----
struct arc * a)
{
struct colordesc *cd = &cm->cd[a->co];
! struct arc *aa = a->colorchain_rev;

! if (aa == NULL)
! {
! assert(cd->arcs == a);
cd->arcs = a->colorchain;
+ }
else
{
! assert(aa->colorchain == a);
aa->colorchain = a->colorchain;
}
+ if (a->colorchain)
+ a->colorchain->colorchain_rev = aa;
a->colorchain = NULL; /* paranoia */
+ a->colorchain_rev = NULL;
}

/*

Index: src/backend/regex/regc_nfa.c
===================================================================
RCS file: /cvsroot/pgsql/src/backend/regex/regc_nfa.c,v
retrieving revision 1.4
diff -c -r1.4 regc_nfa.c
*** src/backend/regex/regc_nfa.c 15 Oct 2005 02:49:24 -0000
1.4
--- src/backend/regex/regc_nfa.c 15 Dec 2007 03:56:43 -0000
***************
*** 633,638 ****
--- 633,640 ----
for (a = s->outs; a != NULL && !NISERR(); a = a->outchain)
{
duptraverse(nfa, a->to, (struct state *) NULL);
+ if (NISERR())
+ break;
assert(a->to->tmp != NULL);
cparc(nfa, a, s->tmp, a->to->tmp);
}

*** regguts.h.orig Sat Nov 26 21:34:41 2005
--- regguts.h Fri Dec 14 23:07:05 2007
***************
*** 290,295 ****
--- 290,296 ----
# define freechain outchain
struct arc *inchain; /* *to's ins chain */
struct arc *colorchain; /* color's arc chain */
+ struct arc *colorchain_rev; /* back-link in color's arc chain
*/
};

struct arcbatch { /* for bulk allocation of arcs */
*** regc_color.c.orig Wed Oct 20 22:16:21 1999
--- regc_color.c Fri Dec 14 23:07:22 2007
***************
*** 552,563 ****
scd->sub = NOSUB;
while ((a = cd->arcs) != NULL) {
assert(a->co == co);
! /* uncolorchain(cm, a); */
! cd->arcs = a->colorchain;
a->co = sco;
! /* colorchain(cm, a); */
! a->colorchain = scd->arcs;
! scd->arcs = a;
}
freecolor(cm, co);
} else {
--- 552,560 ----
scd->sub = NOSUB;
while ((a = cd->arcs) != NULL) {
assert(a->co == co);
! uncolorchain(cm, a);
a->co = sco;
! colorchain(cm, a);
}
freecolor(cm, co);
} else {
***************
*** 586,592 ****
--- 583,592 ----
{
struct colordesc *cd = &cm->cd[a->co];

+ if (cd->arcs)
+ cd->arcs->colorchain_rev = a;
a->colorchain = cd->arcs;
+ a->colorchain_rev = NULL;
cd->arcs = a;
}

***************
*** 600,617 ****
struct arc *a;
{
struct colordesc *cd = &cm->cd[a->co];
! struct arc *aa;

! aa = cd->arcs;
! if (aa == a) /* easy case */
cd->arcs = a->colorchain;
! else {
! for (; aa != NULL && aa->colorchain != a; aa =
aa->colorchain)
! continue;
! assert(aa != NULL);
aa->colorchain = a->colorchain;
}
a->colorchain = NULL; /* paranoia */
}

/*
--- 600,618 ----
struct arc *a;
{
struct colordesc *cd = &cm->cd[a->co];
! struct arc *aa = a->colorchain_rev;

! if (aa == NULL) {
! assert(cd->arcs == a);
cd->arcs = a->colorchain;
! } else {
! assert(aa->colorchain == a);
aa->colorchain = a->colorchain;
}
+ if (a->colorchain)
+ a->colorchain->colorchain_rev = aa;
a->colorchain = NULL; /* paranoia */
+ a->colorchain_rev = NULL;
}

/*

*** regc_nfa.c.orig Wed Aug 4 21:16:57 1999
--- regc_nfa.c Fri Dec 14 23:08:30 2007
***************
*** 651,656 ****
--- 651,658 ----

for (a = s->outs; a != NULL && !NISERR(); a = a->outchain) {
duptraverse(nfa, a->to, (struct state *)NULL);
+ if (NISERR())
+ break;
assert(a->to->tmp != NULL);
cparc(nfa, a, s->tmp, a->to->tmp);
}

File Added: tcl8.5b3-state-limit.patch

Opening now that fixes for critical parts are done.

I don't seem to have access to bug 1810038, but I've pointed Tom to it and
to the repository where it looks like some fixes have been submitted.

thanks!
will

My patches are attached to
Tcl Bug 1810038 if Tom
wants to compare two independently
derived solutions.

First two (crash and hang)
are now fixed. Last issue
is an optimization request.
Worth pursuing, but a lower
priority.

If you drop Tom an email, he has some patches to share/discuss. His
patches haven't appeared here because, in general, only I can access this
"private" bug. Please drop him an email - he's indicated that he's very
happy to share them, but he wants to confirm some of his ideas first.

If this doesn't work for you, I can ask him for what he has. I was hoping
that we'd have some follow up by email rather than via this limited
tracker. (as is, I think this bug has been mirrored to your mailing
lists/nabble which was more disclosure than expected :-/ )

Let me know if you'd like me to attach what he has here - it just makes it
harder to discuss it.

cheers,
will

Ok, Having dug deep here, I can
confirm Tom Lane's diagnosis.
It's a shame his alleged patches
have not appeared here.

Backported. Issue is still prio 9; can only drop once the second part is
also fixed and backported. (Third issue is bad, but not *that* bad...)

Please backport the fix for 8.4.17 as well.

Thanks!

first issue fixed;

second issue duplicate of 1810038?

And 3rd issue looks more like
a feature request than a bug?
Still important but better handled
in another ticket?

No patches?

Fixed first issue though; I can understand that "locally". :-)