Tcl Source Code

Check-in [d58c269d4e]
Login
Bounty program for improvements to Tcl and certain Tcl packages.
Tcl 2019 Conference, Houston/TX, US, Nov 4-8
Send your abstracts to [email protected]
or submit via the online form by Sep 9.

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

Overview
Comment:Merge trunk
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | bug-5d170b5ca5
Files: files | file ages | folders
SHA1: d58c269d4ed59281c49b5b6847e1de145975fd08
User & Date: jan.nijtmans 2015-09-23 12:19:12
References
2015-09-23
12:21 Ticket [57945b574a] lock in forking process under heavy multithreading status still Open with 3 other changes artifact: 6429a791a6 user: jan.nijtmans
Context
2015-09-24
10:03
merge trunk Closed-Leaf check-in: b65985a504 user: jan.nijtmans tags: bug-5d170b5ca5
2015-09-23
12:19
Merge trunk check-in: d58c269d4e user: jan.nijtmans tags: bug-5d170b5ca5
10:29
Micro-optimization handling Tcl_Panic(), suggested by D. Richard Hipp. As a side-effect, this is as ... check-in: 4a27b0487a user: jan.nijtmans tags: trunk
2015-09-07
08:35
Fix for [5d170b5ca5] now available for widespread testing (incl. HPUX and OSX) check-in: 3ff8944fc4 user: jan.nijtmans tags: bug-5d170b5ca5
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to generic/regc_color.c.

255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
...
773
774
775
776
777
778
779
780





781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
	 */

	if (cm->max == MAX_COLOR) {
	    CERR(REG_ECOLORS);
	    return COLORLESS;		/* too many colors */
	}
	n = cm->ncds * 2;
	if (n < MAX_COLOR + 1) {
	    n = MAX_COLOR + 1;
	}
	if (cm->cd == cm->cdspace) {
	    newCd = (struct colordesc *) MALLOC(n * sizeof(struct colordesc));
	    if (newCd != NULL) {
		memcpy(newCd, cm->cdspace,
			cm->ncds * sizeof(struct colordesc));
................................................................................
	    if (cd->flags&PSEUDO) {
		fprintf(f, "#%2ld%s(ps): ", (long) co, has);
	    } else {
		fprintf(f, "#%2ld%s(%2d): ", (long) co, has, cd->nchrs);
	    }

	    /*
	     * It's hard to do this more efficiently.





	     */

	    for (c=CHR_MIN ; c<CHR_MAX ; c++) {
		if (GETCOLOR(cm, c) == co) {
		    dumpchr(c, f);
		}
	    }
	    assert(c == CHR_MAX);
	    if (GETCOLOR(cm, c) == co) {
		dumpchr(c, f);
	    }
	    fprintf(f, "\n");
	}
    }
}
 
/*
 - fillcheck - check proper filling of a tree






|







 







|
>
>
>
>
>


|




<
<
<
<







255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
...
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792




793
794
795
796
797
798
799
	 */

	if (cm->max == MAX_COLOR) {
	    CERR(REG_ECOLORS);
	    return COLORLESS;		/* too many colors */
	}
	n = cm->ncds * 2;
	if (n > MAX_COLOR + 1) {
	    n = MAX_COLOR + 1;
	}
	if (cm->cd == cm->cdspace) {
	    newCd = (struct colordesc *) MALLOC(n * sizeof(struct colordesc));
	    if (newCd != NULL) {
		memcpy(newCd, cm->cdspace,
			cm->ncds * sizeof(struct colordesc));
................................................................................
	    if (cd->flags&PSEUDO) {
		fprintf(f, "#%2ld%s(ps): ", (long) co, has);
	    } else {
		fprintf(f, "#%2ld%s(%2d): ", (long) co, has, cd->nchrs);
	    }

	    /*
	     * Unfortunately, it's hard to do this next bit more efficiently.
	     *
	     * Spencer's original coding has the loop iterating from CHR_MIN
	     * to CHR_MAX, but that's utterly unusable for 32-bit chr, or
	     * even 16-bit.  For debugging purposes it seems fine to print
	     * only chr codes up to 1000 or so.
	     */

	    for (c=CHR_MIN ; c<1000 ; c++) {
		if (GETCOLOR(cm, c) == co) {
		    dumpchr(c, f);
		}
	    }




	    fprintf(f, "\n");
	}
    }
}
 
/*
 - fillcheck - check proper filling of a tree

Changes to generic/regc_cvec.c.

77
78
79
80
81
82
83

84
85
86
87
88
89
90
 ^ static void addchr(struct cvec *, pchr);
 */
static void
addchr(
    struct cvec *cv,		/* character vector */
    pchr c)			/* character to add */
{

    cv->chrs[cv->nchrs++] = (chr)c;
}
 
/*
 - addrange - add a range to a cvec
 ^ static void addrange(struct cvec *, pchr, pchr);
 */






>







77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 ^ static void addchr(struct cvec *, pchr);
 */
static void
addchr(
    struct cvec *cv,		/* character vector */
    pchr c)			/* character to add */
{
    assert(cv->nchrs < cv->chrspace);
    cv->chrs[cv->nchrs++] = (chr)c;
}
 
/*
 - addrange - add a range to a cvec
 ^ static void addrange(struct cvec *, pchr, pchr);
 */

Changes to generic/regc_lex.c.

1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
 */
static chr
newline(void)
{
    return CHR('\n');
}
 
/*
 - ch - return the chr sequence for regc_locale.c's fake collating element ch
 * This helps confine use of CHR to this source file.  Beware that the caller
 * knows how long the sequence is.
 ^ #ifdef REG_DEBUG
 ^ static const chr *ch(NOPARMS);
 ^ #endif
 */
#ifdef REG_DEBUG
static const chr *
ch(void)
{
    static const chr chstr[] = { CHR('c'), CHR('h'), CHR('\0') };

    return chstr;
}
#endif
 
/*
 - chrnamed - return the chr known by a given (chr string) name
 * The code is a bit clumsy, but this routine gets only such specialized
 * use that it hardly matters.
 ^ static chr chrnamed(struct vars *, const chr *, const chr *, pchr);
 */
static chr






<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







1134
1135
1136
1137
1138
1139
1140


















1141
1142
1143
1144
1145
1146
1147
 */
static chr
newline(void)
{
    return CHR('\n');
}
 


















/*
 - chrnamed - return the chr known by a given (chr string) name
 * The code is a bit clumsy, but this routine gets only such specialized
 * use that it hardly matters.
 ^ static chr chrnamed(struct vars *, const chr *, const chr *, pchr);
 */
static chr

Changes to generic/regc_nfa.c.

1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658

1659
1660
1661



1662
1663
1664
1665
1666
1667
1668
....
1677
1678
1679
1680
1681
1682
1683

1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
....
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
....
1759
1760
1761
1762
1763
1764
1765

1766
1767
1768
1769
1770
1771
1772
....
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
    assert(!NISERR());

    nstates = 0;
    narcs = 0;
    for (s = nfa->states; s != NULL; s = s->next) {
	nstates++;
	narcs += 1 + s->nouts + 1;
	/* 1 as a fake for flags, nouts for arcs, 1 as endmarker */
    }


    cnfa->states = (struct carc **) MALLOC(nstates * sizeof(struct carc *));
    cnfa->arcs = (struct carc *) MALLOC(narcs * sizeof(struct carc));
    if (cnfa->states == NULL || cnfa->arcs == NULL) {



	if (cnfa->states != NULL) {
	    FREE(cnfa->states);
	}
	if (cnfa->arcs != NULL) {
	    FREE(cnfa->arcs);
	}
	NERR(REG_ESPACE);
................................................................................
    cnfa->eos[1] = nfa->eos[1];
    cnfa->ncolors = maxcolor(nfa->cm) + 1;
    cnfa->flags = 0;

    ca = cnfa->arcs;
    for (s = nfa->states; s != NULL; s = s->next) {
	assert((size_t) s->no < nstates);

	cnfa->states[s->no] = ca;
	ca->co = 0;		/* clear and skip flags "arc" */
	ca++;
	first = ca;
	for (a = s->outs; a != NULL; a = a->outchain) {
	    switch (a->type) {
	    case PLAIN:
		ca->co = a->co;
		ca->to = a->to->no;
		ca++;
................................................................................
    assert(cnfa->nstates != 0);

    /*
     * Mark no-progress states.
     */

    for (a = nfa->pre->outs; a != NULL; a = a->outchain) {
	cnfa->states[a->to->no]->co = 1;
    }
    cnfa->states[nfa->pre->no]->co = 1;
}
 
/*
 - carcsort - sort compacted-NFA arcs by color
 * Really dumb algorithm, but if the list is long enough for that to matter,
 * you're in real trouble anyway.
 ^ static void carcsort(struct carc *, struct carc *);
................................................................................
 */
static void
freecnfa(
    struct cnfa *cnfa)
{
    assert(cnfa->nstates != 0);	/* not empty already */
    cnfa->nstates = 0;

    FREE(cnfa->states);
    FREE(cnfa->arcs);
}
 
/*
 - dumpnfa - dump an NFA in human-readable form
 ^ static void dumpnfa(struct nfa *, FILE *);
................................................................................
	fprintf(f, ", eol [%ld]", (long) cnfa->eos[1]);
    }
    if (cnfa->flags&HASLACONS) {
	fprintf(f, ", haslacons");
    }
    fprintf(f, "\n");
    for (st = 0; st < cnfa->nstates; st++) {
	dumpcstate(st, cnfa->states[st], cnfa, f);
    }
    fflush(f);
#endif
}
 
#ifdef REG_DEBUG		/* subordinates of dumpcnfa */
/*
 ^ #ifdef REG_DEBUG
 */

/*
 - dumpcstate - dump a compacted-NFA state in human-readable form
 ^ static void dumpcstate(int, struct carc *, struct cnfa *, FILE *);
 */
static void
dumpcstate(
    int st,
    struct carc *ca,
    struct cnfa *cnfa,
    FILE *f)
{
    int i;
    int pos;

    fprintf(f, "%d%s", st, (ca[0].co) ? ":" : ".");
    pos = 1;
    for (i = 1; ca[i].co != COLORLESS; i++) {
	if (ca[i].co < cnfa->ncolors) {
	    fprintf(f, "\t[%ld]->%d", (long) ca[i].co, ca[i].to);
	} else {
	    fprintf(f, "\t:%ld:->%d", (long) ca[i].co-cnfa->ncolors,ca[i].to);
	}
	if (pos == 5) {
	    fprintf(f, "\n");
	    pos = 1;
	} else {
	    pos++;
	}
    }
    if (i == 1 || pos != 1) {
	fprintf(f, "\n");
    }
    fflush(f);
}

/*
 ^ #endif






|
<


>


|
>
>
>







 







>

<
<







 







|

|







 







>







 







|












|




<



|


|

|
|
|

|








|







1648
1649
1650
1651
1652
1653
1654
1655

1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
....
1680
1681
1682
1683
1684
1685
1686
1687
1688


1689
1690
1691
1692
1693
1694
1695
....
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
....
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
....
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008

2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
    assert(!NISERR());

    nstates = 0;
    narcs = 0;
    for (s = nfa->states; s != NULL; s = s->next) {
	nstates++;
	narcs += s->nouts + 1;	/* need one extra for endmarker */

    }

    cnfa->stflags = (char *) MALLOC(nstates * sizeof(char));
    cnfa->states = (struct carc **) MALLOC(nstates * sizeof(struct carc *));
    cnfa->arcs = (struct carc *) MALLOC(narcs * sizeof(struct carc));
    if (cnfa->stflags == NULL || cnfa->states == NULL || cnfa->arcs == NULL) {
	if (cnfa->stflags != NULL) {
	    FREE(cnfa->stflags);
	}
	if (cnfa->states != NULL) {
	    FREE(cnfa->states);
	}
	if (cnfa->arcs != NULL) {
	    FREE(cnfa->arcs);
	}
	NERR(REG_ESPACE);
................................................................................
    cnfa->eos[1] = nfa->eos[1];
    cnfa->ncolors = maxcolor(nfa->cm) + 1;
    cnfa->flags = 0;

    ca = cnfa->arcs;
    for (s = nfa->states; s != NULL; s = s->next) {
	assert((size_t) s->no < nstates);
	cnfa->stflags[s->no] = 0;
	cnfa->states[s->no] = ca;


	first = ca;
	for (a = s->outs; a != NULL; a = a->outchain) {
	    switch (a->type) {
	    case PLAIN:
		ca->co = a->co;
		ca->to = a->to->no;
		ca++;
................................................................................
    assert(cnfa->nstates != 0);

    /*
     * Mark no-progress states.
     */

    for (a = nfa->pre->outs; a != NULL; a = a->outchain) {
	cnfa->stflags[a->to->no] = CNFA_NOPROGRESS;
    }
    cnfa->stflags[nfa->pre->no] = CNFA_NOPROGRESS;
}
 
/*
 - carcsort - sort compacted-NFA arcs by color
 * Really dumb algorithm, but if the list is long enough for that to matter,
 * you're in real trouble anyway.
 ^ static void carcsort(struct carc *, struct carc *);
................................................................................
 */
static void
freecnfa(
    struct cnfa *cnfa)
{
    assert(cnfa->nstates != 0);	/* not empty already */
    cnfa->nstates = 0;
    FREE(cnfa->stflags);
    FREE(cnfa->states);
    FREE(cnfa->arcs);
}
 
/*
 - dumpnfa - dump an NFA in human-readable form
 ^ static void dumpnfa(struct nfa *, FILE *);
................................................................................
	fprintf(f, ", eol [%ld]", (long) cnfa->eos[1]);
    }
    if (cnfa->flags&HASLACONS) {
	fprintf(f, ", haslacons");
    }
    fprintf(f, "\n");
    for (st = 0; st < cnfa->nstates; st++) {
	dumpcstate(st, cnfa, f);
    }
    fflush(f);
#endif
}
 
#ifdef REG_DEBUG		/* subordinates of dumpcnfa */
/*
 ^ #ifdef REG_DEBUG
 */

/*
 - dumpcstate - dump a compacted-NFA state in human-readable form
 ^ static void dumpcstate(int, struct cnfa *, FILE *);
 */
static void
dumpcstate(
    int st,

    struct cnfa *cnfa,
    FILE *f)
{
    struct carc *ca;
    int pos;

    fprintf(f, "%d%s", st, (cnfa->stflags[st] & CNFA_NOPROGRESS) ? ":" : ".");
    pos = 1;
    for (ca = cnfa->states[st]; ca->co != COLORLESS; ca++) {
	if (ca->co < cnfa->ncolors) {
	    fprintf(f, "\t[%ld]->%d", (long) ca->co, ca->to);
	} else {
	    fprintf(f, "\t:%ld:->%d", (long) (ca->co - cnfa->ncolors), ca->to);
	}
	if (pos == 5) {
	    fprintf(f, "\n");
	    pos = 1;
	} else {
	    pos++;
	}
    }
    if (ca == cnfa->states[st] || pos != 1) {
	fprintf(f, "\n");
    }
    fflush(f);
}

/*
 ^ #endif

Changes to generic/regcomp.c.

79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
...
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
...
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
...
254
255
256
257
258
259
260
261
262
263
264
265
266


267
268
269
270
271
272
273
...
589
590
591
592
593
594
595
596

597
598
599


600
601
602


603
604
605
606
607
608
609
...
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
....
1099
1100
1101
1102
1103
1104
1105


1106
1107
1108
1109
1110






1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
....
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
....
1203
1204
1205
1206
1207
1208
1209


1210
1211
1212
1213
1214
1215
1216


1217

1218
1219




1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231


















1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
....
1303
1304
1305
1306
1307
1308
1309


1310
1311
1312
1313
1314
1315
1316
....
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
....
1769
1770
1771
1772
1773
1774
1775
1776

1777
1778
1779
1780
1781
1782
1783
....
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828













1829
1830
1831
1832
1833
1834
1835
....
1928
1929
1930
1931
1932
1933
1934
1935
1936


1937
1938
1939
1940
1941
1942

1943
1944
1945
1946
1947
1948
1949
1950
1951
1952


1953
1954
1955
1956
1957
1958
1959
....
1993
1994
1995
1996
1997
1998
1999

2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011

2012
2013
2014
2015
2016
2017
2018
....
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
....
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
static void lexword(struct vars *);
static int next(struct vars *);
static int lexescape(struct vars *);
static int lexdigits(struct vars *, int, int, int);
static int brenext(struct vars *, pchr);
static void skip(struct vars *);
static chr newline(NOPARMS);
#ifdef REG_DEBUG
static const chr *ch(NOPARMS);
#endif
static chr chrnamed(struct vars *, const chr *, const chr *, pchr);
/* === regc_color.c === */
static void initcm(struct vars *, struct colormap *);
static void freecm(struct colormap *);
static void cmtreefree(struct colormap *, union tree *, int);
static color setcolor(struct colormap *, pchr, pcolor);
static color maxcolor(struct colormap *);
................................................................................
static void dumpstate(struct state *, FILE *);
static void dumparcs(struct state *, FILE *);
static int dumprarcs(struct arc *, struct state *, FILE *, int);
static void dumparc(struct arc *, struct state *, FILE *);
#endif
static void dumpcnfa(struct cnfa *, FILE *);
#ifdef REG_DEBUG
static void dumpcstate(int, struct carc *, struct cnfa *, FILE *);
#endif
/* === regc_cvec.c === */
static struct cvec *clearcvec(struct cvec *);
static void addchr(struct cvec *, pchr);
static void addrange(struct cvec *, pchr, pchr);
static struct cvec *newcvec(int, int);
static struct cvec *getcvec(struct vars *, int, int);
................................................................................
    struct nfa *nfa;		/* the NFA */
    struct colormap *cm;	/* character color map */
    color nlcolor;		/* color of newline */
    struct state *wordchrs;	/* state in nfa holding word-char outarcs */
    struct subre *tree;		/* subexpression tree */
    struct subre *treechain;	/* all tree nodes allocated */
    struct subre *treefree;	/* any free tree nodes */
    int ntree;			/* number of tree nodes */
    struct cvec *cv;		/* interface cvec */
    struct cvec *cv2;		/* utility cvec */
    struct subre *lacons;	/* lookahead-constraint vector */
    int nlacons;		/* size of lacons */
};

/* parsing macros; most know that `v' is the struct vars pointer */
#define	NEXT()	(next(v))		/* advance by one token */
#define	SEE(t)	(v->nexttype == (t))	/* is next token this? */
#define	EAT(t)	(SEE(t) && next(v))	/* if next is this, swallow it */
#define	VISERR(vv)	((vv)->err != 0)/* have we seen an error yet? */
#define	ISERR()	VISERR(v)
#define	VERR(vv,e) \
	((vv)->nexttype = EOS, ((vv)->err) ? (vv)->err : ((vv)->err = (e)))
#define	ERR(e)	VERR(v, e)		/* record an error */
#define	NOERR()	{if (ISERR()) return;}	/* if error seen, return */
#define	NOERRN()	{if (ISERR()) return NULL;}	/* NOERR with retval */
#define	NOERRZ()	{if (ISERR()) return 0;}	/* NOERR with retval */
#define	INSIST(c, e)	((c) ? 0 : ERR(e))	/* if condition false, error */
#define	NOTE(b)	(v->re->re_info |= (b))		/* note visible condition */
#define	EMPTYARC(x, y)	newarc(v->nfa, EMPTY, 0, x, y)

/* token type codes, some also used as NFA arc types */
#define	EMPTY	'n'		/* no token present */
#define	EOS	'e'		/* end of string */
#define	PLAIN	'p'		/* ordinary character */
................................................................................
#define	PREFER	'P'		/* length preference */

/* is an arc colored, and hence on a color chain? */
#define	COLORED(a) \
	((a)->type == PLAIN || (a)->type == AHEAD || (a)->type == BEHIND)

/* static function list */
static struct fns functions = {
    rfree,			/* regfree insides */
};
 
/*
 - compile - compile regular expression


 ^ int compile(regex_t *, const chr *, size_t, int);
 */
int
compile(
    regex_t *re,
    const chr *string,
    size_t len,
................................................................................
    for (a=pre->outs ; a!=NULL ; a=a->outchain) {
	s = a->to;
	for (b=s->ins ; b!=NULL ; b=b->inchain) {
	    if (b->from != pre) {
		break;
	    }
	}
	if (b != NULL && s->tmp == NULL) {

	    /*
	     * Must be split if not already in the list (fixes bugs 505048,
	     * 230589, 840258, 504785).


	     */

	    s->tmp = slist;


	    slist = s;
	}
    }

    /*
     * Do the splits.
     */
................................................................................
	    b = a->inchain;

	    if (a->from != pre) {
		cparc(nfa, a, a->from, s2);
		freearc(nfa, a);
	    }
	}
	s2 = s->tmp;
	s->tmp = NULL;		/* clean up while we're at it */
    }
}
 
/*
 - parse - parse an RE
 * This is actually just the top level, which parses a bunch of branches tied
................................................................................
	atom = subre(v, '=', 0, lp, rp);
	NOERR();
    }

    /*
     * Prepare a general-purpose state skeleton.
     *


     *    ---> [s] ---prefix---> [begin] ---atom---> [end] ----rest---> [rp]
     *   /                                            /
     * [lp] ----> [s2] ----bypass---------------------
     *
     * where bypass is an empty, and prefix is some repetitions of atom






     */

    s = newstate(v->nfa);	/* first, new endpoints for the atom */
    s2 = newstate(v->nfa);
    NOERR();
    moveouts(v->nfa, lp, s);
    moveins(v->nfa, rp, s2);
    NOERR();
    atom->begin = s;
    atom->end = s2;
    s = newstate(v->nfa);	/* and spots for prefix and bypass */
    s2 = newstate(v->nfa);
    NOERR();
    EMPTYARC(lp, s);
    EMPTYARC(lp, s2);
    NOERR();

    /*
     * Break remaining subRE into x{...} and what follows.
     */

    t = subre(v, '.', COMBINE(qprefer, atom->flags), lp, rp);
................................................................................

	dupnfa(v->nfa, v->subs[subno]->begin, v->subs[subno]->end,
		atom->begin, atom->end);
	NOERR();
    }

    /*
     * It's quantifier time; first, turn x{0,...} into x{1,...}|empty
     */

    if (m == 0) {
	EMPTYARC(s2, atom->end);/* the bypass */
	assert(PREF(qprefer) != 0);
	f = COMBINE(qprefer, atom->flags);
	t = subre(v, '|', f, lp, atom->end);
	NOERR();
	t->left = atom;
	t->right = subre(v, '|', PREF(f), s2, atom->end);
	NOERR();
	t->right->left = subre(v, '=', 0, s2, atom->end);
	NOERR();
	*atomp = t;
	atomp = &t->left;
	m = 1;
    }

    /*
     * Deal with the rest of the quantifier.
     */

    if (atomtype == BACKREF) {
	/*
	 * Special case: backrefs have internal quantifiers.
	 */

................................................................................
	 * Just stuff everything into atom.
	 */

	repeat(v, atom->begin, atom->end, m, n);
	atom->min = (short) m;
	atom->max = (short) n;
	atom->flags |= COMBINE(qprefer, atom->flags);


    } else if (m == 1 && n == 1) {
	/*
	 * No/vacuous quantifier: done.
	 */

	EMPTYARC(s, atom->begin);	/* empty prefix */
    } else {


	/*

	 * Turn x{m,n} into x{m-1,n-1}x, with capturing parens in only second
	 * x




	 */

	dupnfa(v->nfa, atom->begin, atom->end, s, atom->begin);
	assert(m >= 1 && m != DUPINF && n >= 1);
	repeat(v, s, atom->begin, m-1, (n == DUPINF) ? n : n-1);
	f = COMBINE(qprefer, atom->flags);
	t = subre(v, '.', f, s, atom->end);	/* prefix and atom */
	NOERR();
	t->left = subre(v, '=', PREF(f), s, atom->begin);
	NOERR();
	t->right = atom;
	*atomp = t;


















    }

    /*
     * And finally, look after that postponed recursion.
     */

    t = top->right;
    if (!(SEE('|') || SEE(stopper) || SEE(EOS))) {
	t->right = parsebranch(v, stopper, type, atom->end, rp, 1);
    } else {
	EMPTYARC(atom->end, rp);
	t->right = subre(v, '=', 0, atom->end, rp);
    }
    NOERR();
    assert(SEE('|') || SEE(stopper) || SEE(EOS));
    t->flags |= COMBINE(t->flags, t->right->flags);
    top->flags |= COMBINE(top->flags, t->flags);
}
 
