1 /* NOTE: this is derived from Henry Spencer's regexp code, and should not
2 * confused with the original package (see point 3 below). Thanks, Henry!
5 /* Additional note: this code is very heavily munged from Henry's version
6 * in places. In some spots I've traded clarity for efficiency, so don't
7 * blame Henry for some of the lack of readability.
10 /* $RCSfile: regcomp.c,v $$Revision: 4.0.1.4 $$Date: 91/11/05 22:55:14 $
13 * Revision 4.0.1.4 91/11/05 22:55:14 lwall
16 * Revision 4.0.1.3 91/11/05 18:22:28 lwall
17 * patch11: minimum match length calculation in regexp is now cumulative
18 * patch11: initial .* in pattern had dependency on value of $*
19 * patch11: certain patterns made use of garbage pointers from uncleared memory
20 * patch11: prepared for ctype implementations that don't define isascii()
22 * Revision 4.0.1.2 91/06/07 11:48:24 lwall
23 * patch4: new copyright notice
24 * patch4: /(x+) \1/ incorrectly optimized to not match "xxx xx"
25 * patch4: // wouldn't use previous pattern if it started with a null character
27 * Revision 4.0.1.1 91/04/12 09:04:45 lwall
28 * patch1: random cleanup in cpp namespace
30 * Revision 4.0 91/03/20 01:39:01 lwall
36 * regcomp and regexec -- regsub and regerror are not used in perl
38 * Copyright (c) 1986 by University of Toronto.
39 * Written by Henry Spencer. Not derived from licensed software.
41 * Permission is granted to anyone to use this software for any
42 * purpose on any computer system, and to redistribute it freely,
43 * subject to the following restrictions:
45 * 1. The author is not responsible for the consequences of use of
46 * this software, no matter how awful, even if they arise
49 * 2. The origin of this software must not be misrepresented, either
50 * by explicit claim or by omission.
52 * 3. Altered versions must be plainly marked as such, and must not
53 * be misrepresented as being the original software.
56 **** Alterations to Henry's code are...
58 **** Copyright (c) 1991, Larry Wall
60 **** You may distribute under the terms of either the GNU General Public
61 **** License or the Artistic License, as specified in the README file.
64 * Beware that some of this code is subtly aware of the way operator
65 * precedence is structured in regular expressions. Serious changes in
66 * regular-expression syntax might require a total rethink.
74 # if defined(BUGGY_MSC6)
75 /* MSC 6.00A breaks on op/regexp.t test 85 unless we turn this off */
76 # pragma optimize("a",off)
77 /* But MSC 6.00A is happy with 'w', for aliases only across function calls*/
78 # pragma optimize("w",on )
79 # endif /* BUGGY_MSC6 */
86 #define ISMULT1(c) ((c) == '*' || (c) == '+' || (c) == '?')
87 #define ISMULT2(s) ((*s) == '*' || (*s) == '+' || (*s) == '?' || \
88 ((*s) == '{' && regcurly(s)))
89 #define META "^$.[()|?+*\\"
92 #undef SPSTART /* dratted cpp namespace... */
95 * Flags to be passed up and down.
97 #define HASWIDTH 01 /* Known never to match null string. */
98 #define SIMPLE 02 /* Simple enough to be STAR/PLUS operand. */
99 #define SPSTART 04 /* Starts with * or +. */
100 #define WORST 0 /* Worst case. */
103 * Global work variables for regcomp().
105 static char *regprecomp; /* uncompiled string. */
106 static char *regparse; /* Input-scan pointer. */
107 static char *regxend; /* End of input for compile */
108 static int regnpar; /* () count. */
109 static char *regcode; /* Code-emit pointer; ®dummy = don't. */
110 static long regsize; /* Code size. */
112 static int regsawbracket; /* Did we do {d,d} trick? */
113 static int regsawback; /* Did we see \1, ...? */
116 * Forward declarations for regcomp()'s friends.
118 STATIC int regcurly();
120 STATIC char *regbranch();
121 STATIC char *regpiece();
122 STATIC char *regatom();
123 STATIC char *regclass();
124 STATIC char *regnode();
125 STATIC char *reganode();
127 STATIC void reginsert();
128 STATIC void regtail();
129 STATIC void regoptail();
132 - regcomp - compile a regular expression into internal code
134 * We can't allocate space until we know how big the compiled form will be,
135 * but we can't compile it (and thus know how big it is) until we've got a
136 * place to put the code. So we cheat: we compile it twice, once with code
137 * generation turned off and size counting turned on, and once "for real".
138 * This also means that we don't allocate space until we are sure that the
139 * thing really will compile successfully, and we never have to move the
140 * code and thus invalidate pointers into it. (Note that it has to be in
141 * one piece because free() must be able to free it all.) [NB: not true in perl]
143 * Beware that the optimization-preparation code in here knows about some
144 * of the structure of the compiled regexp. [I'll say.]
147 regcomp(exp,xend,fold)
154 register STR *longish;
157 register char *first;
164 extern char *safemalloc();
166 extern char *savestr();
171 fatal("NULL regexp argument");
173 /* First pass: determine size, legality. */
177 regprecomp = nsavestr(exp,xend-exp);
184 if (reg(0, &flags) == NULL) {
185 Safefree(regprecomp);
190 /* Small enough for pointer-storage convention? */
191 if (regsize >= 32767L) /* Probably could be 65535L. */
192 FAIL("regexp too big");
194 /* Allocate space. */
195 Newc(1001, r, sizeof(regexp) + (unsigned)regsize, char, regexp);
197 FAIL("regexp out of space");
199 /* Second pass: emit code. */
201 bcopy(regprecomp,exp,xend-exp);
202 r->prelen = xend-exp;
203 r->precomp = regprecomp;
204 r->subbeg = r->subbase = NULL;
207 regcode = r->program;
209 if (reg(0, &flags) == NULL)
212 /* Dig out information for optimizations. */
213 r->regstart = Nullstr; /* Worst-case defaults. */
215 r->regmust = Nullstr;
217 r->regstclass = Nullch;
218 scan = r->program+1; /* First BRANCH. */
219 if (OP(regnext(scan)) == END) {/* Only one top-level choice. */
220 scan = NEXTOPER(scan);
223 while ((OP(first) == OPEN && (sawopen = 1)) ||
224 (OP(first) == BRANCH && OP(regnext(first)) != BRANCH) ||
225 (OP(first) == PLUS) ||
226 (OP(first) == CURLY && ARG1(first) > 0) ) {
227 if (OP(first) == PLUS)
230 first += regarglen[OP(first)];
231 first = NEXTOPER(first);
234 /* Starting-point info. */
236 if (OP(first) == EXACTLY) {
238 str_make(OPERAND(first)+1,*OPERAND(first));
239 if (r->regstart->str_cur > !(sawstudy|fold))
240 fbmcompile(r->regstart,fold);
242 else if ((exp = index(simple,OP(first))) && exp > simple)
243 r->regstclass = first;
244 else if (OP(first) == BOUND || OP(first) == NBOUND)
245 r->regstclass = first;
246 else if (OP(first) == BOL ||
247 (OP(first) == STAR && OP(NEXTOPER(first)) == ANY) ) {
248 /* kinda turn .* into ^.* */
249 r->reganch = ROPT_ANCH | ROPT_IMPLICIT;
250 first = NEXTOPER(first);
253 if (sawplus && (!sawopen || !regsawback))
254 r->reganch |= ROPT_SKIP; /* x+ must match 1st of run */
258 fprintf(stderr,"first %d next %d offset %d\n",
259 OP(first), OP(NEXTOPER(first)), first - scan);
262 * If there's something expensive in the r.e., find the
263 * longest literal string that must appear and make it the
264 * regmust. Resolve ties in favor of later strings, since
265 * the regstart check works with the beginning of the r.e.
266 * and avoiding duplication strengthens checking. Not a
267 * strong reason, but sufficient in the absence of others.
268 * [Now we resolve ties in favor of the earlier string if
269 * it happens that curback has been invalidated, since the
270 * earlier string may buy us something the later one won't.]
272 longish = str_make("",0);
273 longest = str_make("",0);
279 while (OP(scan) != END) {
280 if (OP(scan) == BRANCH) {
281 if (OP(regnext(scan)) == BRANCH) {
283 while (OP(scan) == BRANCH)
284 scan = regnext(scan);
286 else /* single branch is ok */
287 scan = NEXTOPER(scan);
289 if (OP(scan) == EXACTLY) {
293 while (OP(t = regnext(scan)) == CLOSE)
295 minlen += *OPERAND(first);
296 if (curback - backish == len) {
297 str_ncat(longish, OPERAND(first)+1,
299 len += *OPERAND(first);
300 curback += *OPERAND(first);
301 first = regnext(scan);
303 else if (*OPERAND(first) >= len + (curback >= 0)) {
304 len = *OPERAND(first);
305 str_nset(longish, OPERAND(first)+1,len);
308 first = regnext(scan);
311 curback += *OPERAND(first);
313 else if (index(varies,OP(scan))) {
316 if (longish->str_cur > longest->str_cur) {
317 str_sset(longest,longish);
320 str_nset(longish,"",0);
321 if (OP(scan) == PLUS &&
322 index(simple,OP(NEXTOPER(scan))))
324 else if (OP(scan) == CURLY &&
325 index(simple,OP(NEXTOPER(scan)+4)))
326 minlen += ARG1(scan);
328 else if (index(simple,OP(scan))) {
332 if (longish->str_cur > longest->str_cur) {
333 str_sset(longest,longish);
336 str_nset(longish,"",0);
338 scan = regnext(scan);
341 /* Prefer earlier on tie, unless we can tail match latter */
343 if (longish->str_cur + (OP(first) == EOL) > longest->str_cur) {
344 str_sset(longest,longish);
348 str_nset(longish,"",0);
353 !fbminstr((unsigned char*) r->regstart->str_ptr,
354 (unsigned char *) r->regstart->str_ptr
355 + r->regstart->str_cur,
360 r->regmust = longest;
363 r->regback = backest;
365 > !(sawstudy || fold || OP(first) == EOL) )
366 fbmcompile(r->regmust,fold);
367 r->regmust->str_u.str_useful = 100;
368 if (OP(first) == EOL && longish->str_cur)
369 r->regmust->str_pok |= SP_TAIL;
378 r->do_folding = fold;
379 r->nparens = regnpar - 1;
381 Newz(1002, r->startp, regnpar, char*);
382 Newz(1002, r->endp, regnpar, char*);
391 - reg - regular expression, i.e. main body or parenthesized thing
393 * Caller must absorb opening parenthesis.
395 * Combining parenthesis handling with the base level of regular expression
396 * is a trifle forced, but the need to tie the tails of the branches to what
397 * follows makes it hard to avoid.
401 int paren; /* Parenthesized? */
406 register char *ender;
410 *flagp = HASWIDTH; /* Tentatively. */
412 /* Make an OPEN node, if parenthesized. */
416 ret = reganode(OPEN, parno);
420 /* Pick up the branches, linking them together. */
421 br = regbranch(&flags);
425 regtail(ret, br); /* OPEN -> first. */
428 if (!(flags&HASWIDTH))
430 *flagp |= flags&SPSTART;
431 while (*regparse == '|') {
433 br = regbranch(&flags);
436 regtail(ret, br); /* BRANCH -> BRANCH. */
437 if (!(flags&HASWIDTH))
439 *flagp |= flags&SPSTART;
442 /* Make a closing node, and hook it on the end. */
444 ender = reganode(CLOSE, parno);
446 ender = regnode(END);
449 /* Hook the tails of the branches to the closing node. */
450 for (br = ret; br != NULL; br = regnext(br))
451 regoptail(br, ender);
453 /* Check for proper termination. */
454 if (paren && *regparse++ != ')') {
455 FAIL("unmatched () in regexp");
456 } else if (!paren && regparse < regxend) {
457 if (*regparse == ')') {
458 FAIL("unmatched () in regexp");
460 FAIL("junk on end of regexp"); /* "Can't happen". */
468 - regbranch - one alternative of an | operator
470 * Implements the concatenation operator.
477 register char *chain;
478 register char *latest;
481 *flagp = WORST; /* Tentatively. */
483 ret = regnode(BRANCH);
485 while (regparse < regxend && *regparse != '|' && *regparse != ')') {
486 latest = regpiece(&flags);
489 *flagp |= flags&HASWIDTH;
490 if (chain == NULL) /* First piece. */
491 *flagp |= flags&SPSTART;
493 regtail(chain, latest);
496 if (chain == NULL) /* Loop ran zero times. */
497 (void) regnode(NOTHING);
503 - regpiece - something followed by possible [*+?]
505 * Note that the branching code sequences used for ? and the general cases
506 * of * and + are somewhat optimized: they use the same NOTHING node as
507 * both the endmarker for their branch list and the body of the last branch.
508 * It might seem that this node could be dispensed with entirely, but the
509 * endmarker role is not redundant.
519 char *origparse = regparse;
520 int orignpar = regnpar;
525 ret = regatom(&flags);
531 /* Here's a total kludge: if after the atom there's a {\d+,?\d*}
532 * then we decrement the first number by one and reset our
533 * parsing back to the beginning of the same atom. If the first number
534 * is down to 0, decrement the second number instead and fake up
535 * a ? after it. Given the way this compiler doesn't keep track
536 * of offsets on the first pass, this is the only way to replicate
537 * a piece of code. Sigh.
539 if (op == '{' && regcurly(regparse)) {
542 while (isDIGIT(*next) || *next == ',') {
551 if (*next == '}') { /* got one */
555 iter = atoi(regparse);
556 if (flags&SIMPLE) { /* we can do it right after all */
559 reginsert(CURLY, ret);
561 *flagp = (WORST|HASWIDTH);
567 if (tmp && tmp < iter)
568 fatal("Can't do {n,m} with n > m");
569 if (regcode != ®dummy) {
571 *(unsigned short *)(ret+3) = iter;
572 *(unsigned short *)(ret+5) = tmp;
574 ret[3] = iter >> 8; ret[4] = iter & 0377;
575 ret[5] = tmp >> 8; ret[6] = tmp & 0377;
581 regsawbracket++; /* remember we clobbered exp */
584 sprintf(regparse,"%.*d", max-regparse, iter - 1);
586 if (*max == ',' && max[1] != '}') {
587 if (atoi(max+1) <= 0)
588 fatal("Can't do {n,m} with n > m");
590 sprintf(max+1,"%.*d", next-(max+1), atoi(max+1) - 1);
593 if (iter != 1 || *max == ',') {
594 regparse = origparse; /* back up input pointer */
595 regnpar = orignpar; /* don't make more parens */
607 if (max == next) { /* any number more? */
609 op = '*'; /* fake up one with a star */
612 op = '?'; /* fake up optional atom */
614 sprintf(max,"%.*d", next-max, iter - 1);
619 regparse = origparse - 1; /* offset ++ below */
624 fatal("Can't do {n,0}");
627 fatal("Can't do {0}");
636 if (!(flags&HASWIDTH) && op != '?')
637 FAIL("regexp *+ operand could be empty");
638 *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);
640 if (op == '*' && (flags&SIMPLE))
641 reginsert(STAR, ret);
642 else if (op == '*') {
643 /* Emit x* as (x&|), where & means "self". */
644 reginsert(BRANCH, ret); /* Either x */
645 regoptail(ret, regnode(BACK)); /* and loop */
646 regoptail(ret, ret); /* back */
647 regtail(ret, regnode(BRANCH)); /* or */
648 regtail(ret, regnode(NOTHING)); /* null. */
649 } else if (op == '+' && (flags&SIMPLE))
650 reginsert(PLUS, ret);
651 else if (op == '+') {
652 /* Emit x+ as x(&|), where & means "self". */
653 next = regnode(BRANCH); /* Either */
655 regtail(regnode(BACK), ret); /* loop back */
656 regtail(next, regnode(BRANCH)); /* or */
657 regtail(ret, regnode(NOTHING)); /* null. */
658 } else if (op == '?') {
659 /* Emit x? as (x|) */
660 reginsert(BRANCH, ret); /* Either x */
661 regtail(ret, regnode(BRANCH)); /* or */
662 next = regnode(NOTHING); /* null. */
664 regoptail(ret, next);
668 if (ISMULT2(regparse))
669 FAIL("nested *?+ in regexp");
675 - regatom - the lowest level
677 * Optimization: gobbles an entire sequence of ordinary characters so that
678 * it can turn them into a single node, which is smaller to store and
679 * faster to run. Backslashed characters are exceptions, each becoming a
680 * separate node; the code is simpler that way and it's not worth fixing.
682 * [Yes, it is worth fixing, some scripts can run twice the speed.]
691 *flagp = WORST; /* Tentatively. */
693 switch (*regparse++) {
702 *flagp |= HASWIDTH|SIMPLE;
706 *flagp |= HASWIDTH|SIMPLE;
709 ret = reg(1, &flags);
712 *flagp |= flags&(HASWIDTH|SPSTART);
716 FAIL("internal urp in regexp"); /* Supposed to be caught earlier. */
721 FAIL("?+* follows nothing in regexp");
726 ret = regnode(ALNUM);
727 *flagp |= HASWIDTH|SIMPLE;
731 ret = regnode(NALNUM);
732 *flagp |= HASWIDTH|SIMPLE;
736 ret = regnode(BOUND);
741 ret = regnode(NBOUND);
746 ret = regnode(SPACE);
747 *flagp |= HASWIDTH|SIMPLE;
751 ret = regnode(NSPACE);
752 *flagp |= HASWIDTH|SIMPLE;
756 ret = regnode(DIGIT);
757 *flagp |= HASWIDTH|SIMPLE;
761 ret = regnode(NDIGIT);
762 *flagp |= HASWIDTH|SIMPLE;
775 case '1': case '2': case '3': case '4':
776 case '5': case '6': case '7': case '8': case '9':
778 int num = atoi(regparse);
780 if (num > 9 && num >= regnpar)
784 ret = reganode(REF, num);
785 while (isDIGIT(*regparse))
792 if (regparse >= regxend)
793 FAIL("trailing \\ in regexp");
807 ret = regnode(EXACTLY);
808 regc(0); /* save spot for len */
809 for (len=0, p=regparse-1;
810 len < 127 && p < regxend;
860 ender = scanhex(++p, 2, &numlen);
867 ender = toupper(ender);
870 case '0': case '1': case '2': case '3':case '4':
871 case '5': case '6': case '7': case '8':case '9':
873 (isDIGIT(p[1]) && atoi(p) >= regnpar) ) {
874 ender = scanoct(p, 3, &numlen);
884 FAIL("trailing \\ in regexp");
895 if (regfold && isUPPER(ender))
896 ender = tolower(ender);
897 if (ISMULT2(p)) { /* Back off on ?+*. */
911 FAIL("internal disaster in regexp");
915 if (regcode != ®dummy)
931 if (regcode == ®dummy)
935 bits[c >> 3] &= ~(1 << (c & 7));
937 bits[c >> 3] |= (1 << (c & 7));
945 register int lastclass;
946 register int range = 0;
951 ret = regnode(ANYOF);
952 if (*regparse == '^') { /* Complement of range. */
959 for (class = 0; class < 32; class++)
961 if (*regparse == ']' || *regparse == '-')
962 goto skipcond; /* allow 1st char to be ] or - */
963 while (regparse < regxend && *regparse != ']') {
965 class = UCHARAT(regparse++);
967 class = UCHARAT(regparse++);
970 for (class = 'a'; class <= 'z'; class++)
971 regset(bits,def,class);
972 for (class = 'A'; class <= 'Z'; class++)
973 regset(bits,def,class);
974 for (class = '0'; class <= '9'; class++)
975 regset(bits,def,class);
976 regset(bits,def,'_');
980 regset(bits,def,' ');
981 regset(bits,def,'\t');
982 regset(bits,def,'\r');
983 regset(bits,def,'\f');
984 regset(bits,def,'\n');
988 for (class = '0'; class <= '9'; class++)
989 regset(bits,def,class);
1014 class = scanhex(regparse, 2, &numlen);
1018 class = *regparse++;
1020 class = toupper(class);
1023 case '0': case '1': case '2': case '3': case '4':
1024 case '5': case '6': case '7': case '8': case '9':
1025 class = scanoct(--regparse, 3, &numlen);
1031 if (lastclass > class)
1032 FAIL("invalid [] range in regexp");
1037 if (*regparse == '-' && regparse+1 < regxend &&
1038 regparse[1] != ']') {
1041 continue; /* do it next time */
1044 for ( ; lastclass <= class; lastclass++) {
1045 regset(bits,def,lastclass);
1046 if (regfold && isUPPER(lastclass))
1047 regset(bits,def,tolower(lastclass));
1051 if (*regparse != ']')
1052 FAIL("unmatched [] in regexp");
1058 - regnode - emit a node
1060 static char * /* Location. */
1068 if (ret == ®dummy) {
1079 if (!((long)ret & 1))
1085 *ptr++ = '\0'; /* Null "next" pointer. */
1093 - reganode - emit a node with an argument
1095 static char * /* Location. */
1104 if (ret == ®dummy) {
1115 if (!((long)ret & 1))
1121 *ptr++ = '\0'; /* Null "next" pointer. */
1124 *(unsigned short *)(ret+3) = arg;
1126 ret[3] = arg >> 8; ret[4] = arg & 0377;
1135 - regc - emit (if appropriate) a byte of code
1141 if (regcode != ®dummy)
1148 - reginsert - insert an operator in front of already-emitted operand
1150 * Means relocating the operand.
1159 register char *place;
1160 register offset = (op == CURLY ? 4 : 0);
1162 if (regcode == ®dummy) {
1164 regsize += 4 + offset;
1166 regsize += 3 + offset;
1173 regcode += 4 + offset;
1175 regcode += 3 + offset;
1181 place = opnd; /* Op node, where operand used to be. */
1185 while (offset-- > 0)
1190 - regtail - set the next-pointer at the end of a node chain
1197 register char *scan;
1198 register char *temp;
1199 register int offset;
1204 /* Find last node. */
1207 temp = regnext(scan);
1214 offset = val - scan;
1216 *(short*)(scan+1) = offset;
1221 if (OP(scan) == BACK)
1222 offset = scan - val;
1224 offset = val - scan;
1225 *(scan+1) = (offset>>8)&0377;
1226 *(scan+2) = offset&0377;
1231 - regoptail - regtail on operand of first argument; nop if operandless
1238 /* "Operandless" and "op != BRANCH" are synonymous in practice. */
1239 if (p == NULL || p == ®dummy || OP(p) != BRANCH)
1241 regtail(NEXTOPER(p), val);
1245 - regcurly - a little FSA that accepts {\d+,?\d*}
1269 - regdump - dump a regexp onto stderr in vaguely comprehensible form
1276 register char op = EXACTLY; /* Arbitrary non-END op. */
1277 register char *next;
1281 while (op != END) { /* While that wasn't END last time... */
1287 fprintf(stderr,"%2d%s", s-r->program, regprop(s)); /* Where, what. */
1290 if (next == NULL) /* Next ptr. */
1291 fprintf(stderr,"(0)");
1293 fprintf(stderr,"(%d)", (s-r->program)+(next-s));
1298 if (op == EXACTLY) {
1299 /* Literal string, where present. */
1301 while (*s != '\0') {
1307 (void)putchar('\n');
1310 /* Header fields of interest. */
1312 fprintf(stderr,"start `%s' ", r->regstart->str_ptr);
1314 fprintf(stderr,"stclass `%s' ", regprop(r->regstclass));
1315 if (r->reganch & ROPT_ANCH)
1316 fprintf(stderr,"anchored ");
1317 if (r->reganch & ROPT_SKIP)
1318 fprintf(stderr,"plus ");
1319 if (r->reganch & ROPT_IMPLICIT)
1320 fprintf(stderr,"implicit ");
1321 if (r->regmust != NULL)
1322 fprintf(stderr,"must have \"%s\" back %d ", r->regmust->str_ptr,
1324 fprintf(stderr, "minlen %d ", r->minlen);
1325 fprintf(stderr,"\n");
1329 - regprop - printable representation of opcode
1337 (void) strcpy(buf, ":");
1392 (void)sprintf(buf+strlen(buf), "CURLY {%d,%d}",
1397 (void)sprintf(buf+strlen(buf), "REF%d", ARG1(op));
1401 (void)sprintf(buf+strlen(buf), "OPEN%d", ARG1(op));
1405 (void)sprintf(buf+strlen(buf), "CLOSE%d", ARG1(op));
1415 FAIL("corrupted regexp opcode");
1418 (void) strcat(buf, p);
1421 #endif /* DEBUGGING */
1427 Safefree(r->precomp);
1428 r->precomp = Nullch;
1431 Safefree(r->subbase);
1432 r->subbase = Nullch;
1435 str_free(r->regmust);
1436 r->regmust = Nullstr;
1439 str_free(r->regstart);
1440 r->regstart = Nullstr;
1442 Safefree(r->startp);