Tcl Source Code

Check-in [1ab85d8c7d]
Login
Bounty program for improvements to Tcl and certain Tcl packages.

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Add focussed stack limiting to the RE compiler. Tuning might not yet be right but it passes everything normally checked in the test suite. [Bug 1905562]
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 1ab85d8c7df2ba9745aba4ef87ae8afc26e9b04d
User & Date: dkf 2008-07-01 14:29:11
Context
2008-07-03
17:28
* library/package.tcl: Removed [file readable] testing from [tclPkgUnknown] and fri...
check-in: 570fddae32 user: dgp tags: trunk
2008-07-01
14:29
Add focussed stack limiting to the RE compiler. Tuning might not yet be right but it passes everythi... check-in: 1ab85d8c7d user: dkf tags: trunk
13:24
Fix [2006884] check-in: a8de9c95aa user: dkf tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ChangeLog.

1





2
3
4
5
6
7
8
2008-07-01  Donal K. Fellows  <don[email protected]>






	* tests/string.test: Eliminate non-ASCII characters from the actual
	test script. [Bug 2006884]

2008-06-30  Donal K. Fellows  <[email protected]>

	* doc/ObjectType.3: Clean up typedef formatting.
|
>
>
>
>
>







1
2
3
4
5
6
7
8
9
10
11
12
13
2008-07-01  Donal K. Fellows  <d[email protected]net>

	* generic/regc_nfa.c (duptraverse): Impose a maximum stack depth on
	the single most recursive part of the RE engine. The actual maximum
	may need tuning, but that needs a system with a small stack to carry
	out. [Bug 1905562]

	* tests/string.test: Eliminate non-ASCII characters from the actual
	test script. [Bug 2006884]

2008-06-30  Donal K. Fellows  <[email protected]>

	* doc/ObjectType.3: Clean up typedef formatting.

Changes to generic/regc_nfa.c.

721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743

744
745
746
747
748
749
750
751
752
753
754
755
756










757
758
759
760
761
762
763
764
765
{
    if (start == stop) {
	newarc(nfa, EMPTY, 0, from, to);
	return;
    }

    stop->tmp = to;
    duptraverse(nfa, start, from);
    /* done, except for clearing out the tmp pointers */

    stop->tmp = NULL;
    cleartraverse(nfa, start);
}

/*
 - duptraverse - recursive heart of dupnfa
 ^ static void duptraverse(struct nfa *, struct state *, struct state *);
 */
static void
duptraverse(
    struct nfa *nfa,
    struct state *s,
    struct state *stmp)		/* s's duplicate, or NULL */

{
    struct arc *a;

    if (s->tmp != NULL) {
	return;			/* already done */
    }

    s->tmp = (stmp == NULL) ? newstate(nfa) : stmp;
    if (s->tmp == NULL) {
	assert(NISERR());
	return;
    }











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






|














|
>













>
>
>
>
>
>
>
>
>
>

|







721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
{
    if (start == stop) {
	newarc(nfa, EMPTY, 0, from, to);
	return;
    }

    stop->tmp = to;
    duptraverse(nfa, start, from, 0);
    /* done, except for clearing out the tmp pointers */

    stop->tmp = NULL;
    cleartraverse(nfa, start);
}

/*
 - duptraverse - recursive heart of dupnfa
 ^ static void duptraverse(struct nfa *, struct state *, struct state *);
 */
static void
duptraverse(
    struct nfa *nfa,
    struct state *s,
    struct state *stmp,		/* s's duplicate, or NULL */
    int depth)
{
    struct arc *a;

    if (s->tmp != NULL) {
	return;			/* already done */
    }

    s->tmp = (stmp == NULL) ? newstate(nfa) : stmp;
    if (s->tmp == NULL) {
	assert(NISERR());
	return;
    }

    /*
     * Arbitrary depth limit. Needs tuning, but this value is sufficient to
     * make all normal tests (not reg-33.14) pass.
     */
#define DUPTRAVERSE_MAX_DEPTH 500

    if (depth++ > DUPTRAVERSE_MAX_DEPTH) {
	NERR(REG_ESPACE);
    }

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

Changes to generic/regcomp.c.

127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
static void copyins(struct nfa *, struct state *, struct state *);
static void moveouts(struct nfa *, struct state *, struct state *);
static void copyouts(struct nfa *, struct state *, struct state *);
static void cloneouts(struct nfa *, struct state *, struct state *, struct state *, int);
static void delsub(struct nfa *, struct state *, struct state *);
static void deltraverse(struct nfa *, struct state *, struct state *);
static void dupnfa(struct nfa *, struct state *, struct state *, struct state *, struct state *);
static void duptraverse(struct nfa *, struct state *, struct state *);
static void cleartraverse(struct nfa *, struct state *);
static void specialcolors(struct nfa *);
static long optimize(struct nfa *, FILE *);
static void pullback(struct nfa *, FILE *);
static int pull(struct nfa *, struct arc *);
static void pushfwd(struct nfa *, FILE *);
static int push(struct nfa *, struct arc *);






|







127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
static void copyins(struct nfa *, struct state *, struct state *);
static void moveouts(struct nfa *, struct state *, struct state *);
static void copyouts(struct nfa *, struct state *, struct state *);
static void cloneouts(struct nfa *, struct state *, struct state *, struct state *, int);
static void delsub(struct nfa *, struct state *, struct state *);
static void deltraverse(struct nfa *, struct state *, struct state *);
static void dupnfa(struct nfa *, struct state *, struct state *, struct state *, struct state *);
static void duptraverse(struct nfa *, struct state *, struct state *, int);
static void cleartraverse(struct nfa *, struct state *);
static void specialcolors(struct nfa *);
static long optimize(struct nfa *, FILE *);
static void pullback(struct nfa *, FILE *);
static int pull(struct nfa *, struct arc *);
static void pushfwd(struct nfa *, FILE *);
static int push(struct nfa *, struct arc *);