................................................................................
	return 0;
    }
    return n;
}
 
/*
 - repeat - replicate subNFA for quantifiers


 * The duplication sequences used here are chosen carefully so that any
 * pointers starting out pointing into the subexpression end up pointing into
 * the last occurrence. (Note that it may not be strung between the same left
 * and right end states, however!) This used to be important for the subRE
 * tree, although the important bits are now handled by the in-line code in
 * parse(), and when this is called, it doesn't matter any more.
 ^ static void repeat(struct vars *, struct state *, struct state *, int, int);
................................................................................
	    ERR(REG_ESPACE);
	    return NULL;
	}
	ret->chain = v->treechain;
	v->treechain = ret;
    }

    assert(strchr("|.b(=", op) != NULL);

    ret->op = op;
    ret->flags = flags;
    ret->retry = 0;
    ret->subno = 0;
    ret->min = ret->max = 1;
    ret->left = NULL;
    ret->right = NULL;
    ret->begin = begin;
    ret->end = end;
    ZAPCNFA(ret->cnfa);
................................................................................
    }

    if (!NULLCNFA(sr->cnfa)) {
	freecnfa(&sr->cnfa);
    }
    sr->flags = 0;

    if (v != NULL) {

	sr->left = v->treefree;
	v->treefree = sr;
    } else {
	FREE(sr);
    }
}
 
................................................................................
     * nothing with less effort.
     */

    return;
}
 
/*
 - numst - number tree nodes (assigning retry indexes)
 ^ static int numst(struct subre *, int);
 */
static int			/* next number */
numst(
    struct subre *t,
    int start)			/* starting point for subtree numbers */
{
    int i;

    assert(t != NULL);

    i = start;
    t->retry = (short) i++;
    if (t->left != NULL) {
	i = numst(t->left, i);
    }
    if (t->right != NULL) {
	i = numst(t->right, i);
    }
    return i;
}
 
/*
 - markst - mark tree nodes as INUSE













 ^ static void markst(struct subre *);
 */
static void
markst(
    struct subre *t)
{
    assert(t != NULL);
................................................................................
static int			/* lacon number */
newlacon(
    struct vars *v,
    struct state *begin,
    struct state *end,
    int pos)
{
    struct subre *sub;
    int n;



    if (v->nlacons == 0) {
	v->lacons = (struct subre *) MALLOC(2 * sizeof(struct subre));
	n = 1;		/* skip 0th */
	v->nlacons = 2;
    } else {

	v->lacons = (struct subre *) REALLOC(v->lacons,
		(v->nlacons+1)*sizeof(struct subre));
	n = v->nlacons++;
    }

    if (v->lacons == NULL) {
	ERR(REG_ESPACE);
	return 0;
    }



    sub = &v->lacons[n];
    sub->begin = begin;
    sub->end = end;
    sub->subno = pos;
    ZAPCNFA(sub->cnfa);
    return n;
}
................................................................................
	return;
    }

    re->re_magic = 0;	/* invalidate RE */
    g = (struct guts *) re->re_guts;
    re->re_guts = NULL;
    re->re_fns = NULL;

    g->magic = 0;
    freecm(&g->cmap);
    if (g->tree != NULL) {
	freesubre(NULL, g->tree);
    }
    if (g->lacons != NULL) {
	freelacons(g->lacons, g->nlacons);
    }
    if (!NULLCNFA(g->search)) {
	freecnfa(&g->search);
    }
    FREE(g);

}
 
/*
 - dump - dump an RE in human-readable form
 ^ static void dump(regex_t *, FILE *);
 */
static void
................................................................................
    if (g->magic != GUTSMAGIC) {
	fprintf(f, "bad guts magic number (0x%x not 0x%x)\n",
		g->magic, GUTSMAGIC);
    }

    fprintf(f, "\n\n\n========= DUMP ==========\n");
    fprintf(f, "nsub %d, info 0%lo, csize %d, ntree %d\n",
	    re->re_nsub, re->re_info, re->re_csize, g->ntree);

    dumpcolors(&g->cmap, f);
    if (!NULLCNFA(g->search)) {
	printf("\nsearch:\n");
	dumpcnfa(&g->search, f);
    }
    for (i = 1; i < g->nlacons; i++) {
................................................................................
static const char *			/* points to buf or constant string */
stid(
    struct subre *t,
    char *buf,
    size_t bufsize)
{
    /*
     * Big enough for hex int or decimal t->retry?
     */

    if (bufsize < sizeof(void*)*2 + 3 || bufsize < sizeof(t->retry)*3 + 1) {
	return "unable";
    }
    if (t->retry != 0) {
	sprintf(buf, "%d", t->retry);
    } else {
	sprintf(buf, "%p", t);
    }
    return buf;
}

#include "regc_lex.c"






<
<
<







 







|







 







|












|
|




|







 







|





>
>







 







<
>
|
|
|
>
>
|
<
<
>
>







 







|







 







>
>
|
<
<

|
>
>
>
>
>
>










<
|


<







 







|
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







 







>
>






|
>
>

>
|
<
>
>
>
>












>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>








|

|
|







 







>
>







 







|



|







 







|
>







 







|












|











>
>
>
>
>
>
>
>
>
>
>
>
>







 







<

>
>


<

|

>
|
|
<


|




>
>







 







>
|
|
|
|
|
|
|
|
|
|
|
|
>







 







|







 







|


|


|
|







79
80
81
82
83
84
85



86
87
88
89
90
91
92
...
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
...
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
...
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
...
588
589
590
591
592
593
594

595
596
597
598
599
600
601


602
603
604
605
606
607
608
609
610
...
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
....
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109


1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127

1128
1129
1130

1131
1132
1133
1134
1135
1136
1137
....
1170
1171
1172
1173
1174
1175
1176
1177
1178



















1179
1180
1181
1182
1183
1184
1185
....
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209

1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
....
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
....
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
....
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
....
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
....
1956
1957
1958
1959
1960
1961
1962

1963
1964
1965
1966
1967

1968
1969
1970
1971
1972
1973

1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
....
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
....
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
....
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
static void lexword(struct vars *);
static int next(struct vars *);
static int lexescape(struct vars *);
static int lexdigits(struct vars *, int, int, int);
static int brenext(struct vars *, pchr);
static void skip(struct vars *);
static chr newline(NOPARMS);



static chr chrnamed(struct vars *, const chr *, const chr *, pchr);
/* === regc_color.c === */
static void initcm(struct vars *, struct colormap *);
static void freecm(struct colormap *);
static void cmtreefree(struct colormap *, union tree *, int);
static color setcolor(struct colormap *, pchr, pcolor);
static color maxcolor(struct colormap *);
................................................................................
static void dumpstate(struct state *, FILE *);
static void dumparcs(struct state *, FILE *);
static int dumprarcs(struct arc *, struct state *, FILE *, int);
static void dumparc(struct arc *, struct state *, FILE *);
#endif
static void dumpcnfa(struct cnfa *, FILE *);
#ifdef REG_DEBUG
static void dumpcstate(int, struct cnfa *, FILE *);
#endif
/* === regc_cvec.c === */
static struct cvec *clearcvec(struct cvec *);
static void addchr(struct cvec *, pchr);
static void addrange(struct cvec *, pchr, pchr);
static struct cvec *newcvec(int, int);
static struct cvec *getcvec(struct vars *, int, int);
................................................................................
    struct nfa *nfa;		/* the NFA */
    struct colormap *cm;	/* character color map */
    color nlcolor;		/* color of newline */
    struct state *wordchrs;	/* state in nfa holding word-char outarcs */
    struct subre *tree;		/* subexpression tree */
    struct subre *treechain;	/* all tree nodes allocated */
    struct subre *treefree;	/* any free tree nodes */
    int ntree;			/* number of tree nodes, plus one */
    struct cvec *cv;		/* interface cvec */
    struct cvec *cv2;		/* utility cvec */
    struct subre *lacons;	/* lookahead-constraint vector */
    int nlacons;		/* size of lacons */
};

/* parsing macros; most know that `v' is the struct vars pointer */
#define	NEXT()	(next(v))		/* advance by one token */
#define	SEE(t)	(v->nexttype == (t))	/* is next token this? */
#define	EAT(t)	(SEE(t) && next(v))	/* if next is this, swallow it */
#define	VISERR(vv)	((vv)->err != 0)/* have we seen an error yet? */
#define	ISERR()	VISERR(v)
#define VERR(vv,e)	((vv)->nexttype = EOS, \
			 (vv)->err = ((vv)->err ? (vv)->err : (e)))
#define	ERR(e)	VERR(v, e)		/* record an error */
#define	NOERR()	{if (ISERR()) return;}	/* if error seen, return */
#define	NOERRN()	{if (ISERR()) return NULL;}	/* NOERR with retval */
#define	NOERRZ()	{if (ISERR()) return 0;}	/* NOERR with retval */
#define INSIST(c, e) do { if (!(c)) ERR(e); } while (0)	/* error if c false */
#define	NOTE(b)	(v->re->re_info |= (b))		/* note visible condition */
#define	EMPTYARC(x, y)	newarc(v->nfa, EMPTY, 0, x, y)

/* token type codes, some also used as NFA arc types */
#define	EMPTY	'n'		/* no token present */
#define	EOS	'e'		/* end of string */
#define	PLAIN	'p'		/* ordinary character */
................................................................................
#define	PREFER	'P'		/* length preference */

/* is an arc colored, and hence on a color chain? */
#define	COLORED(a) \
	((a)->type == PLAIN || (a)->type == AHEAD || (a)->type == BEHIND)

/* static function list */
static const struct fns functions = {
    rfree,			/* regfree insides */
};
 
/*
 - compile - compile regular expression
 * Note: on failure, no resources remain allocated, so regfree()
 * need not be applied to re.
 ^ int compile(regex_t *, const chr *, size_t, int);
 */
int
compile(
    regex_t *re,
    const chr *string,
    size_t len,
................................................................................
    for (a=pre->outs ; a!=NULL ; a=a->outchain) {
	s = a->to;
	for (b=s->ins ; b!=NULL ; b=b->inchain) {
	    if (b->from != pre) {
		break;
	    }
	}

 
	/*
	 * We want to mark states as being in the list already by having non
	 * NULL tmp fields, but we can't just store the old slist value in tmp
	 * because that doesn't work for the first such state.  Instead, the
	 * first list entry gets its own address in tmp.
	 */


	if (b != NULL && s->tmp == NULL) {
	    s->tmp = (slist != NULL) ? slist : s;
	    slist = s;
	}
    }

    /*
     * Do the splits.
     */
................................................................................
	    b = a->inchain;

	    if (a->from != pre) {
		cparc(nfa, a, a->from, s2);
		freearc(nfa, a);
	    }
	}
	s2 = (s->tmp != s) ? s->tmp : NULL;
	s->tmp = NULL;		/* clean up while we're at it */
    }
}
 
/*
 - parse - parse an RE
 * This is actually just the top level, which parses a bunch of branches tied
................................................................................
	atom = subre(v, '=', 0, lp, rp);
	NOERR();
    }

    /*
     * Prepare a general-purpose state skeleton.
     *
     * In the no-backrefs case, we want this:
     *
     * [lp] ---> [s] ---prefix---> [begin] ---atom---> [end] ---rest---> [rp]


     *
     * where prefix is some repetitions of atom.  In the general case we need
     *
     * [lp] ---> [s] ---iterator---> [s2] ---rest---> [rp]
     *
     * where the iterator wraps around [begin] ---atom---> [end]
     *
     * We make the s state here for both cases; s2 is made below if needed
     */

    s = newstate(v->nfa);	/* first, new endpoints for the atom */
    s2 = newstate(v->nfa);
    NOERR();
    moveouts(v->nfa, lp, s);
    moveins(v->nfa, rp, s2);
    NOERR();
    atom->begin = s;
    atom->end = s2;

    s = newstate(v->nfa);	/* set up starting state */
    NOERR();
    EMPTYARC(lp, s);

    NOERR();

    /*
     * Break remaining subRE into x{...} and what follows.
     */

    t = subre(v, '.', COMBINE(qprefer, atom->flags), lp, rp);
................................................................................

	dupnfa(v->nfa, v->subs[subno]->begin, v->subs[subno]->end,
		atom->begin, atom->end);
	NOERR();
    }

    /*
     * It's quantifier time.  If the atom is just a backref, we'll let it deal
     * with quantifiers internally.



















     */

    if (atomtype == BACKREF) {
	/*
	 * Special case: backrefs have internal quantifiers.
	 */

................................................................................
	 * Just stuff everything into atom.
	 */

	repeat(v, atom->begin, atom->end, m, n);
	atom->min = (short) m;
	atom->max = (short) n;
	atom->flags |= COMBINE(qprefer, atom->flags);
	/* rest of branch can be strung starting from atom->end */
	s2 = atom->end;
    } else if (m == 1 && n == 1) {
	/*
	 * No/vacuous quantifier: done.
	 */

	EMPTYARC(s, atom->begin);	/* empty prefix */
	/* rest of branch can be strung starting from atom->end */
	s2 = atom->end;
    } else if (m > 0 && !(atom->flags & BACKR)) {
	/*
	 * If there's no backrefs involved, we can turn x{m,n} into
	 * x{m-1,n-1}x, with capturing parens in only the second x.  This

	 * is valid because we only care about capturing matches from the
	 * final iteration of the quantifier.  It's a win because we can
	 * implement the backref-free left side as a plain DFA node, since
	 * we don't really care where its submatches are.
	 */

	dupnfa(v->nfa, atom->begin, atom->end, s, atom->begin);
	assert(m >= 1 && m != DUPINF && n >= 1);
	repeat(v, s, atom->begin, m-1, (n == DUPINF) ? n : n-1);
	f = COMBINE(qprefer, atom->flags);
	t = subre(v, '.', f, s, atom->end);	/* prefix and atom */
	NOERR();
	t->left = subre(v, '=', PREF(f), s, atom->begin);
	NOERR();
	t->right = atom;
	*atomp = t;
	/* rest of branch can be strung starting from atom->end */
	s2 = atom->end;
    } else {
	/* general case: need an iteration node */
	s2 = newstate(v->nfa);
	NOERR();
	moveouts(v->nfa, atom->end, s2);
	NOERR();
	dupnfa(v->nfa, atom->begin, atom->end, s, s2);
	repeat(v, s, s2, m, n);
	f = COMBINE(qprefer, atom->flags);
	t = subre(v, '*', f, s, s2);
	NOERR();
	t->min = (short) m;
	t->max = (short) n;
	t->left = atom;
	*atomp = t;
	/* rest of branch is to be strung from iteration's end state */
    }

    /*
     * And finally, look after that postponed recursion.
     */

    t = top->right;
    if (!(SEE('|') || SEE(stopper) || SEE(EOS))) {
	t->right = parsebranch(v, stopper, type, s2, rp, 1);
    } else {
	EMPTYARC(s2, rp);
	t->right = subre(v, '=', 0, s2, rp);
    }
    NOERR();
    assert(SEE('|') || SEE(stopper) || SEE(EOS));
    t->flags |= COMBINE(t->flags, t->right->flags);
    top->flags |= COMBINE(top->flags, t->flags);
}
 
................................................................................
	return 0;
    }
    return n;
}
 
/*
 - repeat - replicate subNFA for quantifiers
 * The sub-NFA strung from lp to rp is modified to represent m to n
 * repetitions of its initial contents.
 * The duplication sequences used here are chosen carefully so that any
 * pointers starting out pointing into the subexpression end up pointing into
 * the last occurrence. (Note that it may not be strung between the same left
 * and right end states, however!) This used to be important for the subRE
 * tree, although the important bits are now handled by the in-line code in
 * parse(), and when this is called, it doesn't matter any more.
 ^ static void repeat(struct vars *, struct state *, struct state *, int, int);
................................................................................
	    ERR(REG_ESPACE);
	    return NULL;
	}
	ret->chain = v->treechain;
	v->treechain = ret;
    }

    assert(strchr("=b|.*(", op) != NULL);

    ret->op = op;
    ret->flags = flags;
    ret->id = 0;		/* will be assigned later */
    ret->subno = 0;
    ret->min = ret->max = 1;
    ret->left = NULL;
    ret->right = NULL;
    ret->begin = begin;
    ret->end = end;
    ZAPCNFA(ret->cnfa);
................................................................................
    }

    if (!NULLCNFA(sr->cnfa)) {
	freecnfa(&sr->cnfa);
    }
    sr->flags = 0;

    if (v != NULL && v->treechain != NULL) {
	/* we're still parsing, maybe we can reuse the subre */
	sr->left = v->treefree;
	v->treefree = sr;
    } else {
	FREE(sr);
    }
}
 
................................................................................
     * nothing with less effort.
     */

    return;
}
 
/*
 - numst - number tree nodes (assigning "id" indexes)
 ^ static int numst(struct subre *, int);
 */
static int			/* next number */
numst(
    struct subre *t,
    int start)			/* starting point for subtree numbers */
{
    int i;

    assert(t != NULL);

    i = start;
    t->id = (short) i++;
    if (t->left != NULL) {
	i = numst(t->left, i);
    }
    if (t->right != NULL) {
	i = numst(t->right, i);
    }
    return i;
}
 
/*
 - markst - mark tree nodes as INUSE
 * Note: this is a great deal more subtle than it looks.  During initial
 * parsing of a regex, all subres are linked into the treechain list;
 * discarded ones are also linked into the treefree list for possible reuse.
 * After we are done creating all subres required for a regex, we run markst()
 * then cleanst(), which results in discarding all subres not reachable from
 * v->tree.  We then clear v->treechain, indicating that subres must be found
 * by descending from v->tree.  This changes the behavior of freesubre(): it
 * will henceforth FREE() unwanted subres rather than sticking them into the
 * treefree list.  (Doing that any earlier would result in dangling links in
 * the treechain list.)  This all means that freev() will clean up correctly
 * if invoked before or after markst()+cleanst(); but it would not work if
 * called partway through this state conversion, so we mustn't error out
 * in or between these two functions.
 ^ static void markst(struct subre *);
 */
static void
markst(
    struct subre *t)
{
    assert(t != NULL);
................................................................................
static int			/* lacon number */
newlacon(
    struct vars *v,
    struct state *begin,
    struct state *end,
    int pos)
{

    int n;
    struct subre *newlacons;
    struct subre *sub;

    if (v->nlacons == 0) {

	n = 1;		/* skip 0th */
	newlacons = (struct subre *) MALLOC(2 * sizeof(struct subre));
    } else {
	n = v->nlacons;
	newlacons = (struct subre *) REALLOC(v->lacons,
					     (n + 1) * sizeof(struct subre));

    }

    if (newlacons == NULL) {
	ERR(REG_ESPACE);
	return 0;
    }

    v->lacons = newlacons;
    v->nlacons = n + 1;
    sub = &v->lacons[n];
    sub->begin = begin;
    sub->end = end;
    sub->subno = pos;
    ZAPCNFA(sub->cnfa);
    return n;
}
................................................................................
	return;
    }

    re->re_magic = 0;	/* invalidate RE */
    g = (struct guts *) re->re_guts;
    re->re_guts = NULL;
    re->re_fns = NULL;
    if (g != NULL) {
	g->magic = 0;
	freecm(&g->cmap);
	if (g->tree != NULL) {
	    freesubre(NULL, g->tree);
	}
	if (g->lacons != NULL) {
	    freelacons(g->lacons, g->nlacons);
	}
	if (!NULLCNFA(g->search)) {
	    freecnfa(&g->search);
	}
	FREE(g);
    }
}
 
/*
 - dump - dump an RE in human-readable form
 ^ static void dump(regex_t *, FILE *);
 */
static void
................................................................................
    if (g->magic != GUTSMAGIC) {
	fprintf(f, "bad guts magic number (0x%x not 0x%x)\n",
		g->magic, GUTSMAGIC);
    }

    fprintf(f, "\n\n\n========= DUMP ==========\n");
    fprintf(f, "nsub %d, info 0%lo, csize %d, ntree %d\n",
	    (int) re->re_nsub, re->re_info, re->re_csize, g->ntree);

    dumpcolors(&g->cmap, f);
    if (!NULLCNFA(g->search)) {
	printf("\nsearch:\n");
	dumpcnfa(&g->search, f);
    }
    for (i = 1; i < g->nlacons; i++) {
................................................................................
static const char *			/* points to buf or constant string */
stid(
    struct subre *t,
    char *buf,
    size_t bufsize)
{
    /*
     * Big enough for hex int or decimal t->id?
     */

    if (bufsize < sizeof(void*)*2 + 3 || bufsize < sizeof(t->id)*3 + 1) {
	return "unable";
    }
    if (t->id != 0) {
	sprintf(buf, "%d", t->id);
    } else {
	sprintf(buf, "%p", t);
    }
    return buf;
}

#include "regc_lex.c"

Changes to generic/rege_dfa.c.

80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
...
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
...
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
...
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
...
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
...
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
...
590
591
592
593
594
595
596
597

598
599
600
601
602
603
604
...
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
...
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
...
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
    /*
     * Main loop.
     */

    if (v->eflags&REG_FTRACE) {
	while (cp < realstop) {
	    FDEBUG(("+++ at c%d +++\n", css - d->ssets));
	    co = GETCOLOR(cm, *cp);
	    FDEBUG(("char %c, color %ld\n", (char)*cp, (long)co));
	    ss = css->outs[co];
	    if (ss == NULL) {
		ss = miss(v, d, css, co, cp+1, start);
		if (ss == NULL) {
		    break;	/* NOTE BREAK OUT */
................................................................................
	}
    }

    /*
     * Shutdown.
     */

    FDEBUG(("+++ shutdown at c%d +++\n", css - d->ssets));
    if (cp == v->stop && stop == v->stop) {
	if (hitstopp != NULL) {
	    *hitstopp = 1;
	}
	co = d->cnfa->eos[(v->eflags&REG_NOTEOL) ? 0 : 1];
	FDEBUG(("color %ld\n", (long)co));
	ss = miss(v, d, css, co, cp, start);
................................................................................

    /*
     * Main loop.
     */

    if (v->eflags&REG_FTRACE) {
	while (cp < realmax) {
	    FDEBUG(("--- at c%d ---\n", css - d->ssets));
	    co = GETCOLOR(cm, *cp);
	    FDEBUG(("char %c, color %ld\n", (char)*cp, (long)co));
	    ss = css->outs[co];
	    if (ss == NULL) {
		ss = miss(v, d, css, co, cp+1, start);
		if (ss == NULL) {
		    break;	/* NOTE BREAK OUT */
................................................................................
	d->work[i] = 0;
    }
    isPost = 0;
    noProgress = 1;
    gotState = 0;
    for (i = 0; i < d->nstates; i++) {
	if (ISBSET(css->states, i)) {
	    for (ca = cnfa->states[i]+1; ca->co != COLORLESS; ca++) {
		if (ca->co == co) {
		    BSET(d->work, ca->to);
		    gotState = 1;
		    if (ca->to == cnfa->post) {
			isPost = 1;
		    }
		    if (!cnfa->states[ca->to]->co) {
			noProgress = 0;
		    }
		    FDEBUG(("%d -> %d\n", i, ca->to));
		}
	    }
	}
    }
    doLAConstraints = (gotState ? (cnfa->flags&HASLACONS) : 0);
    sawLAConstraints = 0;
    while (doLAConstraints) {		/* transitive closure */
	doLAConstraints = 0;
	for (i = 0; i < d->nstates; i++) {
	    if (ISBSET(d->work, i)) {
		for (ca = cnfa->states[i]+1; ca->co != COLORLESS; ca++) {
		    if (ca->co <= cnfa->ncolors) {
			continue;	/* NOTE CONTINUE */
		    }
		    sawLAConstraints = 1;
		    if (ISBSET(d->work, ca->to)) {
			continue;	/* NOTE CONTINUE */
		    }
		    if (!checkLAConstraint(v, cnfa, cp, ca->co)) {
................................................................................
			continue;	/* NOTE CONTINUE */
		    }
		    BSET(d->work, ca->to);
		    doLAConstraints = 1;
		    if (ca->to == cnfa->post) {
			isPost = 1;
		    }
		    if (!cnfa->states[ca->to]->co) {
			noProgress = 0;
		    }
		    FDEBUG(("%d :> %d\n", i, ca->to));
		}
	    }
	}
    }
................................................................................

    /*
     * Next, is that in the cache?
     */

    for (p = d->ssets, i = d->nssused; i > 0; p++, i--) {
	 if (HIT(h, d->work, p, d->wordsper)) {
	     FDEBUG(("cached c%d\n", p - d->ssets));
	     break;			/* NOTE BREAK OUT */
	 }
    }
    if (i == 0) {		/* nope, need a new cache entry */
	p = getVacantSS(v, d, cp, start);
	assert(p != css);
	for (i = 0; i < d->wordsper; i++) {
................................................................................

	/*
	 * lastseen to be dealt with by caller
	 */
    }

    if (!sawLAConstraints) {	/* lookahead conds. always cache miss */
	FDEBUG(("c%d[%d]->c%d\n", css - d->ssets, co, p - d->ssets));

	css->outs[co] = p;
	css->inchain[co] = p->ins;
	p->ins.ss = css;
	p->ins.co = (color) co;
    }
    return p;
}
................................................................................
    /*
     * Clear out its inarcs, including self-referential ones.
     */

    ap = ss->ins;
    while ((p = ap.ss) != NULL) {
	co = ap.co;
	FDEBUG(("zapping c%d's %ld outarc\n", p - d->ssets, (long)co));
	p->outs[co] = NULL;
	ap = p->inchain[co];
	p->inchain[co].ss = NULL; /* paranoia */
    }
    ss->ins.ss = NULL;

    /*
................................................................................

    for (i = 0; i < d->ncolors; i++) {
	p = ss->outs[i];
	assert(p != ss);	/* not self-referential */
	if (p == NULL) {
	    continue;		/* NOTE CONTINUE */
	}
	FDEBUG(("del outarc %d from c%d's in chn\n", i, p - d->ssets));
	if (p->ins.ss == ss && p->ins.co == i) {
	    p->ins = ss->inchain[i];
	} else {
	    assert(p->ins.ss != NULL);
	    for (ap = p->ins; ap.ss != NULL && !(ap.ss == ss && ap.co == i);
		    ap = ap.ss->inchain[ap.co]) {
		lastap = ap;
................................................................................
    } else {
	ancient = start;
    }
    for (ss = d->search, end = &d->ssets[d->nssets]; ss < end; ss++) {
	if ((ss->lastseen == NULL || ss->lastseen < ancient)
		&& !(ss->flags&LOCKED)) {
	    d->search = ss + 1;
	    FDEBUG(("replacing c%d\n", ss - d->ssets));
	    return ss;
	}
    }
    for (ss = d->ssets, end = d->search; ss < end; ss++) {
	if ((ss->lastseen == NULL || ss->lastseen < ancient)
		&& !(ss->flags&LOCKED)) {
	    d->search = ss + 1;
	    FDEBUG(("replacing c%d\n", ss - d->ssets));
	    return ss;
	}
    }

    /*
     * Nobody's old enough?!? -- something's really wrong.
     */






|







 







|







 







|







 







|






|













|
|







 







|







 







|







 







|
>







 







|







 







|







 







|







|







80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
...
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
...
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
...
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
...
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
...
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
...
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
...
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
...
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
...
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
    /*
     * Main loop.
     */

    if (v->eflags&REG_FTRACE) {
	while (cp < realstop) {
	    FDEBUG(("+++ at c%d +++\n", (int) (css - d->ssets)));
	    co = GETCOLOR(cm, *cp);
	    FDEBUG(("char %c, color %ld\n", (char)*cp, (long)co));
	    ss = css->outs[co];
	    if (ss == NULL) {
		ss = miss(v, d, css, co, cp+1, start);
		if (ss == NULL) {
		    break;	/* NOTE BREAK OUT */
................................................................................
	}
    }

    /*
     * Shutdown.
     */

    FDEBUG(("+++ shutdown at c%d +++\n", (int) (css - d->ssets)));
    if (cp == v->stop && stop == v->stop) {
	if (hitstopp != NULL) {
	    *hitstopp = 1;
	}
	co = d->cnfa->eos[(v->eflags&REG_NOTEOL) ? 0 : 1];
	FDEBUG(("color %ld\n", (long)co));
	ss = miss(v, d, css, co, cp, start);
................................................................................

    /*
     * Main loop.
     */

    if (v->eflags&REG_FTRACE) {
	while (cp < realmax) {
	    FDEBUG(("--- at c%d ---\n", (int) (css - d->ssets)));
	    co = GETCOLOR(cm, *cp);
	    FDEBUG(("char %c, color %ld\n", (char)*cp, (long)co));
	    ss = css->outs[co];
	    if (ss == NULL) {
		ss = miss(v, d, css, co, cp+1, start);
		if (ss == NULL) {
		    break;	/* NOTE BREAK OUT */
................................................................................
	d->work[i] = 0;
    }
    isPost = 0;
    noProgress = 1;
    gotState = 0;
    for (i = 0; i < d->nstates; i++) {
	if (ISBSET(css->states, i)) {
	    for (ca = cnfa->states[i]; ca->co != COLORLESS; ca++) {
		if (ca->co == co) {
		    BSET(d->work, ca->to);
		    gotState = 1;
		    if (ca->to == cnfa->post) {
			isPost = 1;
		    }
		    if (!(cnfa->stflags[ca->to] & CNFA_NOPROGRESS)) {
			noProgress = 0;
		    }
		    FDEBUG(("%d -> %d\n", i, ca->to));
		}
	    }
	}
    }
    doLAConstraints = (gotState ? (cnfa->flags&HASLACONS) : 0);
    sawLAConstraints = 0;
    while (doLAConstraints) {		/* transitive closure */
	doLAConstraints = 0;
	for (i = 0; i < d->nstates; i++) {
	    if (ISBSET(d->work, i)) {
		for (ca = cnfa->states[i]; ca->co != COLORLESS; ca++) {
		    if (ca->co < cnfa->ncolors) {
			continue;	/* NOTE CONTINUE */
		    }
		    sawLAConstraints = 1;
		    if (ISBSET(d->work, ca->to)) {
			continue;	/* NOTE CONTINUE */
		    }
		    if (!checkLAConstraint(v, cnfa, cp, ca->co)) {
................................................................................
			continue;	/* NOTE CONTINUE */
		    }
		    BSET(d->work, ca->to);
		    doLAConstraints = 1;
		    if (ca->to == cnfa->post) {
			isPost = 1;
		    }
		    if (!(cnfa->stflags[ca->to] & CNFA_NOPROGRESS)) {
			noProgress = 0;
		    }
		    FDEBUG(("%d :> %d\n", i, ca->to));
		}
	    }
	}
    }
................................................................................

    /*
     * Next, is that in the cache?
     */

    for (p = d->ssets, i = d->nssused; i > 0; p++, i--) {
	 if (HIT(h, d->work, p, d->wordsper)) {
	     FDEBUG(("cached c%d\n", (int) (p - d->ssets)));
	     break;			/* NOTE BREAK OUT */
	 }
    }
    if (i == 0) {		/* nope, need a new cache entry */
	p = getVacantSS(v, d, cp, start);
	assert(p != css);
	for (i = 0; i < d->wordsper; i++) {
................................................................................

	/*
	 * lastseen to be dealt with by caller
	 */
    }

    if (!sawLAConstraints) {	/* lookahead conds. always cache miss */
	FDEBUG(("c%d[%d]->c%d\n",
		(int) (css - d->ssets), co, (int) (p - d->ssets)));
	css->outs[co] = p;
	css->inchain[co] = p->ins;
	p->ins.ss = css;
	p->ins.co = (color) co;
    }
    return p;
}
................................................................................
    /*
     * Clear out its inarcs, including self-referential ones.
     */

    ap = ss->ins;
    while ((p = ap.ss) != NULL) {
	co = ap.co;
	FDEBUG(("zapping c%d's %ld outarc\n", (int) (p - d->ssets), (long)co));
	p->outs[co] = NULL;
	ap = p->inchain[co];
	p->inchain[co].ss = NULL; /* paranoia */
    }
    ss->ins.ss = NULL;

    /*
................................................................................

    for (i = 0; i < d->ncolors; i++) {
	p = ss->outs[i];
	assert(p != ss);	/* not self-referential */
	if (p == NULL) {
	    continue;		/* NOTE CONTINUE */
	}
	FDEBUG(("del outarc %d from c%d's in chn\n", i, (int) (p - d->ssets)));
	if (p->ins.ss == ss && p->ins.co == i) {
	    p->ins = ss->inchain[i];
	} else {
	    assert(p->ins.ss != NULL);
	    for (ap = p->ins; ap.ss != NULL && !(ap.ss == ss && ap.co == i);
		    ap = ap.ss->inchain[ap.co]) {
		lastap = ap;
................................................................................
    } else {
	ancient = start;
    }
    for (ss = d->search, end = &d->ssets[d->nssets]; ss < end; ss++) {
	if ((ss->lastseen == NULL || ss->lastseen < ancient)
		&& !(ss->flags&LOCKED)) {
	    d->search = ss + 1;
	    FDEBUG(("replacing c%d\n", (int) (ss - d->ssets)));
	    return ss;
	}
    }
    for (ss = d->ssets, end = d->search; ss < end; ss++) {
	if ((ss->lastseen == NULL || ss->lastseen < ancient)
		&& !(ss->flags&LOCKED)) {
	    d->search = ss + 1;
	    FDEBUG(("replacing c%d\n", (int) (ss - d->ssets)));
	    return ss;
	}
    }

    /*
     * Nobody's old enough?!? -- something's really wrong.
     */

Changes to generic/regerror.c.

37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
..
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
static const char unk[] = "*** unknown regex error code 0x%x ***";

/*
 * Struct to map among codes, code names, and explanations.
 */

static struct rerr {
    int code;
    const char *name;
    const char *explain;
} rerrs[] = {
    /* The actual table is built from regex.h */
#include "regerrs.h"
    { -1, "", "oops" },		/* explanation special-cased in code */
................................................................................
size_t				/* Actual space needed (including NUL) */
regerror(
    int code,			/* Error code, or REG_ATOI or REG_ITOA */
    const regex_t *preg,	/* Associated regex_t (unused at present) */
    char *errbuf,		/* Result buffer (unless errbuf_size==0) */
    size_t errbuf_size)		/* Available space in errbuf, can be 0 */
{
    struct rerr *r;
    const char *msg;
    char convbuf[sizeof(unk)+50]; /* 50 = plenty for int */
    size_t len;
    int icode;

    switch (code) {
    case REG_ATOI:		/* Convert name to number */






|







 







|







37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
..
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
static const char unk[] = "*** unknown regex error code 0x%x ***";

/*
 * Struct to map among codes, code names, and explanations.
 */

static const struct rerr {
    int code;
    const char *name;
    const char *explain;
} rerrs[] = {
    /* The actual table is built from regex.h */
#include "regerrs.h"
    { -1, "", "oops" },		/* explanation special-cased in code */
................................................................................
size_t				/* Actual space needed (including NUL) */
regerror(
    int code,			/* Error code, or REG_ATOI or REG_ITOA */
    const regex_t *preg,	/* Associated regex_t (unused at present) */
    char *errbuf,		/* Result buffer (unless errbuf_size==0) */
    size_t errbuf_size)		/* Available space in errbuf, can be 0 */
{
    const struct rerr *r;
    const char *msg;
    char convbuf[sizeof(unk)+50]; /* 50 = plenty for int */
    size_t len;
    int icode;

    switch (code) {
    case REG_ATOI:		/* Convert name to number */

Changes to generic/regexec.c.

103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
...
170
171
172
173
174
175
176

177
178
179
180

181
182
183
184
185
186
187
...
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246

247
248
249

250
251
252
253
254
255
256
257

258
259
260
261
262
263
264
265
266
...
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290


291


292
293
294

















295
296
297
298
299
300
301
...
353
354
355
356
357
358
359
360



361
362
363
364
365
366
367
...
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
...
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503

504
505
506
507
508
509
510
...
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
...
590
591
592
593
594
595
596
597










598
599
600
601
602
603
604
605
606
607
608
609


610
611
612
613
614
615
616
617

618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
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
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792


793
794
795
796


797

798
799
800

801

802
803
804


805


806
807

808
809






810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829

830
831
832
833

834
835
836
837
838
839
840
841
842
843
844

845
846
847
848
849
850
851
852
853
854

855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951

952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969

970
971
972
973

974
975
976
977
978

979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075



1076
1077
1078
1079
1080
1081
1082
1083

1084
1085
1086
1087
1088
1089


1090
1091


1092



1093
1094
1095
1096
1097





1098



1099
1100


1101
1102
1103
1104

















1105
1106



































1107





































1108
1109
1110
1111






1112









1113
1114
1115



1116
1117
1118

1119
1120
1121







1122
1123

1124
1125
1126
1127


1128





























1129


1130
1131
1132
1133
1134




1135


1136
1137









1138




1139
1140





1141
1142



























1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157






1158
1159
1160
1161


1162
1163
1164
1165
1166



1167
1168
1169








1170

1171
1172
1173
1174
1175





1176
1177
1178












1179
1180
1181
1182

1183

1184
1185
1186
1187
1188
1189

1190
1191
1192
1193









1194




1195





















































1196




1197



1198
1199
1200
1201
1202
1203
1204
1205
1206
1207




























1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
    int eflags;			/* copies of arguments */
    size_t nmatch;
    regmatch_t *pmatch;
    rm_detail_t *details;
    chr *start;			/* start of string */
    chr *stop;			/* just past end of string */
    int err;			/* error code if any (0 none) */
    regoff_t *mem;		/* memory vector for backtracking */
    struct smalldfa dfa1;
    struct smalldfa dfa2;
};
#define	VISERR(vv) ((vv)->err != 0)	/* have we seen an error yet? */
#define	ISERR()	VISERR(v)
#define	VERR(vv,e) (((vv)->err) ? (vv)->err : ((vv)->err = (e)))
#define	ERR(e)	VERR(v, e)	/* record an error */
#define	NOERR()	{if (ISERR()) return v->err;}	/* if error seen, return it */
#define	OFF(p)	((p) - v->start)
#define	LOFF(p)	((long)OFF(p))
 
/*
 * forward declarations
 */
/* =====^!^===== begin forwards =====^!^===== */
/* automatically gathered by fwd; do not hand-edit */
/* === regexec.c === */
int exec(regex_t *, const chr *, size_t, rm_detail_t *, size_t, regmatch_t [], int);

static int simpleFind(struct vars *const, struct cnfa *const, struct colormap *const);
static int complicatedFind(struct vars *const, struct cnfa *const, struct colormap *const);
static int complicatedFindLoop(struct vars *const, struct cnfa *const, struct colormap *const, struct dfa *const, struct dfa *const, chr **const);
static void zapSubexpressions(regmatch_t *const, const size_t);
static void zapSubtree(struct vars *const, struct subre *const);
static void subset(struct vars *const, struct subre *const, chr *const, chr *const);
static int dissect(struct vars *const, struct subre *, chr *const, chr *const);
static int concatenationDissect(struct vars *const, struct subre *const, chr *const, chr *const);
static int alternationDissect(struct vars *const, struct subre *, chr *const, chr *const);
static inline int complicatedDissect(struct vars *const, struct subre *const, chr *const, chr *const);
static int complicatedCapturingDissect(struct vars *const, struct subre *const, chr *const, chr *const);
static int complicatedConcatenationDissect(struct vars *const, struct subre *const, chr *const, chr *const);
static int complicatedReversedDissect(struct vars *const, struct subre *const, chr *const, chr *const);
static int complicatedBackrefDissect(struct vars *const, struct subre *const, chr *const, chr *const);
static int complicatedAlternationDissect(struct vars *const, struct subre *, chr *const, chr *const);
/* === rege_dfa.c === */
static chr *longest(struct vars *const, struct dfa *const, chr *const, chr *const, int *const);
static chr *shortest(struct vars *const, struct dfa *const, chr *const, chr *const, chr *const, chr **const, int *const);
static chr *lastCold(struct vars *const, struct dfa *const);
static struct dfa *newDFA(struct vars *const, struct cnfa *const, struct colormap *const, struct smalldfa *);
static void freeDFA(struct dfa *const);
static unsigned hash(unsigned *const, const int);
................................................................................
    size_t nmatch,
    regmatch_t pmatch[],
    int flags)
{
    AllocVars(v);
    int st, backref;
    size_t n;

#define	LOCALMAT	20
    regmatch_t mat[LOCALMAT];
#define	LOCALMEM	40
    regoff_t mem[LOCALMEM];


    /*
     * Sanity checks.
     */

    if (re == NULL || string == NULL || re->re_magic != REMAGIC) {
	FreeVars(v);
................................................................................
    } else {
	v->pmatch = pmatch;
    }
    v->details = details;
    v->start = (chr *)string;
    v->stop = (chr *)string + len;
    v->err = 0;
    if (backref) {
	/*
	 * Need retry memory.
	 */

	assert(v->g->ntree >= 0);
	n = (size_t)v->g->ntree;
	if (n <= LOCALMEM) {
	    v->mem = mem;

	} else {
	    v->mem = (regoff_t *) MALLOC(n*sizeof(regoff_t));
	}

	if (v->mem == NULL) {
	    if (v->pmatch != pmatch && v->pmatch != mat) {
		FREE(v->pmatch);
	    }
	    FreeVars(v);
	    return REG_ESPACE;
	}
    } else {

	v->mem = NULL;
    }

    /*
     * Do it.
     */

    assert(v->g->tree != NULL);
    if (backref) {
................................................................................
    }

    /*
     * Copy (portion of) match vector over if necessary.
     */

    if (st == REG_OKAY && v->pmatch != pmatch && nmatch > 0) {
	zapSubexpressions(pmatch, nmatch);
	n = (nmatch < v->nmatch) ? nmatch : v->nmatch;
	memcpy(VS(pmatch), VS(v->pmatch), n*sizeof(regmatch_t));
    }

    /*
     * Clean up.
     */

    if (v->pmatch != pmatch && v->pmatch != mat) {
	FREE(v->pmatch);
    }
    if (v->mem != NULL && v->mem != mem) {
	FREE(v->mem);


    }


    FreeVars(v);
    return st;
}

















 
/*
 - simpleFind - find a match for the main NFA (no-complications case)
 ^ static int simpleFind(struct vars *, struct cnfa *, struct colormap *);
 */
static int
simpleFind(
................................................................................
    for (begin = open; begin <= close; begin++) {
	MDEBUG(("\nfind trying at %ld\n", LOFF(begin)));
	if (shorter) {
	    end = shortest(v, d, begin, begin, v->stop, NULL, &hitend);
	} else {
	    end = longest(v, d, begin, v->stop, &hitend);
	}
	NOERR();



	if (hitend && cold == NULL) {
	    cold = begin;
	}
	if (end != NULL) {
	    break;		/* NOTE BREAK OUT */
	}
    }
................................................................................
	v->details->rm_extend.rm_eo = OFF(v->stop);	/* unknown */
    }
    if (v->nmatch == 1) {	/* no need for submatches */
	return REG_OKAY;
    }

    /*
     * Submatches.
     */

    zapSubexpressions(v->pmatch, v->nmatch);
    return dissect(v, v->g->tree, begin, end);
}
 
/*
 - complicatedFind - find a match for the main NFA (with complications)
 ^ static int complicatedFind(struct vars *, struct cnfa *, struct colormap *);
 */
static int
................................................................................
		    cold = begin;
		}
		if (end == NULL) {
		    break;	/* NOTE BREAK OUT */
		}

		MDEBUG(("tentative end %ld\n", LOFF(end)));
		zapSubexpressions(v->pmatch, v->nmatch);
		zapSubtree(v, v->g->tree);
		er = complicatedDissect(v, v->g->tree, begin, end);
		if (er == REG_OKAY) {
		    if (v->nmatch > 0) {
			v->pmatch[0].rm_so = OFF(begin);
			v->pmatch[0].rm_eo = OFF(end);
		    }
		    *coldp = cold;
		    return REG_OKAY;
		}
		if (er != REG_NOMATCH) {
		    ERR(er);

		    return er;
		}
		if ((shorter) ? end == estop : end == begin) {
		    break;
		}

		/*
................................................................................
    } while (close < v->stop);

    *coldp = cold;
    return REG_NOMATCH;
}
 
/*
 - zapSubexpressions - initialize the subexpression matches to "no match"
 ^ static void zapSubexpressions(regmatch_t *, size_t);
 */
static void
zapSubexpressions(
    regmatch_t *const p,
    const size_t n)
{
    size_t i;

    for (i = n-1; i > 0; i--) {
	p[i].rm_so = -1;
	p[i].rm_eo = -1;
    }
}
 
/*
 - zapSubtree - initialize the retry memory of a subtree to zeros
 ^ static void zapSubtree(struct vars *, struct subre *);
 */
static void
zapSubtree(
    struct vars *const v,
    struct subre *const t)
{
    if (t == NULL) {
	return;
    }

    assert(v->mem != NULL);
    v->mem[t->retry] = 0;
    if (t->op == '(') {
	assert(t->subno > 0);
	v->pmatch[t->subno].rm_so = -1;
	v->pmatch[t->subno].rm_eo = -1;
    }

    if (t->left != NULL) {
	zapSubtree(v, t->left);
    }
    if (t->right != NULL) {
	zapSubtree(v, t->right);
    }
}
 
/*
 - subset - set any subexpression relevant to a successful subre
 ^ static void subset(struct vars *, struct subre *, chr *, chr *);
 */
static void
subset(
    struct vars *const v,
    struct subre *const sub,
    chr *const begin,
................................................................................

    MDEBUG(("setting %d\n", n));
    v->pmatch[n].rm_so = OFF(begin);
    v->pmatch[n].rm_eo = OFF(end);
}
 
/*
 - dissect - determine subexpression matches (uncomplicated case)










 ^ static int dissect(struct vars *, struct subre *, chr *, chr *);
 */
static int			/* regexec return code */
dissect(
    struct vars *const v,
    struct subre *t,
    chr *const begin,		/* beginning of relevant substring */
    chr *const end)		/* end of same */
{
#ifndef COMPILER_DOES_TAILCALL_OPTIMIZATION
  restart:
#endif


    assert(t != NULL);
    MDEBUG(("dissect %ld-%ld\n", LOFF(begin), LOFF(end)));

    switch (t->op) {
    case '=':			/* terminal node */
	assert(t->left == NULL && t->right == NULL);
	return REG_OKAY;	/* no action, parent did the work */
    case '|':			/* alternation */

	assert(t->left != NULL);
	return alternationDissect(v, t, begin, end);
    case 'b':			/* back ref -- shouldn't be calling us! */
	return REG_ASSERT;
    case '.':			/* concatenation */
	assert(t->left != NULL && t->right != NULL);
	return concatenationDissect(v, t, begin, end);
    case '(':			/* capturing */
	assert(t->left != NULL && t->right == NULL);
	assert(t->subno > 0);
	subset(v, t, begin, end);
#ifndef COMPILER_DOES_TAILCALL_OPTIMIZATION
	t = t->left;
	goto restart;
#else
	return dissect(v, t->left, begin, end);
#endif
    default:
	return REG_ASSERT;
    }
}
 
/*
 - concatenationDissect - determine concatenation subexpression matches
 - (uncomplicated)
 ^ static int concatenationDissect(struct vars *, struct subre *, chr *, chr *);
 */
static int			/* regexec return code */
concatenationDissect(
    struct vars *const v,
    struct subre *const t,
    chr *const begin,		/* beginning of relevant substring */
    chr *const end)		/* end of same */
{
    struct dfa *d, *d2;
    chr *mid;
    int i;
    int shorter = (t->left->flags&SHORTER) ? 1 : 0;
    chr *stop = (shorter) ? end : begin;

    assert(t->op == '.');
    assert(t->left != NULL && t->left->cnfa.nstates > 0);
    assert(t->right != NULL && t->right->cnfa.nstates > 0);

    d = newDFA(v, &t->left->cnfa, &v->g->cmap, &v->dfa1);
    NOERR();
    d2 = newDFA(v, &t->right->cnfa, &v->g->cmap, &v->dfa2);
    if (ISERR()) {
	assert(d2 == NULL);
	freeDFA(d);
	return v->err;
    }

    /*
     * Pick a tentative midpoint.
     */

    if (shorter) {
	mid = shortest(v, d, begin, begin, end, NULL, NULL);
    } else {
	mid = longest(v, d, begin, end, NULL);
    }
    if (mid == NULL) {
	freeDFA(d);
	freeDFA(d2);
	return REG_ASSERT;
    }
    MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));

    /*
     * Iterate until satisfaction or failure.
     */

    while (longest(v, d2, mid, end, NULL) != end) {
	/*
	 * That midpoint didn't work, find a new one.
	 */

	if (mid == stop) {
	    /*
	     * All possibilities exhausted!
	     */

	    MDEBUG(("no midpoint!\n"));
	    freeDFA(d);
	    freeDFA(d2);
	    return REG_ASSERT;
	}
	if (shorter) {
	    mid = shortest(v, d, begin, mid+1, end, NULL, NULL);
	} else {
	    mid = longest(v, d, begin, mid-1, NULL);
	}
	if (mid == NULL) {
	    /*
	     * Failed to find a new one!
	     */

	    MDEBUG(("failed midpoint!\n"));
	    freeDFA(d);
	    freeDFA(d2);
	    return REG_ASSERT;
	}
	MDEBUG(("new midpoint %ld\n", LOFF(mid)));
    }

    /*
     * Satisfaction.
     */

    MDEBUG(("successful\n"));
    freeDFA(d);
    freeDFA(d2);
    i = dissect(v, t->left, begin, mid);
    if (i != REG_OKAY) {
	return i;
    }
    return dissect(v, t->right, mid, end);
}
 
/*
 - alternationDissect - determine alternative subexpression matches (uncomplicated)
 ^ static int alternationDissect(struct vars *, struct subre *, chr *, chr *);
 */
static int			/* regexec return code */
alternationDissect(
    struct vars *const v,
    struct subre *t,
    chr *const begin,		/* beginning of relevant substring */
    chr *const end)		/* end of same */
{
    int i;

    assert(t != NULL);
    assert(t->op == '|');

    for (i = 0; t != NULL; t = t->right, i++) {
	struct dfa *d;

	MDEBUG(("trying %dth\n", i));
	assert(t->left != NULL && t->left->cnfa.nstates > 0);
	d = newDFA(v, &t->left->cnfa, &v->g->cmap, &v->dfa1);
	if (ISERR()) {
	    return v->err;
	}
	if (longest(v, d, begin, end, NULL) == end) {
	    MDEBUG(("success\n"));
	    freeDFA(d);
	    return dissect(v, t->left, begin, end);
	}
	freeDFA(d);
    }
    return REG_ASSERT;		/* none of them matched?!? */
}
 
/*
 - complicatedDissect - determine subexpression matches (with complications)
 * The retry memory stores the offset of the trial midpoint from begin, plus 1
 * so that 0 uniquely means "clean slate".
 ^ static int complicatedDissect(struct vars *, struct subre *, chr *, chr *);
 */
static inline int		/* regexec return code */
complicatedDissect(
    struct vars *const v,
    struct subre *const t,
    chr *const begin,		/* beginning of relevant substring */
    chr *const end)		/* end of same */
{
    assert(t != NULL);
    MDEBUG(("complicatedDissect %ld-%ld %c\n", LOFF(begin), LOFF(end), t->op));

    switch (t->op) {
    case '=':			/* terminal node */
	assert(t->left == NULL && t->right == NULL);
	return REG_OKAY;	/* no action, parent did the work */


    case '|':			/* alternation */
	assert(t->left != NULL);
	return complicatedAlternationDissect(v, t, begin, end);
    case 'b':			/* back ref -- shouldn't be calling us! */


	assert(t->left == NULL && t->right == NULL);

	return complicatedBackrefDissect(v, t, begin, end);
    case '.':			/* concatenation */
	assert(t->left != NULL && t->right != NULL);

	return complicatedConcatenationDissect(v, t, begin, end);

    case '(':			/* capturing */
	assert(t->left != NULL && t->right == NULL);
	assert(t->subno > 0);


	return complicatedCapturingDissect(v, t, begin, end);


    default:
	return REG_ASSERT;

    }
}







static int			/* regexec return code */
complicatedCapturingDissect(
    struct vars *const v,
    struct subre *const t,
    chr *const begin,		/* beginning of relevant substring */
    chr *const end)		/* end of same */
{
    int er = complicatedDissect(v, t->left, begin, end);

    if (er == REG_OKAY) {
	subset(v, t, begin, end);
    }
    return er;
}
 
/*
 - complicatedConcatenationDissect - concatenation subexpression matches (with complications)
 * The retry memory stores the offset of the trial midpoint from begin, plus 1
 * so that 0 uniquely means "clean slate".

 ^ static int complicatedConcatenationDissect(struct vars *, struct subre *, chr *, chr *);
 */
static int			/* regexec return code */
complicatedConcatenationDissect(

    struct vars *const v,
    struct subre *const t,
    chr *const begin,		/* beginning of relevant substring */
    chr *const end)		/* end of same */
{
    struct dfa *d, *d2;
    chr *mid;

    assert(t->op == '.');
    assert(t->left != NULL && t->left->cnfa.nstates > 0);
    assert(t->right != NULL && t->right->cnfa.nstates > 0);


    if (t->left->flags&SHORTER) { /* reverse scan */
	return complicatedReversedDissect(v, t, begin, end);
    }

    d = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
    if (ISERR()) {
	return v->err;
    }
    d2 = newDFA(v, &t->right->cnfa, &v->g->cmap, DOMALLOC);

    if (ISERR()) {
	freeDFA(d);
	return v->err;
    }
    MDEBUG(("cConcat %d\n", t->retry));

    /*
     * Pick a tentative midpoint.
     */

    if (v->mem[t->retry] == 0) {
	mid = longest(v, d, begin, end, NULL);
	if (mid == NULL) {
	    freeDFA(d);
	    freeDFA(d2);
	    return REG_NOMATCH;
	}
	MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));
	v->mem[t->retry] = (mid - begin) + 1;
    } else {
	mid = begin + (v->mem[t->retry] - 1);
	MDEBUG(("working midpoint %ld\n", LOFF(mid)));
    }

    /*
     * Iterate until satisfaction or failure.
     */

    for (;;) {
	/*
	 * Try this midpoint on for size.
	 */

	if (longest(v, d2, mid, end, NULL) == end) {
	    int er = complicatedDissect(v, t->left, begin, mid);

	    if (er == REG_OKAY) {
		er = complicatedDissect(v, t->right, mid, end);
		if (er == REG_OKAY) {
		    /*
		     * Satisfaction.
		     */

		    MDEBUG(("successful\n"));
		    freeDFA(d);
		    freeDFA(d2);
		    return REG_OKAY;
		}
	    }
	    if ((er != REG_OKAY) && (er != REG_NOMATCH)) {
		freeDFA(d);
		freeDFA(d2);
		return er;
	    }
	}

	/*
	 * That midpoint didn't work, find a new one.
	 */

	if (mid == begin) {
	    /*
	     * All possibilities exhausted.
	     */

	    MDEBUG(("%d no midpoint\n", t->retry));
	    freeDFA(d);
	    freeDFA(d2);
	    return REG_NOMATCH;
	}
	mid = longest(v, d, begin, mid-1, NULL);
	if (mid == NULL) {
	    /*
	     * Failed to find a new one.
	     */

	    MDEBUG(("%d failed midpoint\n", t->retry));
	    freeDFA(d);
	    freeDFA(d2);
	    return REG_NOMATCH;
	}
	MDEBUG(("%d: new midpoint %ld\n", t->retry, LOFF(mid)));
	v->mem[t->retry] = (mid - begin) + 1;
	zapSubtree(v, t->left);
	zapSubtree(v, t->right);
    }
}
 
/*
 - complicatedReversedDissect - determine backref shortest-first subexpression
 - matches
 * The retry memory stores the offset of the trial midpoint from begin, plus 1
 * so that 0 uniquely means "clean slate".
 ^ static int complicatedReversedDissect(struct vars *, struct subre *, chr *, chr *);
 */
static int			/* regexec return code */
complicatedReversedDissect(

    struct vars *const v,
    struct subre *const t,
    chr *const begin,		/* beginning of relevant substring */
    chr *const end)		/* end of same */
{
    struct dfa *d, *d2;
    chr *mid;

    assert(t->op == '.');
    assert(t->left != NULL && t->left->cnfa.nstates > 0);
    assert(t->right != NULL && t->right->cnfa.nstates > 0);
    assert(t->left->flags&SHORTER);

    /*
     * Concatenation -- need to split the substring between parts.
     */

    d = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);

    if (ISERR()) {
	return v->err;
    }
    d2 = newDFA(v, &t->right->cnfa, &v->g->cmap, DOMALLOC);

    if (ISERR()) {
	freeDFA(d);
	return v->err;
    }
    MDEBUG(("cRev %d\n", t->retry));


    /*
     * Pick a tentative midpoint.
     */

    if (v->mem[t->retry] == 0) {
	mid = shortest(v, d, begin, begin, end, NULL, NULL);
	if (mid == NULL) {
	    freeDFA(d);
	    freeDFA(d2);
	    return REG_NOMATCH;
	}
	MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));
	v->mem[t->retry] = (mid - begin) + 1;
    } else {
	mid = begin + (v->mem[t->retry] - 1);
	MDEBUG(("working midpoint %ld\n", LOFF(mid)));
    }

    /*
     * Iterate until satisfaction or failure.
     */

    for (;;) {
	/*
	 * Try this midpoint on for size.
	 */

	if (longest(v, d2, mid, end, NULL) == end) {
	    int er = complicatedDissect(v, t->left, begin, mid);

	    if (er == REG_OKAY) {
		er = complicatedDissect(v, t->right, mid, end);
		if (er == REG_OKAY) {
		    /*
		     * Satisfaction.
		     */

		    MDEBUG(("successful\n"));
		    freeDFA(d);
		    freeDFA(d2);
		    return REG_OKAY;
		}
	    }
	    if (er != REG_OKAY && er != REG_NOMATCH) {
		freeDFA(d);
		freeDFA(d2);
		return er;
	    }
	}

	/*
	 * That midpoint didn't work, find a new one.
	 */

	if (mid == end) {
	    /*
	     * All possibilities exhausted.
	     */

	    MDEBUG(("%d no midpoint\n", t->retry));
	    freeDFA(d);
	    freeDFA(d2);
	    return REG_NOMATCH;
	}
	mid = shortest(v, d, begin, mid+1, end, NULL, NULL);
	if (mid == NULL) {
	    /*
	     * Failed to find a new one.
	     */

	    MDEBUG(("%d failed midpoint\n", t->retry));
	    freeDFA(d);
	    freeDFA(d2);
	    return REG_NOMATCH;
	}
	MDEBUG(("%d: new midpoint %ld\n", t->retry, LOFF(mid)));
	v->mem[t->retry] = (mid - begin) + 1;
	zapSubtree(v, t->left);
	zapSubtree(v, t->right);
    }
}
 
/*
 - complicatedBackrefDissect - determine backref subexpression matches
 ^ static int complicatedBackrefDissect(struct vars *, struct subre *, chr *, chr *);
 */
static int			/* regexec return code */
complicatedBackrefDissect(
    struct vars *const v,
    struct subre *const t,
    chr *const begin,		/* beginning of relevant substring */
    chr *const end)		/* end of same */
{
    int i, n = t->subno, min = t->min, max = t->max;
    chr *paren, *p, *stop;
    size_t len;




    assert(t != NULL);
    assert(t->op == 'b');
    assert(n >= 0);
    assert((size_t)n < v->nmatch);

    MDEBUG(("cbackref n%d %d{%d-%d}\n", t->retry, n, min, max));


    if (v->pmatch[n].rm_so == -1) {
	return REG_NOMATCH;
    }
    paren = v->start + v->pmatch[n].rm_so;
    len = v->pmatch[n].rm_eo - v->pmatch[n].rm_so;



    /*
     * No room to maneuver -- retries are pointless.


     */




    if (v->mem[t->retry]) {
	return REG_NOMATCH;
    }
    v->mem[t->retry] = 1;









    /*
     * Special-case zero-length string.


     */

    if (len == 0) {
	if (begin == end) {

















	    return REG_OKAY;
	}



































	return REG_NOMATCH;





































    }

    /*
     * And too-short string.






     */










    assert(end >= begin);
    if ((size_t)(end - begin) < len) {



	return REG_NOMATCH;
    }
    stop = end - len;


    /*
     * Count occurrences.







     */


    i = 0;
    for (p = begin; p <= stop && (i < max || max == DUPINF); p += len) {
	if (v->g->compare(paren, p, len) != 0) {
	    break;


	}





























	i++;


    }
    MDEBUG(("cbackref found %d\n", i));

    /*
     * And sort it out.




     */



    if (p != end) {		/* didn't consume all of it */









	return REG_NOMATCH;




    }
    if (min <= i && (i <= max || max == DUPINF)) {





	return REG_OKAY;
    }



























    return REG_NOMATCH;		/* out of range */
}
 
/*
 - complicatedAlternationDissect - determine alternative subexpression matches (w.
 - complications)
 ^ static int complicatedAlternationDissect(struct vars *, struct subre *, chr *, chr *);
 */
static int			/* regexec return code */
complicatedAlternationDissect(
    struct vars *const v,
    struct subre *t,
    chr *const begin,		/* beginning of relevant substring */
    chr *const end)		/* end of same */
{






    int er;
#define	UNTRIED	0		/* not yet tried at all */
#define	TRYING	1		/* top matched, trying submatches */
#define	TRIED	2		/* top didn't match or submatches exhausted */



#ifndef COMPILER_DOES_TAILCALL_OPTIMIZATION
    if (0) {
    doRight:
	t = t->right;



    }
#endif
    if (t == NULL) {








	return REG_NOMATCH;

    }
    assert(t->op == '|');
    if (v->mem[t->retry] == TRIED) {
	goto doRight;
    }






    MDEBUG(("cAlt n%d\n", t->retry));
    assert(t->left != NULL);













    if (v->mem[t->retry] == UNTRIED) {
	struct dfa *d = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);


	if (ISERR()) {

	    return v->err;
	}
	if (longest(v, d, begin, end, NULL) != end) {
	    freeDFA(d);
	    v->mem[t->retry] = TRIED;
	    goto doRight;

	}
	freeDFA(d);
	MDEBUG(("cAlt matched\n"));
	v->mem[t->retry] = TRYING;









    }


























































    er = complicatedDissect(v, t->left, begin, end);




    if (er != REG_NOMATCH) {



	return er;
    }

    v->mem[t->retry] = TRIED;
#ifndef COMPILER_DOES_TAILCALL_OPTIMIZATION
    goto doRight;
#else
  doRight:
    return complicatedAlternationDissect(v, t->right, begin, end);
#endif




























}

#include "rege_dfa.c"
 
/*
 * Local Variables:
 * mode: c
 * c-basic-offset: 4
 * fill-column: 78
 * End:
 */






|





|












>



|
|

|
|
|
|
|
|
|
<
<







 







>


|
<
>







 







<
<
<
<
<
|
|
|
<
>
|
<
<
>
|
|
|
<
|
|
|
<
>
|
<







 







|











|
|
>
>

>
>



>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







|
>
>
>







 







|


|
|







 







|
<
|










>







 







|
|


|












|
|


|



|
|
|
|
|
|
|
<
<
<



|


|




|







 







|
>
>
>
>
>
>
>
>
>
>
|


|
|

|
|

<
<
<
>
>

|




|
|
>
|
|
<
|


|
<
<
<
|
<
<
<
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
>
>


|
<
>
>
|
>
|
<
<
>
|
>



>
>
|
>
>

|
>

|
>
>
>
>
>
>

<
<
<
<
<
<
<
<
<
<
<
<




<
<
<
>
|


<
>
|
|
|
|







>

<
|
<
<
<
|
<
<
<
>
|
<
<
|
|




<
<
|
|
<
<
|
|
|
<
<
<
<
<











|


|






<
<



|
<
<













|
<
<








|
<
<


|
<
|
|




|
<
<
<
|


<
>
|
|
|
|









<
<
<
<
<
>
|
<
<
<
>
|
<
<
|
<
>





<
|
|
<
<
|
|
|
<
<
<
<
<











|


|






<
<



|
<
<













|
<
<








|
<
<


|
<
|
|




|
|


|
|
|
|
|

|
|
|
>
>
>






|

>



|
|

>
>
|
<
>
>
|
>
>
>
|
<


<
>
>
>
>
>
|
>
>
>

<
>
>


<
<
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>



|
>
>
>
>
>
>

>
>
>
>
>
>
>
>
>

<
<
>
>
>
|

<
>


<
>
>
>
>
>
>
>


>
|
<
<
<
>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
>
>
|
<

|
<
>
>
>
>
|
>
>

<
>
>
>
>
>
>
>
>
>
|
>
>
>
>
|
<
>
>
>
>
>
|
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|



|
<
|


<
|
|
|
|

>
>
>
>
>
>
|
<
<
<
>
>

<
<
<
|
>
>
>
|
<
<
>
>
>
>
>
>
>
>
|
>

<
<
<
|
>
>
>
>
>
|
<
<
>
>
>
>
>
>
>
>
>
>
>
>

<
<
<
>
|
>
|
|
<
<
<
<
>
|
<
<
<
>
>
>
>
>
>
>
>
>
|
>
>
>
>

>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
>
>
>
>
|
>
>
>
|
|

<
<
<
<
<
<
<
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>











103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142


143
144
145
146
147
148
149
...
169
170
171
172
173
174
175
176
177
178
179

180
181
182
183
184
185
186
187
...
231
232
233
234
235
236
237





238
239
240

241
242


243
244
245
246

247
248
249

250
251

252
253
254
255
256
257
258
...
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
...
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
...
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
...
500
501
502
503
504
505
506
507

508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
...
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575



576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
...
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629



630
631
632
633
634
635
636
637
638
639
640
641
642

643
644
645
646



647



648
































































































































































649
650
651
652
653

654
655
656
657
658


659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681












682
683
684
685



686
687
688
689

690
691
692
693
694
695
696
697
698
699
700
701
702
703

704



705



706
707


708
709
710
711
712
713


714
715


716
717
718





719
720
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



777
778
779

780
781
782
783
784
785
786
787
788
789
790
791
792
793





794
795



796
797


798

799
800
801
802
803
804

805
806


807
808
809





810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830


831
832
833
834


835
836
837
838
839
840
841
842
843
844
845
846
847
848


849
850
851
852
853
854
855
856
857


858
859
860

861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900

901
902
903
904
905
906
907

908
909

910
911
912
913
914
915
916
917
918
919

920
921
922
923


924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036


1037
1038
1039
1040
1041

1042
1043
1044

1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055



1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091

1092
1093

1094
1095
1096
1097
1098
1099
1100
1101

1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116

1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155

1156
1157
1158

1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170



1171
1172
1173



1174
1175
1176
1177
1178


1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189



1190
1191
1192
1193
1194
1195
1196


1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209



1210
1211
1212
1213
1214




1215
1216



1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296







1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
    int eflags;			/* copies of arguments */
    size_t nmatch;
    regmatch_t *pmatch;
    rm_detail_t *details;
    chr *start;			/* start of string */
    chr *stop;			/* just past end of string */
    int err;			/* error code if any (0 none) */
    struct dfa **subdfas;	/* per-subre DFAs */
    struct smalldfa dfa1;
    struct smalldfa dfa2;
};
#define	VISERR(vv) ((vv)->err != 0)	/* have we seen an error yet? */
#define	ISERR()	VISERR(v)
#define VERR(vv,e) ((vv)->err = ((vv)->err ? (vv)->err : (e)))
#define	ERR(e)	VERR(v, e)	/* record an error */
#define	NOERR()	{if (ISERR()) return v->err;}	/* if error seen, return it */
#define	OFF(p)	((p) - v->start)
#define	LOFF(p)	((long)OFF(p))
 
/*
 * forward declarations
 */
/* =====^!^===== begin forwards =====^!^===== */
/* automatically gathered by fwd; do not hand-edit */
/* === regexec.c === */
int exec(regex_t *, const chr *, size_t, rm_detail_t *, size_t, regmatch_t [], int);
static struct dfa *getsubdfa(struct vars *, struct subre *);
static int simpleFind(struct vars *const, struct cnfa *const, struct colormap *const);
static int complicatedFind(struct vars *const, struct cnfa *const, struct colormap *const);
static int complicatedFindLoop(struct vars *const, struct cnfa *const, struct colormap *const, struct dfa *const, struct dfa *const, chr **const);
static void zapallsubs(regmatch_t *const, const size_t);
static void zaptreesubs(struct vars *const, struct subre *const);
static void subset(struct vars *const, struct subre *const, chr *const, chr *const);
static int cdissect(struct vars *, struct subre *, chr *, chr *);
static int ccondissect(struct vars *, struct subre *, chr *, chr *);
static int crevcondissect(struct vars *, struct subre *, chr *, chr *);
static int cbrdissect(struct vars *, struct subre *, chr *, chr *);
static int caltdissect(struct vars *, struct subre *, chr *, chr *);
static int citerdissect(struct vars *, struct subre *, chr *, chr *);
static int creviterdissect(struct vars *, struct subre *, chr *, chr *);


/* === rege_dfa.c === */
static chr *longest(struct vars *const, struct dfa *const, chr *const, chr *const, int *const);
static chr *shortest(struct vars *const, struct dfa *const, chr *const, chr *const, chr *const, chr **const, int *const);
static chr *lastCold(struct vars *const, struct dfa *const);
static struct dfa *newDFA(struct vars *const, struct cnfa *const, struct colormap *const, struct smalldfa *);
static void freeDFA(struct dfa *const);
static unsigned hash(unsigned *const, const int);
................................................................................
    size_t nmatch,
    regmatch_t pmatch[],
    int flags)
{
    AllocVars(v);
    int st, backref;
    size_t n;
    size_t i;
#define	LOCALMAT	20
    regmatch_t mat[LOCALMAT];
#define LOCALDFAS	40

    struct dfa *subdfas[LOCALDFAS];

    /*
     * Sanity checks.
     */

    if (re == NULL || string == NULL || re->re_magic != REMAGIC) {
	FreeVars(v);
................................................................................
    } else {
	v->pmatch = pmatch;
    }
    v->details = details;
    v->start = (chr *)string;
    v->stop = (chr *)string + len;
    v->err = 0;





    assert(v->g->ntree >= 0);
    n = (size_t) v->g->ntree;
    if (n <= LOCALDFAS)

	v->subdfas = subdfas;
    else


	v->subdfas = (struct dfa **) MALLOC(n * sizeof(struct dfa *));
    if (v->subdfas == NULL) {
	if (v->pmatch != pmatch && v->pmatch != mat)
	    FREE(v->pmatch);

	FreeVars(v);
	return REG_ESPACE;
    }

    for (i = 0; i < n; i++)
	v->subdfas[i] = NULL;


    /*
     * Do it.
     */

    assert(v->g->tree != NULL);
    if (backref) {
................................................................................
    }

    /*
     * Copy (portion of) match vector over if necessary.
     */

    if (st == REG_OKAY && v->pmatch != pmatch && nmatch > 0) {
	zapallsubs(pmatch, nmatch);
	n = (nmatch < v->nmatch) ? nmatch : v->nmatch;
	memcpy(VS(pmatch), VS(v->pmatch), n*sizeof(regmatch_t));
    }

    /*
     * Clean up.
     */

    if (v->pmatch != pmatch && v->pmatch != mat) {
	FREE(v->pmatch);
    }
    n = (size_t) v->g->ntree;
    for (i = 0; i < n; i++) {
	if (v->subdfas[i] != NULL)
	    freeDFA(v->subdfas[i]);
    }
    if (v->subdfas != subdfas)
	FREE(v->subdfas);
    FreeVars(v);
    return st;
}
 
/*
 - getsubdfa - create or re-fetch the DFA for a subre node
 * We only need to create the DFA once per overall regex execution.
 * The DFA will be freed by the cleanup step in exec().
 */
static struct dfa *
getsubdfa(struct vars * v,
	  struct subre * t)
{
    if (v->subdfas[t->id] == NULL) {
	v->subdfas[t->id] = newDFA(v, &t->cnfa, &v->g->cmap, DOMALLOC);
	if (ISERR())
	    return NULL;
    }
    return v->subdfas[t->id];
}
 
/*
 - simpleFind - find a match for the main NFA (no-complications case)
 ^ static int simpleFind(struct vars *, struct cnfa *, struct colormap *);
 */
static int
simpleFind(
................................................................................
    for (begin = open; begin <= close; begin++) {
	MDEBUG(("\nfind trying at %ld\n", LOFF(begin)));
	if (shorter) {
	    end = shortest(v, d, begin, begin, v->stop, NULL, &hitend);
	} else {
	    end = longest(v, d, begin, v->stop, &hitend);
	}
	if (ISERR()) {
	    freeDFA(d);
	    return v->err;
	}
	if (hitend && cold == NULL) {
	    cold = begin;
	}
	if (end != NULL) {
	    break;		/* NOTE BREAK OUT */
	}
    }
................................................................................
	v->details->rm_extend.rm_eo = OFF(v->stop);	/* unknown */
    }
    if (v->nmatch == 1) {	/* no need for submatches */
	return REG_OKAY;
    }

    /*
     * Find submatches.
     */

    zapallsubs(v->pmatch, v->nmatch);
    return cdissect(v, v->g->tree, begin, end);
}
 
/*
 - complicatedFind - find a match for the main NFA (with complications)
 ^ static int complicatedFind(struct vars *, struct cnfa *, struct colormap *);
 */
static int
................................................................................
		    cold = begin;
		}
		if (end == NULL) {
		    break;	/* NOTE BREAK OUT */
		}

		MDEBUG(("tentative end %ld\n", LOFF(end)));
		zapallsubs(v->pmatch, v->nmatch);

		er = cdissect(v, v->g->tree, begin, end);
		if (er == REG_OKAY) {
		    if (v->nmatch > 0) {
			v->pmatch[0].rm_so = OFF(begin);
			v->pmatch[0].rm_eo = OFF(end);
		    }
		    *coldp = cold;
		    return REG_OKAY;
		}
		if (er != REG_NOMATCH) {
		    ERR(er);
		    *coldp = cold;
		    return er;
		}
		if ((shorter) ? end == estop : end == begin) {
		    break;
		}

		/*
................................................................................
    } while (close < v->stop);

    *coldp = cold;
    return REG_NOMATCH;
}
 
/*
 - zapallsubs - initialize all subexpression matches to "no match"
 ^ static void zapallsubs(regmatch_t *, size_t);
 */
static void
zapallsubs(
    regmatch_t *const p,
    const size_t n)
{
    size_t i;

    for (i = n-1; i > 0; i--) {
	p[i].rm_so = -1;
	p[i].rm_eo = -1;
    }
}
 
/*
 - zaptreesubs - initialize subexpressions within subtree to "no match"
 ^ static void zaptreesubs(struct vars *, struct subre *);
 */
static void
zaptreesubs(
    struct vars *const v,
    struct subre *const t)
{
    if (t->op == '(') {
	int n = t->subno;
	assert(n > 0);
	if ((size_t) n < v->nmatch) {
	    v->pmatch[n].rm_so = -1;
	    v->pmatch[n].rm_eo = -1;
	}



    }

    if (t->left != NULL) {
	zaptreesubs(v, t->left);
    }
    if (t->right != NULL) {
	zaptreesubs(v, t->right);
    }
}
 
/*
 - subset - set subexpression match data for a successful subre
 ^ static void subset(struct vars *, struct subre *, chr *, chr *);
 */
static void
subset(
    struct vars *const v,
    struct subre *const sub,
    chr *const begin,
................................................................................

    MDEBUG(("setting %d\n", n));
    v->pmatch[n].rm_so = OFF(begin);
    v->pmatch[n].rm_eo = OFF(end);
}
 
/*
 - cdissect - check backrefs and determine subexpression matches
 * cdissect recursively processes a subre tree to check matching of backrefs
 * and/or identify submatch boundaries for capture nodes.  The proposed match
 * runs from "begin" to "end" (not including "end"), and we are basically
 * "dissecting" it to see where the submatches are.
 * Before calling any level of cdissect, the caller must have run the node's
 * DFA and found that the proposed substring satisfies the DFA.  (We make
 * the caller do that because in concatenation and iteration nodes, it's
 * much faster to check all the substrings against the child DFAs before we
 * recurse.)  Also, caller must have cleared subexpression match data via
 * zaptreesubs (or zapallsubs at the top level).
 ^ static int cdissect(struct vars *, struct subre *, chr *, chr *);
 */
static int			/* regexec return code */
cdissect(
    struct vars *v,
    struct subre *t,
    chr *begin,		/* beginning of relevant substring */
    chr *end)		/* end of same */
{



    int er;

    assert(t != NULL);
    MDEBUG(("cdissect %ld-%ld %c\n", LOFF(begin), LOFF(end), t->op));

    switch (t->op) {
    case '=':			/* terminal node */
	assert(t->left == NULL && t->right == NULL);
	er = REG_OKAY;		/* no action, parent did the work */
	break;
    case 'b':			/* back reference */
	assert(t->left == NULL && t->right == NULL);
	er = cbrdissect(v, t, begin, end);

	break;
    case '.':			/* concatenation */
	assert(t->left != NULL && t->right != NULL);
	if (t->left->flags & SHORTER) /* reverse scan */



	    er = crevcondissect(v, t, begin, end);



	else
































































































































































	    er = ccondissect(v, t, begin, end);
	break;
    case '|':			/* alternation */
	assert(t->left != NULL);
	er = caltdissect(v, t, begin, end);

	break;
    case '*':			/* iteration */
	assert(t->left != NULL);
	if (t->left->flags & SHORTER) /* reverse scan */
	    er = creviterdissect(v, t, begin, end);


	else
	    er = citerdissect(v, t, begin, end);
	break;
    case '(':			/* capturing */
	assert(t->left != NULL && t->right == NULL);
	assert(t->subno > 0);
	er = cdissect(v, t->left, begin, end);
	if (er == REG_OKAY) {
	    subset(v, t, begin, end);
	}
	break;
    default:
	er = REG_ASSERT;
	break;
    }

    /*
     * We should never have a match failure unless backrefs lurk below;
     * otherwise, either caller failed to check the DFA, or there's some
     * inconsistency between the DFA and the node's innards.
     */
    assert(er != REG_NOMATCH || (t->flags & BACKR));













    return er;
}
 
/*



 - ccondissect - dissect match for concatenation node
 ^ static int ccondissect(struct vars *, struct subre *, chr *, chr *);
 */
static int			/* regexec return code */

ccondissect(
    struct vars *v,
    struct subre *t,
    chr *begin,		/* beginning of relevant substring */
    chr *end)		/* end of same */
{
    struct dfa *d, *d2;
    chr *mid;

    assert(t->op == '.');
    assert(t->left != NULL && t->left->cnfa.nstates > 0);
    assert(t->right != NULL && t->right->cnfa.nstates > 0);
    assert(!(t->left->flags & SHORTER));


    d = getsubdfa(v, t->left);



    NOERR();



    d2 = getsubdfa(v, t->right);
    NOERR();



    MDEBUG(("cConcat %d\n", t->id));

    /*
     * Pick a tentative midpoint.
     */


    mid = longest(v, d, begin, end, (int *) NULL);
    if (mid == NULL) {


	return REG_NOMATCH;
    }
    MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));






    /*
     * Iterate until satisfaction or failure.
     */

    for (;;) {
	/*
	 * Try this midpoint on for size.
	 */

	if (longest(v, d2, mid, end, NULL) == end) {
	    int er = cdissect(v, t->left, begin, mid);

	    if (er == REG_OKAY) {
		er = cdissect(v, t->right, mid, end);
		if (er == REG_OKAY) {
		    /*
		     * Satisfaction.
		     */

		    MDEBUG(("successful\n"));


		    return REG_OKAY;
		}
	    }
	    if (er != REG_NOMATCH) {


		return er;
	    }
	}

	/*
	 * That midpoint didn't work, find a new one.
	 */

	if (mid == begin) {
	    /*
	     * All possibilities exhausted.
	     */

	    MDEBUG(("%d no midpoint\n", t->id));


	    return REG_NOMATCH;
	}
	mid = longest(v, d, begin, mid-1, NULL);
	if (mid == NULL) {
	    /*
	     * Failed to find a new one.
	     */

	    MDEBUG(("%d failed midpoint\n", t->id));


	    return REG_NOMATCH;
	}
	MDEBUG(("%d: new midpoint %ld\n", t->id, LOFF(mid)));

	zaptreesubs(v, t->left);
	zaptreesubs(v, t->right);
    }
}
 
/*
 - crevcondissect - dissect match for concatenation node, shortest-first



 ^ static int crevcondissect(struct vars *, struct subre *, chr *, chr *);
 */
static int			/* regexec return code */

crevcondissect(
    struct vars *v,
    struct subre *t,
    chr *begin,		/* beginning of relevant substring */
    chr *end)		/* end of same */
{
    struct dfa *d, *d2;
    chr *mid;

    assert(t->op == '.');
    assert(t->left != NULL && t->left->cnfa.nstates > 0);
    assert(t->right != NULL && t->right->cnfa.nstates > 0);
    assert(t->left->flags&SHORTER);






    d = getsubdfa(v, t->left);
    NOERR();



    d2 = getsubdfa(v, t->right);
    NOERR();




    MDEBUG(("crevcon %d\n", t->id));

    /*
     * Pick a tentative midpoint.
     */


    mid = shortest(v, d, begin, begin, end, (chr **) NULL, (int *) NULL);
    if (mid == NULL) {


	return REG_NOMATCH;
    }
    MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));






    /*
     * Iterate until satisfaction or failure.
     */

    for (;;) {
	/*
	 * Try this midpoint on for size.
	 */

	if (longest(v, d2, mid, end, NULL) == end) {
	    int er = cdissect(v, t->left, begin, mid);

	    if (er == REG_OKAY) {
		er = cdissect(v, t->right, mid, end);
		if (er == REG_OKAY) {
		    /*
		     * Satisfaction.
		     */

		    MDEBUG(("successful\n"));


		    return REG_OKAY;
		}
	    }
	    if (er != REG_NOMATCH) {


		return er;
	    }
	}

	/*
	 * That midpoint didn't work, find a new one.
	 */

	if (mid == end) {
	    /*
	     * All possibilities exhausted.
	     */

	    MDEBUG(("%d no midpoint\n", t->id));


	    return REG_NOMATCH;
	}
	mid = shortest(v, d, begin, mid+1, end, NULL, NULL);
	if (mid == NULL) {
	    /*
	     * Failed to find a new one.
	     */

	    MDEBUG(("%d failed midpoint\n", t->id));


	    return REG_NOMATCH;
	}
	MDEBUG(("%d: new midpoint %ld\n", t->id, LOFF(mid)));

	zaptreesubs(v, t->left);
	zaptreesubs(v, t->right);
    }
}
 
/*
 - cbrdissect - dissect match for backref node
 ^ static int cbrdissect(struct vars *, struct subre *, chr *, chr *);
 */
static int			/* regexec return code */
cbrdissect(
    struct vars *v,
    struct subre *t,
    chr *begin,		/* beginning of relevant substring */
    chr *end)		/* end of same */
{
    int n = t->subno, min = t->min, max = t->max;
    size_t numreps;
    size_t tlen;
    size_t brlen;
    chr *brstring;
    chr *p;

    assert(t != NULL);
    assert(t->op == 'b');
    assert(n >= 0);
    assert((size_t)n < v->nmatch);

    MDEBUG(("cbackref n%d %d{%d-%d}\n", t->id, n, min, max));

    /* get the backreferenced string */
    if (v->pmatch[n].rm_so == -1) {
	return REG_NOMATCH;
    }
    brstring = v->start + v->pmatch[n].rm_so;
    brlen = v->pmatch[n].rm_eo - v->pmatch[n].rm_so;

    /* special cases for zero-length strings */
    if (brlen == 0) {
	/*

	 * matches only if target is zero length, but any number of
	 * repetitions can be considered to be present
	 */
	if (begin == end && min <= max) {
	    MDEBUG(("cbackref matched trivially\n"));
	    return REG_OKAY;
	}

	return REG_NOMATCH;
    }

    if (begin == end) {
	/* matches only if zero repetitions are okay */
	if (min == 0) {
	    MDEBUG(("cbackref matched trivially\n"));
	    return REG_OKAY;
	}
	return REG_NOMATCH;
    }

    /*

     * check target length to see if it could possibly be an allowed number of
     * repetitions of brstring
     */



    assert(end > begin);
    tlen = end - begin;
    if (tlen % brlen != 0)
	return REG_NOMATCH;
    numreps = tlen / brlen;
    if (numreps < (size_t)min || (numreps > (size_t)max && max != DUPINF))
	return REG_NOMATCH;

    /* okay, compare the actual string contents */
    p = begin;
    while (numreps-- > 0) {
	if ((*v->g->compare) (brstring, p, brlen) != 0)
	    return REG_NOMATCH;
	p += brlen;
    }

    MDEBUG(("cbackref matched\n"));
    return REG_OKAY;
}
 
/*
 - caltdissect - dissect match for alternation node
 ^ static int caltdissect(struct vars *, struct subre *, chr *, chr *);
 */
static int			/* regexec return code */
caltdissect(
    struct vars *v,
    struct subre *t,
    chr *begin,		/* beginning of relevant substring */
    chr *end)		/* end of same */
{
    struct dfa *d;
    int er;

    /* We loop, rather than tail-recurse, to handle a chain of alternatives */
    while (t != NULL) {
	assert(t->op == '|');
	assert(t->left != NULL && t->left->cnfa.nstates > 0);

	MDEBUG(("calt n%d\n", t->id));

	d = getsubdfa(v, t->left);
	NOERR();
	if (longest(v, d, begin, end, (int *) NULL) == end) {
	    MDEBUG(("calt matched\n"));
	    er = cdissect(v, t->left, begin, end);
	    if (er != REG_NOMATCH) {
		return er;
	    }
	}

	t = t->right;
    }

    return REG_NOMATCH;
}
 
/*
 - citerdissect - dissect match for iteration node
 ^ static int citerdissect(struct vars *, struct subre *, chr *, chr *);
 */
static int			/* regexec return code */
citerdissect(struct vars * v,
	     struct subre * t,
	     chr *begin,	/* beginning of relevant substring */
	     chr *end)		/* end of same */
{
    struct dfa *d;
    chr	  **endpts;
    chr	   *limit;
    int		min_matches;
    size_t	max_matches;
    int		nverified;
    int		k;
    int		i;
    int		er;

    assert(t->op == '*');
    assert(t->left != NULL && t->left->cnfa.nstates > 0);
    assert(!(t->left->flags & SHORTER));
    assert(begin <= end);

    /*
     * If zero matches are allowed, and target string is empty, just declare
     * victory.  OTOH, if target string isn't empty, zero matches can't work
     * so we pretend the min is 1.
     */
    min_matches = t->min;
    if (min_matches <= 0) {
	if (begin == end)
	    return REG_OKAY;
	min_matches = 1;
    }

    /*
     * We need workspace to track the endpoints of each sub-match.  Normally
     * we consider only nonzero-length sub-matches, so there can be at most
     * end-begin of them.  However, if min is larger than that, we will also
     * consider zero-length sub-matches in order to find enough matches.
     *
     * For convenience, endpts[0] contains the "begin" pointer and we store
     * sub-match endpoints in endpts[1..max_matches].
     */
    max_matches = end - begin;
    if (max_matches > (size_t)t->max && t->max != DUPINF)
	max_matches = t->max;
    if (max_matches < (size_t)min_matches)
	max_matches = min_matches;
    endpts = (chr **) MALLOC((max_matches + 1) * sizeof(chr *));
    if (endpts == NULL)
	return REG_ESPACE;
    endpts[0] = begin;



    d = getsubdfa(v, t->left);
    if (ISERR()) {
	FREE(endpts);
	return v->err;
    }

    MDEBUG(("citer %d\n", t->id));

    /*

     * Our strategy is to first find a set of sub-match endpoints that are
     * valid according to the child node's DFA, and then recursively dissect
     * each sub-match to confirm validity.  If any validity check fails,
     * backtrack the last sub-match and try again.  And, when we next try for
     * a validity check, we need not recheck any successfully verified
     * sub-matches that we didn't move the endpoints of.  nverified remembers
     * how many sub-matches are currently known okay.
     */

    /* initialize to consider first sub-match */
    nverified = 0;



    k = 1;
    limit = end;

    /* iterate until satisfaction or failure */
    while (k > 0) {
	/* try to find an endpoint for the k'th sub-match */
	endpts[k] = longest(v, d, endpts[k - 1], limit, (int *) NULL);
	if (endpts[k] == NULL) {
	    /* no match possible, so see if we can shorten previous one */
	    k--;
	    goto backtrack;
	}
	MDEBUG(("%d: working endpoint %d: %ld\n",
		t->id, k, LOFF(endpts[k])));

	/* k'th sub-match can no longer be considered verified */
	if (nverified >= k)
	    nverified = k - 1;

	if (endpts[k] != end) {
	    /* haven't reached end yet, try another iteration if allowed */
	    if ((size_t)k >= max_matches) {
		/* must try to shorten some previous match */
		k--;
		goto backtrack;
	    }

	    /* reject zero-length match unless necessary to achieve min */
	    if (endpts[k] == endpts[k - 1] &&
		(k >= min_matches || min_matches - k < end - endpts[k]))
		goto backtrack;

	    k++;
	    limit = end;
	    continue;
	}


	/*

	 * We've identified a way to divide the string into k sub-matches
	 * that works so far as the child DFA can tell.  If k is an allowed
	 * number of matches, start the slow part: recurse to verify each
	 * sub-match.  We always have k <= max_matches, needn't check that.
	 */
	if (k < min_matches)
	    goto backtrack;


	MDEBUG(("%d: verifying %d..%d\n", t->id, nverified + 1, k));

	for (i = nverified + 1; i <= k; i++) {
	    zaptreesubs(v, t->left);
	    er = cdissect(v, t->left, endpts[i - 1], endpts[i]);
	    if (er == REG_OKAY) {
		nverified = i;
		continue;
	    }
	    if (er == REG_NOMATCH)
		break;
	    /* oops, something failed */
	    FREE(endpts);
	    return er;
	}


	if (i > k) {
	    /* satisfaction */
	    MDEBUG(("%d successful\n", t->id));
	    FREE(endpts);
	    return REG_OKAY;
	}

	/* match failed to verify, so backtrack */

    backtrack:
	/*
	 * Must consider shorter versions of the current sub-match.  However,
	 * we'll only ask for a zero-length match if necessary.
	 */
	while (k > 0) {
	    chr	   *prev_end = endpts[k - 1];

	    if (endpts[k] > prev_end) {
		limit = endpts[k] - 1;
		if (limit > prev_end ||
		    (k < min_matches && min_matches - k >= end - prev_end)) {
		    /* break out of backtrack loop, continue the outer one */
		    break;
		}
	    }
	    /* can't shorten k'th sub-match any more, consider previous one */
	    k--;
	}
    }

    /* all possibilities exhausted */
    MDEBUG(("%d failed\n", t->id));
    FREE(endpts);
    return REG_NOMATCH;
}
 
/*
 - creviterdissect - dissect match for iteration node, shortest-first

 ^ static int creviterdissect(struct vars *, struct subre *, chr *, chr *);
 */
static int			/* regexec return code */

creviterdissect(struct vars * v,
		struct subre * t,
		chr *begin,	/* beginning of relevant substring */
		chr *end)	/* end of same */
{
    struct dfa *d;
    chr	  **endpts;
    chr	   *limit;
    int		min_matches;
    size_t	max_matches;
    int		nverified;
    int		k;



    int		i;
    int		er;




    assert(t->op == '*');
    assert(t->left != NULL && t->left->cnfa.nstates > 0);
    assert(t->left->flags & SHORTER);
    assert(begin <= end);



    /*
     * If zero matches are allowed, and target string is empty, just declare
     * victory.  OTOH, if target string isn't empty, zero matches can't work
     * so we pretend the min is 1.
     */
    min_matches = t->min;
    if (min_matches <= 0) {
	if (begin == end)
	    return REG_OKAY;
	min_matches = 1;
    }




    /*
     * We need workspace to track the endpoints of each sub-match.  Normally
     * we consider only nonzero-length sub-matches, so there can be at most
     * end-begin of them.  However, if min is larger than that, we will also
     * consider zero-length sub-matches in order to find enough matches.
     *


     * For convenience, endpts[0] contains the "begin" pointer and we store
     * sub-match endpoints in endpts[1..max_matches].
     */
    max_matches = end - begin;
    if (max_matches > (size_t)t->max && t->max != DUPINF)
	max_matches = t->max;
    if (max_matches < (size_t)min_matches)
	max_matches = min_matches;
    endpts = (chr **) MALLOC((max_matches + 1) * sizeof(chr *));
    if (endpts == NULL)
	return REG_ESPACE;
    endpts[0] = begin;




    d = getsubdfa(v, t->left);
    if (ISERR()) {
	FREE(endpts);
	return v->err;
    }




    MDEBUG(("creviter %d\n", t->id));




    /*
     * Our strategy is to first find a set of sub-match endpoints that are
     * valid according to the child node's DFA, and then recursively dissect
     * each sub-match to confirm validity.  If any validity check fails,
     * backtrack the last sub-match and try again.  And, when we next try for
     * a validity check, we need not recheck any successfully verified
     * sub-matches that we didn't move the endpoints of.  nverified remembers
     * how many sub-matches are currently known okay.
     */

    /* initialize to consider first sub-match */
    nverified = 0;
    k = 1;
    limit = begin;

    /* iterate until satisfaction or failure */
    while (k > 0) {
	/* disallow zero-length match unless necessary to achieve min */
	if (limit == endpts[k - 1] &&
	    limit != end &&
	    (k >= min_matches || min_matches - k < end - limit))
	    limit++;

	/* if this is the last allowed sub-match, it must reach to the end */
	if ((size_t)k >= max_matches)
	    limit = end;

	/* try to find an endpoint for the k'th sub-match */
	endpts[k] = shortest(v, d, endpts[k - 1], limit, end,
			     (chr **) NULL, (int *) NULL);
	if (endpts[k] == NULL) {
	    /* no match possible, so see if we can lengthen previous one */
	    k--;
	    goto backtrack;
	}
	MDEBUG(("%d: working endpoint %d: %ld\n",
		t->id, k, LOFF(endpts[k])));

	/* k'th sub-match can no longer be considered verified */
	if (nverified >= k)
	    nverified = k - 1;

	if (endpts[k] != end) {
	    /* haven't reached end yet, try another iteration if allowed */
	    if ((size_t)k >= max_matches) {
		/* must try to lengthen some previous match */
		k--;
		goto backtrack;
	    }

	    k++;
	    limit = endpts[k - 1];
	    continue;
	}

	/*
	 * We've identified a way to divide the string into k sub-matches
	 * that works so far as the child DFA can tell.  If k is an allowed
	 * number of matches, start the slow part: recurse to verify each
	 * sub-match.  We always have k <= max_matches, needn't check that.
	 */
	if (k < min_matches)
	    goto backtrack;

	MDEBUG(("%d: verifying %d..%d\n", t->id, nverified + 1, k));

	for (i = nverified + 1; i <= k; i++) {
	    zaptreesubs(v, t->left);
	    er = cdissect(v, t->left, endpts[i - 1], endpts[i]);
	    if (er == REG_OKAY) {
		nverified = i;
		continue;
	    }
	    if (er == REG_NOMATCH)
		break;
	    /* oops, something failed */
	    FREE(endpts);
	    return er;
	}








	if (i > k) {
	    /* satisfaction */
	    MDEBUG(("%d successful\n", t->id));
	    FREE(endpts);
	    return REG_OKAY;
	}

	/* match failed to verify, so backtrack */

    backtrack:
	/*
	 * Must consider longer versions of the current sub-match.
	 */
	while (k > 0) {
	    if (endpts[k] < end) {
		limit = endpts[k] + 1;
		/* break out of backtrack loop, continue the outer one */
		break;
	    }
	    /* can't lengthen k'th sub-match any more, consider previous one */
	    k--;
	}
    }

    /* all possibilities exhausted */
    MDEBUG(("%d failed\n", t->id));
    FREE(endpts);
    return REG_NOMATCH;
}

#include "rege_dfa.c"
 
/*
 * Local Variables:
 * mode: c
 * c-basic-offset: 4
 * fill-column: 78
 * End:
 */

Changes to generic/regguts.h.

182
183
184
185
186
187
188

189






190
191
192
193
194
195
196
...
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
...
293
294
295
296
297
298
299











300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315


316

317
318
319
320
321
322
323
...
325
326
327
328
329
330
331


















332
333
334
335
336
337
338
339
340
341
342
343
...
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
...
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
    int flags;
#define	FREECOL	01		/* currently free */
#define	PSEUDO	02		/* pseudocolor, no real chars */
#define	UNUSEDCOLOR(cd)	((cd)->flags&FREECOL)
    union tree *block;		/* block of solid color, if any */
};


/* the color map itself */






struct colormap {
    int magic;
#define	CMMAGIC	0x876
    struct vars *v;		/* for compile error reporting */
    size_t ncds;		/* number of colordescs */
    size_t max;			/* highest in use */
    color free;			/* beginning of free chain (if non-0) */
................................................................................
 * Having a "from" pointer within each arc may seem redundant, but it saves a
 * lot of hassle.
 */

struct state;

struct arc {
    int type;
#define	ARCFREE	'\0'
    color co;
    struct state *from;		/* where it's from (and contained within) */
    struct state *to;		/* where it's to */
    struct arc *outchain;	/* *from's outs chain or free chain */
#define	freechain	outchain
    struct arc *inchain;	/* *to's ins chain */
    struct arc *colorchain;	/* color's arc chain */
    struct arc *colorchainRev;	/* back-link in color's arc chain */
};

struct arcbatch {		/* for bulk allocation of arcs */
    struct arcbatch *next;
#define	ABSIZE	10
    struct arc a[ABSIZE];
................................................................................
				 * by children of this state. */
    struct vars *v;		/* simplifies compile error reporting */
    struct nfa *parent;		/* parent NFA, if any */
};

/*
 * definitions for compacted NFA











 */

struct carc {
    color co;			/* COLORLESS is list terminator */
    int to;			/* state number */
};

struct cnfa {
    int nstates;		/* number of states */
    int ncolors;		/* number of colors */
    int flags;
#define	HASLACONS	01	/* uses lookahead constraints */
    int pre;			/* setup state number */
    int post;			/* teardown state number */
    color bos[2];		/* colors, if any, assigned to BOS and BOL */
    color eos[2];		/* colors, if any, assigned to EOS and EOL */


    struct carc **states;	/* vector of pointers to outarc lists */

    struct carc *arcs;		/* the area for the lists */
};
#define	ZAPCNFA(cnfa)	((cnfa).nstates = 0)
#define	NULLCNFA(cnfa)	((cnfa).nstates == 0)

/*
 * Used to limit the maximum NFA size to something sane. [Bug 1810264]
................................................................................

#ifndef REG_MAX_STATES
#   define REG_MAX_STATES	100000
#endif

/*
 * subexpression tree


















 */

struct subre {
    char op;			/* '|', '.' (concat), 'b' (backref), '(',
				 * '=' */
    char flags;
#define	LONGER	01		/* prefers longer match */
#define	SHORTER	02		/* prefers shorter match */
#define	MIXED	04		/* mixed preference below */
#define	CAP	010		/* capturing parens below */
#define	BACKR	020		/* back reference below */
#define	INUSE	0100		/* in use in final tree */
................................................................................
#define	LMIX(f)	((f)<<2)	/* LONGER -> MIXED */
#define	SMIX(f)	((f)<<1)	/* SHORTER -> MIXED */
#define	UP(f)	(((f)&~NOPROP) | (LMIX(f) & SMIX(f) & MIXED))
#define	MESSY(f)	((f)&(MIXED|CAP|BACKR))
#define	PREF(f)	((f)&NOPROP)
#define	PREF2(f1, f2)	((PREF(f1) != 0) ? PREF(f1) : PREF(f2))
#define	COMBINE(f1, f2)	(UP((f1)|(f2)) | PREF2(f1, f2))
    short retry;		/* index into retry memory */
    int subno;			/* subexpression number (for 'b' and '(') */
    short min;			/* min repetitions, for backref only */
    short max;			/* max repetitions, for backref only */
    struct subre *left;		/* left child, if any (also freelist chain) */
    struct subre *right;	/* right child, if any */
    struct state *begin;	/* outarcs from here... */
    struct state *end;		/* ...ending in inarcs here */
    struct cnfa cnfa;		/* compacted NFA, if any */
    struct subre *chain;	/* for bookkeeping and error cleanup */
};
................................................................................
    int magic;
#define	GUTSMAGIC	0xfed9
    int cflags;			/* copy of compile flags */
    long info;			/* copy of re_info */
    size_t nsub;		/* copy of re_nsub */
    struct subre *tree;
    struct cnfa search;		/* for fast preliminary search */
    int ntree;
    struct colormap cmap;
    int FUNCPTR(compare, (const chr *, const chr *, size_t));
    struct subre *lacons;	/* lookahead-constraint vector */
    int nlacons;		/* size of lacons */
};

/*






>
|
>
>
>
>
>
>







 







|
<



|

|
|







 







>
>
>
>
>
>
>
>
>
>
>




|











>
>

>







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>



|
<







 







|

|
|







 







|







182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
...
245
246
247
248
249
250
251
252

253
254
255
256
257
258
259
260
261
262
263
264
265
266
...
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
...
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373

374
375
376
377
378
379
380
...
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
...
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
    int flags;
#define	FREECOL	01		/* currently free */
#define	PSEUDO	02		/* pseudocolor, no real chars */
#define	UNUSEDCOLOR(cd)	((cd)->flags&FREECOL)
    union tree *block;		/* block of solid color, if any */
};

/*
 * The color map itself
 *
 * Much of the data in the colormap struct is only used at compile time.
 * However, the bulk of the space usage is in the "tree" structure, so it's
 * not clear that there's much point in converting the rest to a more compact
 * form when compilation is finished.
 */
struct colormap {
    int magic;
#define	CMMAGIC	0x876
    struct vars *v;		/* for compile error reporting */
    size_t ncds;		/* number of colordescs */
    size_t max;			/* highest in use */
    color free;			/* beginning of free chain (if non-0) */
................................................................................
 * Having a "from" pointer within each arc may seem redundant, but it saves a
 * lot of hassle.
 */

struct state;

struct arc {
    int type;			/* 0 if free, else an NFA arc type code */

    color co;
    struct state *from;		/* where it's from (and contained within) */
    struct state *to;		/* where it's to */
    struct arc *outchain;	/* link in *from's outs chain or free chain */
#define	freechain	outchain
    struct arc *inchain;	/* link in *to's ins chain */
    struct arc *colorchain;	/* link in color's arc chain */
    struct arc *colorchainRev;	/* back-link in color's arc chain */
};

struct arcbatch {		/* for bulk allocation of arcs */
    struct arcbatch *next;
#define	ABSIZE	10
    struct arc a[ABSIZE];
................................................................................
				 * by children of this state. */
    struct vars *v;		/* simplifies compile error reporting */
    struct nfa *parent;		/* parent NFA, if any */
};

/*
 * definitions for compacted NFA
 *
 * The main space savings in a compacted NFA is from making the arcs as small
 * as possible.  We store only the transition color and next-state number for
 * each arc.  The list of out arcs for each state is an array beginning at
 * cnfa.states[statenumber], and terminated by a dummy carc struct with
 * co == COLORLESS.
 *
 * The non-dummy carc structs are of two types: plain arcs and LACON arcs.
 * Plain arcs just store the transition color number as "co".  LACON arcs
 * store the lookahead constraint number plus cnfa.ncolors as "co".  LACON
 * arcs can be distinguished from plain by testing for co >= cnfa.ncolors.
 */

struct carc {
    color co;			/* COLORLESS is list terminator */
    int to;			/* next-state number */
};

struct cnfa {
    int nstates;		/* number of states */
    int ncolors;		/* number of colors */
    int flags;
#define	HASLACONS	01	/* uses lookahead constraints */
    int pre;			/* setup state number */
    int post;			/* teardown state number */
    color bos[2];		/* colors, if any, assigned to BOS and BOL */
    color eos[2];		/* colors, if any, assigned to EOS and EOL */
    char *stflags;		/* vector of per-state flags bytes */
#define CNFA_NOPROGRESS	01	/* flag bit for a no-progress state */
    struct carc **states;	/* vector of pointers to outarc lists */
    /* states[n] are pointers into a single malloc'd array of arcs */
    struct carc *arcs;		/* the area for the lists */
};
#define	ZAPCNFA(cnfa)	((cnfa).nstates = 0)
#define	NULLCNFA(cnfa)	((cnfa).nstates == 0)

/*
 * Used to limit the maximum NFA size to something sane. [Bug 1810264]
................................................................................

#ifndef REG_MAX_STATES
#   define REG_MAX_STATES	100000
#endif

/*
 * subexpression tree
 *
 * "op" is one of:
 *	'='  plain regex without interesting substructure (implemented as DFA)
 *	'b'  back-reference (has no substructure either)
 *	'('  capture node: captures the match of its single child
 *	'.'  concatenation: matches a match for left, then a match for right
 *	'|'  alternation: matches a match for left or a match for right
 *	'*'  iteration: matches some number of matches of its single child
 *
 * Note: the right child of an alternation must be another alternation or
 * NULL; hence, an N-way branch requires N alternation nodes, not N-1 as you
 * might expect.  This could stand to be changed.  Actually I'd rather see
 * a single alternation node with N children, but that will take revising
 * the representation of struct subre.
 *
 * Note: when a backref is directly quantified, we stick the min/max counts
 * into the backref rather than plastering an iteration node on top.  This is
 * for efficiency: there is no need to search for possible division points.
 */

struct subre {
    char op;			/* see type codes above */

    char flags;
#define	LONGER	01		/* prefers longer match */
#define	SHORTER	02		/* prefers shorter match */
#define	MIXED	04		/* mixed preference below */
#define	CAP	010		/* capturing parens below */
#define	BACKR	020		/* back reference below */
#define	INUSE	0100		/* in use in final tree */
................................................................................
#define	LMIX(f)	((f)<<2)	/* LONGER -> MIXED */
#define	SMIX(f)	((f)<<1)	/* SHORTER -> MIXED */
#define	UP(f)	(((f)&~NOPROP) | (LMIX(f) & SMIX(f) & MIXED))
#define	MESSY(f)	((f)&(MIXED|CAP|BACKR))
#define	PREF(f)	((f)&NOPROP)
#define	PREF2(f1, f2)	((PREF(f1) != 0) ? PREF(f1) : PREF(f2))
#define	COMBINE(f1, f2)	(UP((f1)|(f2)) | PREF2(f1, f2))
    short id;			/* ID of subre (1..ntree-1) */
    int subno;			/* subexpression number (for 'b' and '(') */
    short min;			/* min repetitions for iteration or backref */
    short max;			/* max repetitions for iteration or backref */
    struct subre *left;		/* left child, if any (also freelist chain) */
    struct subre *right;	/* right child, if any */
    struct state *begin;	/* outarcs from here... */
    struct state *end;		/* ...ending in inarcs here */
    struct cnfa cnfa;		/* compacted NFA, if any */
    struct subre *chain;	/* for bookkeeping and error cleanup */
};
................................................................................
    int magic;
#define	GUTSMAGIC	0xfed9
    int cflags;			/* copy of compile flags */
    long info;			/* copy of re_info */
    size_t nsub;		/* copy of re_nsub */
    struct subre *tree;
    struct cnfa search;		/* for fast preliminary search */
    int ntree;			/* number of subre's, plus one */
    struct colormap cmap;
    int FUNCPTR(compare, (const chr *, const chr *, size_t));
    struct subre *lacons;	/* lookahead-constraint vector */
    int nlacons;		/* size of lacons */
};

/*

Changes to generic/tcl.decls.

33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
...
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
...
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
}
declare 1 {
    CONST84_RETURN char *Tcl_PkgRequireEx(Tcl_Interp *interp,
	    const char *name, const char *version, int exact,
	    void *clientDataPtr)
}
declare 2 {
    void Tcl_Panic(const char *format, ...)
}
declare 3 {
    char *Tcl_Alloc(unsigned int size)
}
declare 4 {
    void Tcl_Free(char *ptr)
}
................................................................................
declare 228 {
    void Tcl_SetErrorCode(Tcl_Interp *interp, ...)
}
declare 229 {
    void Tcl_SetMaxBlockTime(const Tcl_Time *timePtr)
}
declare 230 {
    void Tcl_SetPanicProc(Tcl_PanicProc *panicProc)
}
declare 231 {
    int Tcl_SetRecursionLimit(Tcl_Interp *interp, int depth)
}
declare 232 {
    void Tcl_SetResult(Tcl_Interp *interp, char *result,
	    Tcl_FreeProc *freeProc)
................................................................................
declare 276 {
    int  Tcl_VarEvalVA(Tcl_Interp *interp, va_list argList)
}
declare 277 {
    Tcl_Pid Tcl_WaitPid(Tcl_Pid pid, int *statPtr, int options)
}
declare 278 {
    void Tcl_PanicVA(const char *format, va_list argList)
}
declare 279 {
    void Tcl_GetVersion(int *major, int *minor, int *patchLevel, int *type)
}
declare 280 {
    void Tcl_InitMemory(Tcl_Interp *interp)
}






|







 







|







 







|







33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
...
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
...
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
}
declare 1 {
    CONST84_RETURN char *Tcl_PkgRequireEx(Tcl_Interp *interp,
	    const char *name, const char *version, int exact,
	    void *clientDataPtr)
}
declare 2 {
    TCL_NORETURN void Tcl_Panic(const char *format, ...)
}
declare 3 {
    char *Tcl_Alloc(unsigned int size)
}
declare 4 {
    void Tcl_Free(char *ptr)
}
................................................................................
declare 228 {
    void Tcl_SetErrorCode(Tcl_Interp *interp, ...)
}
declare 229 {
    void Tcl_SetMaxBlockTime(const Tcl_Time *timePtr)
}
declare 230 {
    void Tcl_SetPanicProc(TCL_NORETURN1 Tcl_PanicProc *panicProc)
}
declare 231 {
    int Tcl_SetRecursionLimit(Tcl_Interp *interp, int depth)
}
declare 232 {
    void Tcl_SetResult(Tcl_Interp *interp, char *result,
	    Tcl_FreeProc *freeProc)
................................................................................
declare 276 {
    int  Tcl_VarEvalVA(Tcl_Interp *interp, va_list argList)
}
declare 277 {
    Tcl_Pid Tcl_WaitPid(Tcl_Pid pid, int *statPtr, int options)
}
declare 278 {
    TCL_NORETURN void Tcl_PanicVA(const char *format, va_list argList)
}
declare 279 {
    void Tcl_GetVersion(int *major, int *minor, int *patchLevel, int *type)
}
declare 280 {
    void Tcl_InitMemory(Tcl_Interp *interp)
}

Changes to generic/tcl.h.

139
140
141
142
143
144
145






146
147






148
149
150
151
152
153
154
#ifndef TCL_NO_DEPRECATED
#    define TCL_VARARGS(type, name) (type name, ...)
#    define TCL_VARARGS_DEF(type, name) (type name, ...)
#    define TCL_VARARGS_START(type, name, list) (va_start(list, name), name)
#endif
#if defined(__GNUC__) && (__GNUC__ > 2)
#   define TCL_FORMAT_PRINTF(a,b) __attribute__ ((__format__ (__printf__, a, b)))






#else
#   define TCL_FORMAT_PRINTF(a,b)






#endif

/*
 * Allow a part of Tcl's API to be explicitly marked as deprecated.
 *
 * Used to make TIP 330/336 generate moans even if people use the
 * compatibility macros. Change your code, guys! We won't support you forever.






>
>
>
>
>
>


>
>
>
>
>
>







139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#ifndef TCL_NO_DEPRECATED
#    define TCL_VARARGS(type, name) (type name, ...)
#    define TCL_VARARGS_DEF(type, name) (type name, ...)
#    define TCL_VARARGS_START(type, name, list) (va_start(list, name), name)
#endif
#if defined(__GNUC__) && (__GNUC__ > 2)
#   define TCL_FORMAT_PRINTF(a,b) __attribute__ ((__format__ (__printf__, a, b)))
#   define TCL_NORETURN __attribute__ ((noreturn))
#   if defined(BUILD_tcl) || defined(BUILD_tk)
#	define TCL_NORETURN1 __attribute__ ((noreturn))
#   else
#	define TCL_NORETURN1 /* nothing */
#   endif
#else
#   define TCL_FORMAT_PRINTF(a,b)
#   if defined(_MSC_VER) && (_MSC_VER >= 1310)
#	define TCL_NORETURN _declspec(noreturn)
#   else
#	define TCL_NORETURN /* nothing */
#   endif
#   define TCL_NORETURN1 /* nothing */
#endif

/*
 * Allow a part of Tcl's API to be explicitly marked as deprecated.
 *
 * Used to make TIP 330/336 generate moans even if people use the
 * compatibility macros. Change your code, guys! We won't support you forever.

Changes to generic/tclDecls.h.

44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
...
682
683
684
685
686
687
688
689

690
691
692
693
694
695
696
...
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
....
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
....
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
....
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
				const char *name, const char *version,
				const void *clientData);
/* 1 */
EXTERN CONST84_RETURN char * Tcl_PkgRequireEx(Tcl_Interp *interp,
				const char *name, const char *version,
				int exact, void *clientDataPtr);
/* 2 */
EXTERN void		Tcl_Panic(const char *format, ...) TCL_FORMAT_PRINTF(1, 2);
/* 3 */
EXTERN char *		Tcl_Alloc(unsigned int size);
/* 4 */
EXTERN void		Tcl_Free(char *ptr);
/* 5 */
EXTERN char *		Tcl_Realloc(char *ptr, unsigned int size);
/* 6 */
................................................................................
/* 227 */
EXTERN void		Tcl_SetErrno(int err);
/* 228 */
EXTERN void		Tcl_SetErrorCode(Tcl_Interp *interp, ...);
/* 229 */
EXTERN void		Tcl_SetMaxBlockTime(const Tcl_Time *timePtr);
/* 230 */
EXTERN void		Tcl_SetPanicProc(Tcl_PanicProc *panicProc);

/* 231 */
EXTERN int		Tcl_SetRecursionLimit(Tcl_Interp *interp, int depth);
/* 232 */
EXTERN void		Tcl_SetResult(Tcl_Interp *interp, char *result,
				Tcl_FreeProc *freeProc);
/* 233 */
EXTERN int		Tcl_SetServiceMode(int mode);
................................................................................
EXTERN void		Tcl_SetErrorCodeVA(Tcl_Interp *interp,
				va_list argList);
/* 276 */
EXTERN int		Tcl_VarEvalVA(Tcl_Interp *interp, va_list argList);
/* 277 */
EXTERN Tcl_Pid		Tcl_WaitPid(Tcl_Pid pid, int *statPtr, int options);
/* 278 */
EXTERN void		Tcl_PanicVA(const char *format, va_list argList);
/* 279 */
EXTERN void		Tcl_GetVersion(int *major, int *minor,
				int *patchLevel, int *type);
/* 280 */
EXTERN void		Tcl_InitMemory(Tcl_Interp *interp);
/* 281 */
EXTERN Tcl_Channel	Tcl_StackChannel(Tcl_Interp *interp,
................................................................................

typedef struct TclStubs {
    int magic;
    const TclStubHooks *hooks;

    int (*tcl_PkgProvideEx) (Tcl_Interp *interp, const char *name, const char *version, const void *clientData); /* 0 */
    CONST84_RETURN char * (*tcl_PkgRequireEx) (Tcl_Interp *interp, const char *name, const char *version, int exact, void *clientDataPtr); /* 1 */
    void (*tcl_Panic) (const char *format, ...) TCL_FORMAT_PRINTF(1, 2); /* 2 */
    char * (*tcl_Alloc) (unsigned int size); /* 3 */
    void (*tcl_Free) (char *ptr); /* 4 */
    char * (*tcl_Realloc) (char *ptr, unsigned int size); /* 5 */
    char * (*tcl_DbCkalloc) (unsigned int size, const char *file, int line); /* 6 */
    void (*tcl_DbCkfree) (char *ptr, const char *file, int line); /* 7 */
    char * (*tcl_DbCkrealloc) (char *ptr, unsigned int size, const char *file, int line); /* 8 */
#if !defined(_WIN32) && !defined(MAC_OSX_TCL) /* UNIX */
................................................................................
    void (*tcl_SetAssocData) (Tcl_Interp *interp, const char *name, Tcl_InterpDeleteProc *proc, ClientData clientData); /* 223 */
    void (*tcl_SetChannelBufferSize) (Tcl_Channel chan, int sz); /* 224 */
    int (*tcl_SetChannelOption) (Tcl_Interp *interp, Tcl_Channel chan, const char *optionName, const char *newValue); /* 225 */
    int (*tcl_SetCommandInfo) (Tcl_Interp *interp, const char *cmdName, const Tcl_CmdInfo *infoPtr); /* 226 */
    void (*tcl_SetErrno) (int err); /* 227 */
    void (*tcl_SetErrorCode) (Tcl_Interp *interp, ...); /* 228 */
    void (*tcl_SetMaxBlockTime) (const Tcl_Time *timePtr); /* 229 */
    void (*tcl_SetPanicProc) (Tcl_PanicProc *panicProc); /* 230 */
    int (*tcl_SetRecursionLimit) (Tcl_Interp *interp, int depth); /* 231 */
    void (*tcl_SetResult) (Tcl_Interp *interp, char *result, Tcl_FreeProc *freeProc); /* 232 */
    int (*tcl_SetServiceMode) (int mode); /* 233 */
    void (*tcl_SetObjErrorCode) (Tcl_Interp *interp, Tcl_Obj *errorObjPtr); /* 234 */
    void (*tcl_SetObjResult) (Tcl_Interp *interp, Tcl_Obj *resultObjPtr); /* 235 */
    void (*tcl_SetStdChannel) (Tcl_Channel channel, int type); /* 236 */
    CONST84_RETURN char * (*tcl_SetVar) (Tcl_Interp *interp, const char *varName, const char *newValue, int flags); /* 237 */
................................................................................
    CONST84_RETURN char * (*tcl_PkgPresent) (Tcl_Interp *interp, const char *name, const char *version, int exact); /* 271 */
    CONST84_RETURN char * (*tcl_PkgPresentEx) (Tcl_Interp *interp, const char *name, const char *version, int exact, void *clientDataPtr); /* 272 */
    int (*tcl_PkgProvide) (Tcl_Interp *interp, const char *name, const char *version); /* 273 */
    CONST84_RETURN char * (*tcl_PkgRequire) (Tcl_Interp *interp, const char *name, const char *version, int exact); /* 274 */
    void (*tcl_SetErrorCodeVA) (Tcl_Interp *interp, va_list argList); /* 275 */
    int (*tcl_VarEvalVA) (Tcl_Interp *interp, va_list argList); /* 276 */
    Tcl_Pid (*tcl_WaitPid) (Tcl_Pid pid, int *statPtr, int options); /* 277 */
    void (*tcl_PanicVA) (const char *format, va_list argList); /* 278 */
    void (*tcl_GetVersion) (int *major, int *minor, int *patchLevel, int *type); /* 279 */
    void (*tcl_InitMemory) (Tcl_Interp *interp); /* 280 */
    Tcl_Channel (*tcl_StackChannel) (Tcl_Interp *interp, const Tcl_ChannelType *typePtr, ClientData instanceData, int mask, Tcl_Channel prevChan); /* 281 */
    int (*tcl_UnstackChannel) (Tcl_Interp *interp, Tcl_Channel chan); /* 282 */
    Tcl_Channel (*tcl_GetStackedChannel) (Tcl_Channel chan); /* 283 */
    void (*tcl_SetMainLoop) (Tcl_MainLoopProc *proc); /* 284 */
    void (*reserved285)(void);






|







 







|
>







 







|







 







|







 







|







 







|







44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
...
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
...
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
....
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
....
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
....
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
				const char *name, const char *version,
				const void *clientData);
/* 1 */
EXTERN CONST84_RETURN char * Tcl_PkgRequireEx(Tcl_Interp *interp,
				const char *name, const char *version,
				int exact, void *clientDataPtr);
/* 2 */
EXTERN TCL_NORETURN void Tcl_Panic(const char *format, ...) TCL_FORMAT_PRINTF(1, 2);
/* 3 */
EXTERN char *		Tcl_Alloc(unsigned int size);
/* 4 */
EXTERN void		Tcl_Free(char *ptr);
/* 5 */
EXTERN char *		Tcl_Realloc(char *ptr, unsigned int size);
/* 6 */
................................................................................
/* 227 */
EXTERN void		Tcl_SetErrno(int err);
/* 228 */
EXTERN void		Tcl_SetErrorCode(Tcl_Interp *interp, ...);
/* 229 */
EXTERN void		Tcl_SetMaxBlockTime(const Tcl_Time *timePtr);
/* 230 */
EXTERN void		Tcl_SetPanicProc(
				TCL_NORETURN1 Tcl_PanicProc *panicProc);
/* 231 */
EXTERN int		Tcl_SetRecursionLimit(Tcl_Interp *interp, int depth);
/* 232 */
EXTERN void		Tcl_SetResult(Tcl_Interp *interp, char *result,
				Tcl_FreeProc *freeProc);
/* 233 */
EXTERN int		Tcl_SetServiceMode(int mode);
................................................................................
EXTERN void		Tcl_SetErrorCodeVA(Tcl_Interp *interp,
				va_list argList);
/* 276 */
EXTERN int		Tcl_VarEvalVA(Tcl_Interp *interp, va_list argList);
/* 277 */
EXTERN Tcl_Pid		Tcl_WaitPid(Tcl_Pid pid, int *statPtr, int options);
/* 278 */
EXTERN TCL_NORETURN void Tcl_PanicVA(const char *format, va_list argList);
/* 279 */
EXTERN void		Tcl_GetVersion(int *major, int *minor,
				int *patchLevel, int *type);
/* 280 */
EXTERN void		Tcl_InitMemory(Tcl_Interp *interp);
/* 281 */
EXTERN Tcl_Channel	Tcl_StackChannel(Tcl_Interp *interp,
................................................................................

typedef struct TclStubs {
    int magic;
    const TclStubHooks *hooks;

    int (*tcl_PkgProvideEx) (Tcl_Interp *interp, const char *name, const char *version, const void *clientData); /* 0 */
    CONST84_RETURN char * (*tcl_PkgRequireEx) (Tcl_Interp *interp, const char *name, const char *version, int exact, void *clientDataPtr); /* 1 */
    TCL_NORETURN1 void (*tcl_Panic) (const char *format, ...) TCL_FORMAT_PRINTF(1, 2); /* 2 */
    char * (*tcl_Alloc) (unsigned int size); /* 3 */
    void (*tcl_Free) (char *ptr); /* 4 */
    char * (*tcl_Realloc) (char *ptr, unsigned int size); /* 5 */
    char * (*tcl_DbCkalloc) (unsigned int size, const char *file, int line); /* 6 */
    void (*tcl_DbCkfree) (char *ptr, const char *file, int line); /* 7 */
    char * (*tcl_DbCkrealloc) (char *ptr, unsigned int size, const char *file, int line); /* 8 */
#if !defined(_WIN32) && !defined(MAC_OSX_TCL) /* UNIX */
................................................................................
    void (*tcl_SetAssocData) (Tcl_Interp *interp, const char *name, Tcl_InterpDeleteProc *proc, ClientData clientData); /* 223 */
    void (*tcl_SetChannelBufferSize) (Tcl_Channel chan, int sz); /* 224 */
    int (*tcl_SetChannelOption) (Tcl_Interp *interp, Tcl_Channel chan, const char *optionName, const char *newValue); /* 225 */
    int (*tcl_SetCommandInfo) (Tcl_Interp *interp, const char *cmdName, const Tcl_CmdInfo *infoPtr); /* 226 */
    void (*tcl_SetErrno) (int err); /* 227 */
    void (*tcl_SetErrorCode) (Tcl_Interp *interp, ...); /* 228 */
    void (*tcl_SetMaxBlockTime) (const Tcl_Time *timePtr); /* 229 */
    void (*tcl_SetPanicProc) (TCL_NORETURN1 Tcl_PanicProc *panicProc); /* 230 */
    int (*tcl_SetRecursionLimit) (Tcl_Interp *interp, int depth); /* 231 */
    void (*tcl_SetResult) (Tcl_Interp *interp, char *result, Tcl_FreeProc *freeProc); /* 232 */
    int (*tcl_SetServiceMode) (int mode); /* 233 */
    void (*tcl_SetObjErrorCode) (Tcl_Interp *interp, Tcl_Obj *errorObjPtr); /* 234 */
    void (*tcl_SetObjResult) (Tcl_Interp *interp, Tcl_Obj *resultObjPtr); /* 235 */
    void (*tcl_SetStdChannel) (Tcl_Channel channel, int type); /* 236 */
    CONST84_RETURN char * (*tcl_SetVar) (Tcl_Interp *interp, const char *varName, const char *newValue, int flags); /* 237 */
................................................................................
    CONST84_RETURN char * (*tcl_PkgPresent) (Tcl_Interp *interp, const char *name, const char *version, int exact); /* 271 */
    CONST84_RETURN char * (*tcl_PkgPresentEx) (Tcl_Interp *interp, const char *name, const char *version, int exact, void *clientDataPtr); /* 272 */
    int (*tcl_PkgProvide) (Tcl_Interp *interp, const char *name, const char *version); /* 273 */
    CONST84_RETURN char * (*tcl_PkgRequire) (Tcl_Interp *interp, const char *name, const char *version, int exact); /* 274 */
    void (*tcl_SetErrorCodeVA) (Tcl_Interp *interp, va_list argList); /* 275 */
    int (*tcl_VarEvalVA) (Tcl_Interp *interp, va_list argList); /* 276 */
    Tcl_Pid (*tcl_WaitPid) (Tcl_Pid pid, int *statPtr, int options); /* 277 */
    TCL_NORETURN1 void (*tcl_PanicVA) (const char *format, va_list argList); /* 278 */
    void (*tcl_GetVersion) (int *major, int *minor, int *patchLevel, int *type); /* 279 */
    void (*tcl_InitMemory) (Tcl_Interp *interp); /* 280 */
    Tcl_Channel (*tcl_StackChannel) (Tcl_Interp *interp, const Tcl_ChannelType *typePtr, ClientData instanceData, int mask, Tcl_Channel prevChan); /* 281 */
    int (*tcl_UnstackChannel) (Tcl_Interp *interp, Tcl_Channel chan); /* 282 */
    Tcl_Channel (*tcl_GetStackedChannel) (Tcl_Channel chan); /* 283 */
    void (*tcl_SetMainLoop) (Tcl_MainLoopProc *proc); /* 284 */
    void (*reserved285)(void);

Changes to generic/tclHash.c.

322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
	for (hPtr = tablePtr->buckets[index]; hPtr != NULL;
		hPtr = hPtr->nextPtr) {
#if TCL_HASH_KEY_STORE_HASH
	    if (hash != PTR2UINT(hPtr->hash)) {
		continue;
	    }
#endif
	    if (compareKeysProc((void *) key, hPtr)) {
		if (newPtr) {
		    *newPtr = 0;
		}
		return hPtr;
	    }
	}
    } else {






|







322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
	for (hPtr = tablePtr->buckets[index]; hPtr != NULL;
		hPtr = hPtr->nextPtr) {
#if TCL_HASH_KEY_STORE_HASH
	    if (hash != PTR2UINT(hPtr->hash)) {
		continue;
	    }
#endif
	    if (((void *) key == hPtr) || compareKeysProc((void *) key, hPtr)) {
		if (newPtr) {
		    *newPtr = 0;
		}
		return hPtr;
	    }
	}
    } else {

Changes to generic/tclObj.c.

3967
3968
3969
3970
3971
3972
3973
3974
3975
3976
3977

3978
3979
3980
3981
3982
3983
3984
3985
3986
    Tcl_Obj *objPtr1 = keyPtr;
    Tcl_Obj *objPtr2 = (Tcl_Obj *) hPtr->key.oneWordValue;
    register const char *p1, *p2;
    register int l1, l2;

    /*
     * If the object pointers are the same then they match.
     */

    if (objPtr1 == objPtr2) {
	return 1;

    }

    /*
     * Don't use Tcl_GetStringFromObj as it would prevent l1 and l2 being
     * in a register.
     */

    p1 = TclGetString(objPtr1);
    l1 = objPtr1->length;






|
|
|
<
>
|
<







3967
3968
3969
3970
3971
3972
3973
3974
3975
3976

3977
3978

3979
3980
3981
3982
3983
3984
3985
    Tcl_Obj *objPtr1 = keyPtr;
    Tcl_Obj *objPtr2 = (Tcl_Obj *) hPtr->key.oneWordValue;
    register const char *p1, *p2;
    register int l1, l2;

    /*
     * If the object pointers are the same then they match.
     * OPT: this comparison was moved to the caller
     
       if (objPtr1 == objPtr2) return 1;

    */
    

    /*
     * Don't use Tcl_GetStringFromObj as it would prevent l1 and l2 being
     * in a register.
     */

    p1 = TclGetString(objPtr1);
    l1 = objPtr1->length;

Changes to generic/tclPanic.c.

11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
..
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
 *
 * See the file "license.terms" for information on usage and redistribution of
 * this file, and for a DISCLAIMER OF ALL WARRANTIES.
 */

#include "tclInt.h"
#if defined(_WIN32) || defined(__CYGWIN__)
    MODULE_SCOPE void tclWinDebugPanic(const char *format, ...);
#endif

/*
 * The panicProc variable contains a pointer to an application specific panic
 * procedure.
 */

#if defined(__CYGWIN__)
static Tcl_PanicProc *panicProc = tclWinDebugPanic;
#else
static Tcl_PanicProc *panicProc = NULL;
#endif
 
/*
 *----------------------------------------------------------------------
 *
 * Tcl_SetPanicProc --
 *
................................................................................
 *	Sets the panicProc variable.
 *
 *----------------------------------------------------------------------
 */

void
Tcl_SetPanicProc(
    Tcl_PanicProc *proc)
{
#if defined(_WIN32)
    /* tclWinDebugPanic only installs if there is no panicProc yet. */
    if ((proc != tclWinDebugPanic) || (panicProc == NULL))
#elif defined(__CYGWIN__)
    if (proc == NULL)
	panicProc = tclWinDebugPanic;






|








|

|







 







|







11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
..
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
 *
 * See the file "license.terms" for information on usage and redistribution of
 * this file, and for a DISCLAIMER OF ALL WARRANTIES.
 */

#include "tclInt.h"
#if defined(_WIN32) || defined(__CYGWIN__)
    MODULE_SCOPE TCL_NORETURN void tclWinDebugPanic(const char *format, ...);
#endif

/*
 * The panicProc variable contains a pointer to an application specific panic
 * procedure.
 */

#if defined(__CYGWIN__)
static TCL_NORETURN Tcl_PanicProc *panicProc = tclWinDebugPanic;
#else
static TCL_NORETURN1 Tcl_PanicProc *panicProc = NULL;
#endif
 
/*
 *----------------------------------------------------------------------
 *
 * Tcl_SetPanicProc --
 *
................................................................................
 *	Sets the panicProc variable.
 *
 *----------------------------------------------------------------------
 */

void
Tcl_SetPanicProc(
    TCL_NORETURN1 Tcl_PanicProc *proc)
{
#if defined(_WIN32)
    /* tclWinDebugPanic only installs if there is no panicProc yet. */
    if ((proc != tclWinDebugPanic) || (panicProc == NULL))
#elif defined(__CYGWIN__)
    if (proc == NULL)
	panicProc = tclWinDebugPanic;

Changes to generic/tclVar.c.

6360
6361
6362
6363
6364
6365
6366
6367
6368
6369
6370

6371
6372
6373
6374
6375
6376
6377
6378
6379
    Tcl_Obj *objPtr1 = keyPtr;
    Tcl_Obj *objPtr2 = hPtr->key.objPtr;
    register const char *p1, *p2;
    register int l1, l2;

    /*
     * If the object pointers are the same then they match.
     */

    if (objPtr1 == objPtr2) {
	return 1;

    }

    /*
     * Don't use Tcl_GetStringFromObj as it would prevent l1 and l2 being in a
     * register.
     */

    p1 = TclGetString(objPtr1);
    l1 = objPtr1->length;






|
|
|
<
>
|
<







6360
6361
6362
6363
6364
6365
6366
6367
6368
6369

6370
6371

6372
6373
6374
6375
6376
6377
6378
    Tcl_Obj *objPtr1 = keyPtr;
    Tcl_Obj *objPtr2 = hPtr->key.objPtr;
    register const char *p1, *p2;
    register int l1, l2;

    /*
     * If the object pointers are the same then they match.
     * OPT: this comparison was moved to the caller
     
       if (objPtr1 == objPtr2) return 1;

    */
    

    /*
     * Don't use Tcl_GetStringFromObj as it would prevent l1 and l2 being in a
     * register.
     */

    p1 = TclGetString(objPtr1);
    l1 = objPtr1->length;

Changes to tests/reg.test.

665
666
667
668
669
670
671
672






673
674
675
676
677
678
679
...
792
793
794
795
796
797
798

799
800
801
802
803
804
805
...
844
845
846
847
848
849
850

851
852
853
854
855
856
857
expectMatch	14.16 RP	{a([bc])\1*}	ab	ab	b
expectMatch	14.17 RP	{a([bc])(\1*)}	ab	ab	b	""
expectError	14.18 -		{a((b)\1)}	ESUBREG
expectError	14.19 -		{a(b)c\2}	ESUBREG
expectMatch	14.20 bR	{a\(b*\)c\1}	abbcbb	abbcbb	bb
expectMatch	14.21 RP	{^([bc])\1*$}	bbb	bbb	b
expectMatch	14.22 RP	{^([bc])\1*$}	ccc	ccc	c
knownBug expectNomatch 14.23 R	{^([bc])\1*$}	bcb








doing 15 "octal escapes vs back references"
# initial zero is always octal
expectMatch	15.1  MP	"a\\010b"	"a\bb"	"a\bb"
expectMatch	15.2  MP	"a\\0070b"	"a\0070b"	"a\0070b"
expectMatch	15.3  MP	"a\\07b"	"a\007b"	"a\007b"
................................................................................
expectIndices	21.28 Q		"a(b){2,3}c"	xabbbcy	{1 5}	{4 4}
expectIndices	21.29 Q		"a(b){2,3}c"	xabbcy	{1 4}	{3 3}
expectNomatch	21.30 Q		"a(b){2,3}c"	xabcy
expectMatch	21.31 LP	"\\y(\\w+)\\y"	"-- abc-"	"abc"	"abc"
expectMatch	21.32 -		a((b|c)d+)+	abacdbd	acdbd	bd	b
expectMatch	21.33 N		(.*).*		abc	abc	abc
expectMatch	21.34 N		(a*)*		bc	""	""



doing 22 "multicharacter collating elements"
# again ugh
expectMatch	22.1  &+L	{a[c]e}		ace	ace
expectNomatch	22.2  &+IL	{a[c]h}		ach
expectMatch	22.3  &+L	{a[[.ch.]]}	ach	ach
................................................................................
expectMatch	24.6  PT	ab??c		abc	abc
expectMatch	24.7  PQT	"ab{2,4}?"	abbbb	abb
expectMatch	24.8  PQT	"ab{2,4}?c"	abbbbc	abbbbc
expectMatch	24.9  -		3z*		123zzzz456	3zzzz
expectMatch	24.10 PT	3z*?		123zzzz456	3
expectMatch	24.11 -		z*4		123zzzz456	zzzz4
expectMatch	24.12 PT	z*?4		123zzzz456	zzzz4



doing 25 "mixed quantifiers"
# this is very incomplete as yet
# should include |
expectMatch	25.1 PNT	{^(.*?)(a*)$}	"xyza"	xyza	xyz	a
expectMatch	25.2 PNT	{^(.*?)(a*)$}	"xyzaa"	xyzaa	xyz	aa






|
>
>
>
>
>
>







 







>







 







>







665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
...
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
...
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
expectMatch	14.16 RP	{a([bc])\1*}	ab	ab	b
expectMatch	14.17 RP	{a([bc])(\1*)}	ab	ab	b	""
expectError	14.18 -		{a((b)\1)}	ESUBREG
expectError	14.19 -		{a(b)c\2}	ESUBREG
expectMatch	14.20 bR	{a\(b*\)c\1}	abbcbb	abbcbb	bb
expectMatch	14.21 RP	{^([bc])\1*$}	bbb	bbb	b
expectMatch	14.22 RP	{^([bc])\1*$}	ccc	ccc	c
expectNomatch	14.23 RP	{^([bc])\1*$}	bcb
expectMatch	14.24 LRP	{^(\w+)( \1)+$}	{abc abc abc} {abc abc abc} abc { abc}
expectNomatch	14.25 LRP	{^(\w+)( \1)+$}	{abc abd abc}
expectNomatch	14.26 LRP	{^(\w+)( \1)+$}	{abc abc abd}
expectMatch	14.27 RP	{^(.+)( \1)+$}	{abc abc abc} {abc abc abc} abc { abc}
expectNomatch	14.28 RP	{^(.+)( \1)+$}	{abc abd abc}
expectNomatch	14.29 RP	{^(.+)( \1)+$}	{abc abc abd}


doing 15 "octal escapes vs back references"
# initial zero is always octal
expectMatch	15.1  MP	"a\\010b"	"a\bb"	"a\bb"
expectMatch	15.2  MP	"a\\0070b"	"a\0070b"	"a\0070b"
expectMatch	15.3  MP	"a\\07b"	"a\007b"	"a\007b"
................................................................................
expectIndices	21.28 Q		"a(b){2,3}c"	xabbbcy	{1 5}	{4 4}
expectIndices	21.29 Q		"a(b){2,3}c"	xabbcy	{1 4}	{3 3}
expectNomatch	21.30 Q		"a(b){2,3}c"	xabcy
expectMatch	21.31 LP	"\\y(\\w+)\\y"	"-- abc-"	"abc"	"abc"
expectMatch	21.32 -		a((b|c)d+)+	abacdbd	acdbd	bd	b
expectMatch	21.33 N		(.*).*		abc	abc	abc
expectMatch	21.34 N		(a*)*		bc	""	""
expectMatch	21.35 M		{ TO (([a-z0-9._]+|"([^"]+|"")+")+)}	{asd TO foo}	{ TO foo} foo o {}


doing 22 "multicharacter collating elements"
# again ugh
expectMatch	22.1  &+L	{a[c]e}		ace	ace
expectNomatch	22.2  &+IL	{a[c]h}		ach
expectMatch	22.3  &+L	{a[[.ch.]]}	ach	ach
................................................................................
expectMatch	24.6  PT	ab??c		abc	abc
expectMatch	24.7  PQT	"ab{2,4}?"	abbbb	abb
expectMatch	24.8  PQT	"ab{2,4}?c"	abbbbc	abbbbc
expectMatch	24.9  -		3z*		123zzzz456	3zzzz
expectMatch	24.10 PT	3z*?		123zzzz456	3
expectMatch	24.11 -		z*4		123zzzz456	zzzz4
expectMatch	24.12 PT	z*?4		123zzzz456	zzzz4
expectMatch	24.13 PT	{^([^/]+?)(?:/([^/]+?))(?:/([^/]+?))?$}	{foo/bar/baz}	{foo/bar/baz} {foo} {bar} {baz}


doing 25 "mixed quantifiers"
# this is very incomplete as yet
# should include |
expectMatch	25.1 PNT	{^(.*?)(a*)$}	"xyza"	xyza	xyz	a
expectMatch	25.2 PNT	{^(.*?)(a*)$}	"xyzaa"	xyzaa	xyz	aa

Changes to tools/genStubs.tcl.

578
579
580
581
582
583
584


585
586
587
588
589
590
591
    set text "    "
    if {$args eq ""} {
	append text $rtype " *" $lfname "; /* $index */\n"
	return $text
    }
    if {[string range $rtype end-8 end] eq "__stdcall"} {
	append text [string trim [string range $rtype 0 end-9]] " (__stdcall *" $lfname ") "


    } else {
	append text $rtype " (*" $lfname ") "
    }
    set arg1 [lindex $args 0]
    switch -exact $arg1 {
	void {
	    append text "(void)"






>
>







578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
    set text "    "
    if {$args eq ""} {
	append text $rtype " *" $lfname "; /* $index */\n"
	return $text
    }
    if {[string range $rtype end-8 end] eq "__stdcall"} {
	append text [string trim [string range $rtype 0 end-9]] " (__stdcall *" $lfname ") "
    } elseif {[string range $rtype 0 11] eq "TCL_NORETURN"} {
	append text "TCL_NORETURN1 " [string trim [string range $rtype 12 end]] " (*" $lfname ") "
    } else {
	append text $rtype " (*" $lfname ") "
    }
    set arg1 [lindex $args 0]
    switch -exact $arg1 {
	void {
	    append text "(void)"

Changes to win/tclWinError.c.

377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
 *
 * Side effects:
 *	None.
 *
 *----------------------------------------------------------------------
 */

void
tclWinDebugPanic(
    const char *format, ...)
{
#define TCL_MAX_WARN_LEN 1024
    va_list argList;
    va_start(argList, format);







|







377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
 *
 * Side effects:
 *	None.
 *
 *----------------------------------------------------------------------
 */

TCL_NORETURN void
tclWinDebugPanic(
    const char *format, ...)
{
#define TCL_MAX_WARN_LEN 1024
    va_list argList;
    va_start(argList, format);

Changes to win/tclWinFile.c.

168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
...
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
static int		WinIsReserved(const char *path);
static Tcl_Obj *	WinReadLink(const TCHAR *LinkSource);
static Tcl_Obj *	WinReadLinkDirectory(const TCHAR *LinkDirectory);
static int		WinLink(const TCHAR *LinkSource,
			    const TCHAR *LinkTarget, int linkAction);
static int		WinSymLinkDirectory(const TCHAR *LinkDirectory,
			    const TCHAR *LinkTarget);
MODULE_SCOPE void	tclWinDebugPanic(const char *format, ...);
 
/*
 *--------------------------------------------------------------------
 *
 * WinLink --
 *
 *	Make a link from source to target.
................................................................................
 *
 * Side effects:
 *	None.
 *
 *----------------------------------------------------------------------
 */

void
tclWinDebugPanic(
    const char *format, ...)
{
#define TCL_MAX_WARN_LEN 1024
    va_list argList;
    char buf[TCL_MAX_WARN_LEN * TCL_UTF_MAX];
    WCHAR msgString[TCL_MAX_WARN_LEN];






|







 







|







168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
...
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
static int		WinIsReserved(const char *path);
static Tcl_Obj *	WinReadLink(const TCHAR *LinkSource);
static Tcl_Obj *	WinReadLinkDirectory(const TCHAR *LinkDirectory);
static int		WinLink(const TCHAR *LinkSource,
			    const TCHAR *LinkTarget, int linkAction);
static int		WinSymLinkDirectory(const TCHAR *LinkDirectory,
			    const TCHAR *LinkTarget);
MODULE_SCOPE TCL_NORETURN void	tclWinDebugPanic(const char *format, ...);
 
/*
 *--------------------------------------------------------------------
 *
 * WinLink --
 *
 *	Make a link from source to target.
................................................................................
 *
 * Side effects:
 *	None.
 *
 *----------------------------------------------------------------------
 */

TCL_NORETURN void
tclWinDebugPanic(
    const char *format, ...)
{
#define TCL_MAX_WARN_LEN 1024
    va_list argList;
    char buf[TCL_MAX_WARN_LEN * TCL_UTF_MAX];
    WCHAR msgString[TCL_MAX_WARN_LEN];