regcomp.c
上传用户:romrleung
上传日期:2022-05-23
资源大小:18897k
文件大小:39k
源码类别:

MySQL数据库

开发平台:

Visual C++

  1. #include <my_global.h>
  2. #include <m_string.h>
  3. #include <m_ctype.h>
  4. #ifdef __WIN__
  5. #include  <limits.h>
  6. #endif
  7. #include "my_regex.h"
  8. #include "utils.h"
  9. #include "regex2.h"
  10. #include "cclass.h"
  11. #include "cname.h"
  12. /*
  13.  * parse structure, passed up and down to avoid global variables and
  14.  * other clumsinesses
  15.  */
  16. struct parse {
  17. char *next; /* next character in RE */
  18. char *end; /* end of string (-> NUL normally) */
  19. int error; /* has an error been seen? */
  20. sop *strip; /* malloced strip */
  21. sopno ssize; /* malloced strip size (allocated) */
  22. sopno slen; /* malloced strip length (used) */
  23. int ncsalloc; /* number of csets allocated */
  24. struct re_guts *g;
  25. # define NPAREN 10 /* we need to remember () 1-9 for back refs */
  26. sopno pbegin[NPAREN]; /* -> ( ([0] unused) */
  27. sopno pend[NPAREN]; /* -> ) ([0] unused) */
  28. CHARSET_INFO *charset; /* for ctype things  */
  29. };
  30. #include "regcomp.ih"
  31. static char nuls[10]; /* place to point scanner in event of error */
  32. struct cclass cclasses[CCLASS_LAST+1]= {
  33.   { "alnum", "","", _MY_U | _MY_L | _MY_NMR},
  34.   { "alpha", "","", _MY_U | _MY_L },
  35.   { "blank", "","", _MY_B },
  36.   { "cntrl", "","", _MY_CTR },
  37.   { "digit", "","", _MY_NMR },
  38.   { "graph", "","", _MY_PNT | _MY_U | _MY_L | _MY_NMR},
  39.   { "lower", "","", _MY_L },
  40.   { "print", "","", _MY_PNT | _MY_U | _MY_L | _MY_NMR | _MY_B },
  41.   { "punct", "","", _MY_PNT },
  42.   { "space", "","", _MY_SPC },
  43.   { "upper", "","", _MY_U },
  44.   { "xdigit", "","", _MY_X },
  45.   { NULL,NULL,NULL, 0 }
  46. };
  47. /*
  48.  * macros for use with parse structure
  49.  * BEWARE:  these know that the parse structure is named `p' !!!
  50.  */
  51. #define PEEK() (*p->next)
  52. #define PEEK2() (*(p->next+1))
  53. #define MORE() (p->next < p->end)
  54. #define MORE2() (p->next+1 < p->end)
  55. #define SEE(c) (MORE() && PEEK() == (c))
  56. #define SEETWO(a, b) (MORE() && MORE2() && PEEK() == (a) && PEEK2() == (b))
  57. #define EAT(c) ((SEE(c)) ? (NEXT(), 1) : 0)
  58. #define EATTWO(a, b) ((SEETWO(a, b)) ? (NEXT2(), 1) : 0)
  59. #define NEXT() (p->next++)
  60. #define NEXT2() (p->next += 2)
  61. #define NEXTn(n) (p->next += (n))
  62. #define GETNEXT() (*p->next++)
  63. #define SETERROR(e) seterr(p, (e))
  64. #define REQUIRE(co, e) ((co) || SETERROR(e))
  65. #define MUSTSEE(c, e) (REQUIRE(MORE() && PEEK() == (c), e))
  66. #define MUSTEAT(c, e) (REQUIRE(MORE() && GETNEXT() == (c), e))
  67. #define MUSTNOTSEE(c, e) (REQUIRE(!MORE() || PEEK() != (c), e))
  68. #define EMIT(op, sopnd) doemit(p, (sop)(op), (size_t)(sopnd))
  69. #define INSERT(op, pos) doinsert(p, (sop)(op), HERE()-(pos)+1, pos)
  70. #define AHEAD(pos) dofwd(p, pos, HERE()-(pos))
  71. #define ASTERN(sop, pos) EMIT(sop, HERE()-pos)
  72. #define HERE() (p->slen)
  73. #define THERE() (p->slen - 1)
  74. #define THERETHERE() (p->slen - 2)
  75. #define DROP(n) (p->slen -= (n))
  76. #ifndef NDEBUG
  77. static int never = 0; /* for use in asserts; shuts lint up */
  78. #else
  79. #define never 0 /* some <assert.h>s have bugs too */
  80. #endif
  81. /*
  82.  - regcomp - interface for parser and compilation
  83.  = extern int regcomp(regex_t *, const char *, int);
  84.  = #define REG_BASIC 0000
  85.  = #define REG_EXTENDED 0001
  86.  = #define REG_ICASE 0002
  87.  = #define REG_NOSUB 0004
  88.  = #define REG_NEWLINE 0010
  89.  = #define REG_NOSPEC 0020
  90.  = #define REG_PEND 0040
  91.  = #define REG_DUMP 0200
  92.  */
  93. int /* 0 success, otherwise REG_something */
  94. my_regcomp(preg, pattern, cflags, charset)
  95. my_regex_t *preg;
  96. const char *pattern;
  97. int cflags;
  98. CHARSET_INFO *charset;
  99. {
  100. struct parse pa;
  101. register struct re_guts *g;
  102. register struct parse *p = &pa;
  103. register int i;
  104. register size_t len;
  105. #ifdef REDEBUG
  106. # define GOODFLAGS(f) (f)
  107. #else
  108. # define GOODFLAGS(f) ((f)&~REG_DUMP)
  109. #endif
  110. my_regex_init(charset); /* Init cclass if neaded */
  111. preg->charset=charset;
  112. cflags = GOODFLAGS(cflags);
  113. if ((cflags&REG_EXTENDED) && (cflags&REG_NOSPEC))
  114. return(REG_INVARG);
  115. if (cflags&REG_PEND) {
  116. if (preg->re_endp < pattern)
  117. return(REG_INVARG);
  118. len = preg->re_endp - pattern;
  119. } else
  120. len = strlen((char *)pattern);
  121. /* do the mallocs early so failure handling is easy */
  122. g = (struct re_guts *)malloc(sizeof(struct re_guts) +
  123. (NC-1)*sizeof(cat_t));
  124. if (g == NULL)
  125. return(REG_ESPACE);
  126. p->ssize = (long) (len/(size_t)2*(size_t)3 + (size_t)1); /* ugh */
  127. p->strip = (sop *)malloc(p->ssize * sizeof(sop));
  128. p->slen = 0;
  129. if (p->strip == NULL) {
  130. free((char *)g);
  131. return(REG_ESPACE);
  132. }
  133. /* set things up */
  134. p->g = g;
  135. p->next = (char *)pattern; /* convenience; we do not modify it */
  136. p->end = p->next + len;
  137. p->error = 0;
  138. p->ncsalloc = 0;
  139. p->charset = preg->charset;
  140. for (i = 0; i < NPAREN; i++) {
  141. p->pbegin[i] = 0;
  142. p->pend[i] = 0;
  143. }
  144. g->csetsize = NC;
  145. g->sets = NULL;
  146. g->setbits = NULL;
  147. g->ncsets = 0;
  148. g->cflags = cflags;
  149. g->iflags = 0;
  150. g->nbol = 0;
  151. g->neol = 0;
  152. g->must = NULL;
  153. g->mlen = 0;
  154. g->nsub = 0;
  155. g->ncategories = 1; /* category 0 is "everything else" */
  156. g->categories = &g->catspace[-(CHAR_MIN)];
  157. (void) memset((char *)g->catspace, 0, NC*sizeof(cat_t));
  158. g->backrefs = 0;
  159. /* do it */
  160. EMIT(OEND, 0);
  161. g->firststate = THERE();
  162. if (cflags&REG_EXTENDED)
  163. p_ere(p, OUT);
  164. else if (cflags&REG_NOSPEC)
  165. p_str(p);
  166. else
  167. p_bre(p, OUT, OUT);
  168. EMIT(OEND, 0);
  169. g->laststate = THERE();
  170. /* tidy up loose ends and fill things in */
  171. categorize(p, g);
  172. stripsnug(p, g);
  173. findmust(p, g);
  174. g->nplus = pluscount(p, g);
  175. g->magic = MAGIC2;
  176. preg->re_nsub = g->nsub;
  177. preg->re_g = g;
  178. preg->re_magic = MAGIC1;
  179. #ifndef REDEBUG
  180. /* not debugging, so can't rely on the assert() in regexec() */
  181. if (g->iflags&BAD)
  182. SETERROR(REG_ASSERT);
  183. #endif
  184. /* win or lose, we're done */
  185. if (p->error != 0) /* lose */
  186. my_regfree(preg);
  187. return(p->error);
  188. }
  189. /*
  190.  - p_ere - ERE parser top level, concatenation and alternation
  191.  == static void p_ere(register struct parse *p, int stop);
  192.  */
  193. static void
  194. p_ere(p, stop)
  195. register struct parse *p;
  196. int stop; /* character this ERE should end at */
  197. {
  198. register char c;
  199. register sopno prevback;
  200. register sopno prevfwd;
  201. register sopno conc;
  202. register int first = 1; /* is this the first alternative? */
  203. LINT_INIT(prevback); LINT_INIT(prevfwd);
  204. for (;;) {
  205. /* do a bunch of concatenated expressions */
  206. conc = HERE();
  207. while (MORE() && (c = PEEK()) != '|' && c != stop)
  208. p_ere_exp(p);
  209. if(REQUIRE(HERE() != conc, REG_EMPTY)) {}/* require nonempty */
  210. if (!EAT('|'))
  211. break; /* NOTE BREAK OUT */
  212. if (first) {
  213. INSERT(OCH_, conc); /* offset is wrong */
  214. prevfwd = conc;
  215. prevback = conc;
  216. first = 0;
  217. }
  218. ASTERN(OOR1, prevback);
  219. prevback = THERE();
  220. AHEAD(prevfwd); /* fix previous offset */
  221. prevfwd = HERE();
  222. EMIT(OOR2, 0); /* offset is very wrong */
  223. }
  224. if (!first) { /* tail-end fixups */
  225. AHEAD(prevfwd);
  226. ASTERN(O_CH, prevback);
  227. }
  228. assert(!MORE() || SEE(stop));
  229. }
  230. /*
  231.  - p_ere_exp - parse one subERE, an atom possibly followed by a repetition op
  232.  == static void p_ere_exp(register struct parse *p);
  233.  */
  234. static void
  235. p_ere_exp(p)
  236. register struct parse *p;
  237. {
  238. register char c;
  239. register sopno pos;
  240. register int count;
  241. register int count2;
  242. register sopno subno;
  243. int wascaret = 0;
  244. assert(MORE()); /* caller should have ensured this */
  245. c = GETNEXT();
  246. pos = HERE();
  247. switch (c) {
  248. case '(':
  249. if(REQUIRE(MORE(), REG_EPAREN)) {}
  250. p->g->nsub++;
  251. subno = (sopno) p->g->nsub;
  252. if (subno < NPAREN)
  253.         p->pbegin[subno] = HERE();
  254. EMIT(OLPAREN, subno);
  255. if (!SEE(')'))
  256. p_ere(p, ')');
  257. if (subno < NPAREN) {
  258. p->pend[subno] = HERE();
  259. assert(p->pend[subno] != 0);
  260. }
  261. EMIT(ORPAREN, subno);
  262. if(MUSTEAT(')', REG_EPAREN)) {}
  263. break;
  264. #ifndef POSIX_MISTAKE
  265. case ')': /* happens only if no current unmatched ( */
  266. /*
  267.  * You may ask, why the ifndef?  Because I didn't notice
  268.  * this until slightly too late for 1003.2, and none of the
  269.  * other 1003.2 regular-expression reviewers noticed it at
  270.  * all.  So an unmatched ) is legal POSIX, at least until
  271.  * we can get it fixed.
  272.  */
  273. SETERROR(REG_EPAREN);
  274. break;
  275. #endif
  276. case '^':
  277. EMIT(OBOL, 0);
  278. p->g->iflags |= USEBOL;
  279. p->g->nbol++;
  280. wascaret = 1;
  281. break;
  282. case '$':
  283. EMIT(OEOL, 0);
  284. p->g->iflags |= USEEOL;
  285. p->g->neol++;
  286. break;
  287. case '|':
  288. SETERROR(REG_EMPTY);
  289. break;
  290. case '*':
  291. case '+':
  292. case '?':
  293. SETERROR(REG_BADRPT);
  294. break;
  295. case '.':
  296. if (p->g->cflags&REG_NEWLINE)
  297. nonnewline(p);
  298. else
  299. EMIT(OANY, 0);
  300. break;
  301. case '[':
  302. p_bracket(p);
  303. break;
  304. case '\':
  305. if(REQUIRE(MORE(), REG_EESCAPE)) {}
  306. c = GETNEXT();
  307. ordinary(p, c);
  308. break;
  309. case '{': /* okay as ordinary except if digit follows */
  310. if(REQUIRE(!MORE() || !my_isdigit(p->charset,PEEK()), REG_BADRPT)) {}
  311. /* FALLTHROUGH */
  312. default:
  313. ordinary(p, c);
  314. break;
  315. }
  316. if (!MORE())
  317. return;
  318. c = PEEK();
  319. /* we call { a repetition if followed by a digit */
  320. if (!( c == '*' || c == '+' || c == '?' ||
  321. (c == '{' && MORE2() && 
  322.  my_isdigit(p->charset,PEEK2())) ))
  323. return; /* no repetition, we're done */
  324. NEXT();
  325. if(REQUIRE(!wascaret, REG_BADRPT)) {}
  326. switch (c) {
  327. case '*': /* implemented as +? */
  328. /* this case does not require the (y|) trick, noKLUDGE */
  329. INSERT(OPLUS_, pos);
  330. ASTERN(O_PLUS, pos);
  331. INSERT(OQUEST_, pos);
  332. ASTERN(O_QUEST, pos);
  333. break;
  334. case '+':
  335. INSERT(OPLUS_, pos);
  336. ASTERN(O_PLUS, pos);
  337. break;
  338. case '?':
  339. /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
  340. INSERT(OCH_, pos); /* offset slightly wrong */
  341. ASTERN(OOR1, pos); /* this one's right */
  342. AHEAD(pos); /* fix the OCH_ */
  343. EMIT(OOR2, 0); /* offset very wrong... */
  344. AHEAD(THERE()); /* ...so fix it */
  345. ASTERN(O_CH, THERETHERE());
  346. break;
  347. case '{':
  348. count = p_count(p);
  349. if (EAT(',')) {
  350. if (my_isdigit(p->charset,PEEK())) {
  351. count2 = p_count(p);
  352. if(REQUIRE(count <= count2, REG_BADBR)) {}
  353. } else /* single number with comma */
  354. count2 = RE_INFINITY;
  355. } else /* just a single number */
  356. count2 = count;
  357. repeat(p, pos, count, count2);
  358. if (!EAT('}')) { /* error heuristics */
  359. while (MORE() && PEEK() != '}')
  360. NEXT();
  361. if(REQUIRE(MORE(), REG_EBRACE)) {}
  362. SETERROR(REG_BADBR);
  363. }
  364. break;
  365. }
  366. if (!MORE())
  367. return;
  368. c = PEEK();
  369. if (!( c == '*' || c == '+' || c == '?' ||
  370. (c == '{' && MORE2() && 
  371.  my_isdigit(p->charset,PEEK2())) ) )
  372. return;
  373. SETERROR(REG_BADRPT);
  374. }
  375. /*
  376.  - p_str - string (no metacharacters) "parser"
  377.  == static void p_str(register struct parse *p);
  378.  */
  379. static void
  380. p_str(p)
  381. register struct parse *p;
  382. {
  383. if(REQUIRE(MORE(), REG_EMPTY)) {}
  384. while (MORE())
  385. ordinary(p, GETNEXT());
  386. }
  387. /*
  388.  - p_bre - BRE parser top level, anchoring and concatenation
  389.  == static void p_bre(register struct parse *p, register int end1, 
  390.  == register int end2);
  391.  * Giving end1 as OUT essentially eliminates the end1/end2 check.
  392.  *
  393.  * This implementation is a bit of a kludge, in that a trailing $ is first
  394.  * taken as an ordinary character and then revised to be an anchor.  The
  395.  * only undesirable side effect is that '$' gets included as a character
  396.  * category in such cases.  This is fairly harmless; not worth fixing.
  397.  * The amount of lookahead needed to avoid this kludge is excessive.
  398.  */
  399. static void
  400. p_bre(p, end1, end2)
  401. register struct parse *p;
  402. register int end1; /* first terminating character */
  403. register int end2; /* second terminating character */
  404. {
  405. register sopno start = HERE();
  406. register int first = 1; /* first subexpression? */
  407. register int wasdollar = 0;
  408. if (EAT('^')) {
  409. EMIT(OBOL, 0);
  410. p->g->iflags |= USEBOL;
  411. p->g->nbol++;
  412. }
  413. while (MORE() && !SEETWO(end1, end2)) {
  414. wasdollar = p_simp_re(p, first);
  415. first = 0;
  416. }
  417. if (wasdollar) { /* oops, that was a trailing anchor */
  418. DROP(1);
  419. EMIT(OEOL, 0);
  420. p->g->iflags |= USEEOL;
  421. p->g->neol++;
  422. }
  423. if(REQUIRE(HERE() != start, REG_EMPTY)) {} /* require nonempty */
  424. }
  425. /*
  426.  - p_simp_re - parse a simple RE, an atom possibly followed by a repetition
  427.  == static int p_simp_re(register struct parse *p, int starordinary);
  428.  */
  429. static int /* was the simple RE an unbackslashed $? */
  430. p_simp_re(p, starordinary)
  431. register struct parse *p;
  432. int starordinary; /* is a leading * an ordinary character? */
  433. {
  434. register int c;
  435. register int count;
  436. register int count2;
  437. register sopno pos;
  438. register int i;
  439. register sopno subno;
  440. # define BACKSL (1<<CHAR_BIT)
  441. pos = HERE(); /* repetion op, if any, covers from here */
  442. assert(MORE()); /* caller should have ensured this */
  443. c = GETNEXT();
  444. if (c == '\') {
  445. if(REQUIRE(MORE(), REG_EESCAPE)) {}
  446. c = BACKSL | (unsigned char)GETNEXT();
  447. }
  448. switch (c) {
  449. case '.':
  450. if (p->g->cflags&REG_NEWLINE)
  451. nonnewline(p);
  452. else
  453. EMIT(OANY, 0);
  454. break;
  455. case '[':
  456. p_bracket(p);
  457. break;
  458. case BACKSL|'{':
  459. SETERROR(REG_BADRPT);
  460. break;
  461. case BACKSL|'(':
  462. p->g->nsub++;
  463. subno = (sopno) p->g->nsub;
  464. if (subno < NPAREN)
  465. p->pbegin[subno] = HERE();
  466. EMIT(OLPAREN, subno);
  467. /* the MORE here is an error heuristic */
  468. if (MORE() && !SEETWO('\', ')'))
  469. p_bre(p, '\', ')');
  470. if (subno < NPAREN) {
  471. p->pend[subno] = HERE();
  472. assert(p->pend[subno] != 0);
  473. }
  474. EMIT(ORPAREN, subno);
  475. if(REQUIRE(EATTWO('\', ')'), REG_EPAREN)) {}
  476. break;
  477. case BACKSL|')': /* should not get here -- must be user */
  478. case BACKSL|'}':
  479. SETERROR(REG_EPAREN);
  480. break;
  481. case BACKSL|'1':
  482. case BACKSL|'2':
  483. case BACKSL|'3':
  484. case BACKSL|'4':
  485. case BACKSL|'5':
  486. case BACKSL|'6':
  487. case BACKSL|'7':
  488. case BACKSL|'8':
  489. case BACKSL|'9':
  490. i = (c&~BACKSL) - '0';
  491. assert(i < NPAREN);
  492. if (p->pend[i] != 0) {
  493. assert((uint) i <= p->g->nsub);
  494. EMIT(OBACK_, i);
  495. assert(p->pbegin[i] != 0);
  496. assert(OP(p->strip[p->pbegin[i]]) == OLPAREN);
  497. assert(OP(p->strip[p->pend[i]]) == ORPAREN);
  498. (void) dupl(p, p->pbegin[i]+1, p->pend[i]);
  499. EMIT(O_BACK, i);
  500. } else
  501. SETERROR(REG_ESUBREG);
  502. p->g->backrefs = 1;
  503. break;
  504. case '*':
  505. if(REQUIRE(starordinary, REG_BADRPT)) {}
  506. /* FALLTHROUGH */
  507. default:
  508. ordinary(p, c &~ BACKSL);
  509. break;
  510. }
  511. if (EAT('*')) { /* implemented as +? */
  512. /* this case does not require the (y|) trick, noKLUDGE */
  513. INSERT(OPLUS_, pos);
  514. ASTERN(O_PLUS, pos);
  515. INSERT(OQUEST_, pos);
  516. ASTERN(O_QUEST, pos);
  517. } else if (EATTWO('\', '{')) {
  518. count = p_count(p);
  519. if (EAT(',')) {
  520. if (MORE() && my_isdigit(p->charset,PEEK())) {
  521. count2 = p_count(p);
  522. if(REQUIRE(count <= count2, REG_BADBR)) {}
  523. } else /* single number with comma */
  524. count2 = RE_INFINITY;
  525. } else /* just a single number */
  526. count2 = count;
  527. repeat(p, pos, count, count2);
  528. if (!EATTWO('\', '}')) { /* error heuristics */
  529. while (MORE() && !SEETWO('\', '}'))
  530. NEXT();
  531. if(REQUIRE(MORE(), REG_EBRACE)) {}
  532. SETERROR(REG_BADBR);
  533. }
  534. } else if (c == (unsigned char)'$') /* $ (but not $) ends it */
  535. return(1);
  536. return(0);
  537. }
  538. /*
  539.  - p_count - parse a repetition count
  540.  == static int p_count(register struct parse *p);
  541.  */
  542. static int /* the value */
  543. p_count(p)
  544. register struct parse *p;
  545. {
  546. register int count = 0;
  547. register int ndigits = 0;
  548. while (MORE() && my_isdigit(p->charset,PEEK()) && count <= DUPMAX) {
  549. count = count*10 + (GETNEXT() - '0');
  550. ndigits++;
  551. }
  552. if(REQUIRE(ndigits > 0 && count <= DUPMAX, REG_BADBR)) {}
  553. return(count);
  554. }
  555. /*
  556.  - p_bracket - parse a bracketed character list
  557.  == static void p_bracket(register struct parse *p);
  558.  *
  559.  * Note a significant property of this code:  if the allocset() did SETERROR,
  560.  * no set operations are done.
  561.  */
  562. static void
  563. p_bracket(p)
  564. register struct parse *p;
  565. {
  566. register cset *cs = allocset(p);
  567. register int invert = 0;
  568. /* Dept of Truly Sickening Special-Case Kludges */
  569. if (p->next + 5 < p->end && strncmp(p->next, "[:<:]]", 6) == 0) {
  570. EMIT(OBOW, 0);
  571. NEXTn(6);
  572. return;
  573. }
  574. if (p->next + 5 < p->end && strncmp(p->next, "[:>:]]", 6) == 0) {
  575. EMIT(OEOW, 0);
  576. NEXTn(6);
  577. return;
  578. }
  579. if (EAT('^'))
  580. invert++; /* make note to invert set at end */
  581. if (EAT(']'))
  582. CHadd(cs, ']');
  583. else if (EAT('-'))
  584. CHadd(cs, '-');
  585. while (MORE() && PEEK() != ']' && !SEETWO('-', ']'))
  586. p_b_term(p, cs);
  587. if (EAT('-'))
  588. CHadd(cs, '-');
  589. if(MUSTEAT(']', REG_EBRACK)) {}
  590. if (p->error != 0) /* don't mess things up further */
  591. return;
  592. if (p->g->cflags&REG_ICASE) {
  593. register int i;
  594. register int ci;
  595. for (i = p->g->csetsize - 1; i >= 0; i--)
  596. if (CHIN(cs, i) && my_isalpha(p->charset,i)) {
  597. ci = othercase(p->charset,i);
  598. if (ci != i)
  599. CHadd(cs, ci);
  600. }
  601. if (cs->multis != NULL)
  602. mccase(p, cs);
  603. }
  604. if (invert) {
  605. register int i;
  606. for (i = p->g->csetsize - 1; i >= 0; i--)
  607. if (CHIN(cs, i))
  608. CHsub(cs, i);
  609. else
  610. CHadd(cs, i);
  611. if (p->g->cflags&REG_NEWLINE)
  612. CHsub(cs, 'n');
  613. if (cs->multis != NULL)
  614. mcinvert(p, cs);
  615. }
  616. assert(cs->multis == NULL); /* xxx */
  617. if (nch(p, cs) == 1) { /* optimize singleton sets */
  618. ordinary(p, firstch(p, cs));
  619. freeset(p, cs);
  620. } else
  621. EMIT(OANYOF, freezeset(p, cs));
  622. }
  623. /*
  624.  - p_b_term - parse one term of a bracketed character list
  625.  == static void p_b_term(register struct parse *p, register cset *cs);
  626.  */
  627. static void
  628. p_b_term(p, cs)
  629. register struct parse *p;
  630. register cset *cs;
  631. {
  632. register char c;
  633. register char start, finish;
  634. register int i;
  635. /* classify what we've got */
  636. switch ((MORE()) ? PEEK() : '') {
  637. case '[':
  638. c = (MORE2()) ? PEEK2() : '';
  639. break;
  640. case '-':
  641. SETERROR(REG_ERANGE);
  642. return; /* NOTE RETURN */
  643. break;
  644. default:
  645. c = '';
  646. break;
  647. }
  648. switch (c) {
  649. case ':': /* character class */
  650. NEXT2();
  651. if(REQUIRE(MORE(), REG_EBRACK)) {}
  652. c = PEEK();
  653. if(REQUIRE(c != '-' && c != ']', REG_ECTYPE)) {}
  654. p_b_cclass(p, cs);
  655. if(REQUIRE(MORE(), REG_EBRACK)) {}
  656. if(REQUIRE(EATTWO(':', ']'), REG_ECTYPE)) {}
  657. break;
  658. case '=': /* equivalence class */
  659. NEXT2();
  660. if(REQUIRE(MORE(), REG_EBRACK)) {}
  661. c = PEEK();
  662. if(REQUIRE(c != '-' && c != ']', REG_ECOLLATE)) {}
  663. p_b_eclass(p, cs);
  664. if(REQUIRE(MORE(), REG_EBRACK)) {}
  665. if(REQUIRE(EATTWO('=', ']'), REG_ECOLLATE)) {}
  666. break;
  667. default: /* symbol, ordinary character, or range */
  668. /* xxx revision needed for multichar stuff */
  669. start = p_b_symbol(p);
  670. if (SEE('-') && MORE2() && PEEK2() != ']') {
  671. /* range */
  672. NEXT();
  673. if (EAT('-'))
  674. finish = '-';
  675. else
  676. finish = p_b_symbol(p);
  677. } else
  678. finish = start;
  679. /* xxx what about signed chars here... */
  680. if(REQUIRE(start <= finish, REG_ERANGE)) {}
  681. for (i = start; i <= finish; i++)
  682. CHadd(cs, i);
  683. break;
  684. }
  685. }
  686. /*
  687.  - p_b_cclass - parse a character-class name and deal with it
  688.  == static void p_b_cclass(register struct parse *p, register cset *cs);
  689.  */
  690. static void
  691. p_b_cclass(p, cs)
  692. register struct parse *p;
  693. register cset *cs;
  694. {
  695. register char *sp = p->next;
  696. register struct cclass *cp;
  697. register size_t len;
  698. while (MORE() && my_isalpha(p->charset,PEEK()))
  699. NEXT();
  700. len = p->next - sp;
  701. for (cp = cclasses; cp->name != NULL; cp++)
  702. if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '')
  703. break;
  704. if (cp->name == NULL) {
  705. /* oops, didn't find it */
  706. SETERROR(REG_ECTYPE);
  707. return;
  708. }
  709. #ifndef USE_ORIG_REGEX_CODE
  710. {
  711. register size_t i;
  712. for (i=1 ; i<256 ; i++)
  713. if (p->charset->ctype[i+1] & cp->mask)
  714. CHadd(cs, i);
  715. }
  716. #else
  717. {
  718. register char *u = (char*) cp->chars;
  719. register char c;
  720. while ((c = *u++) != '')
  721. CHadd(cs, c);
  722. for (u = (char*) cp->multis; *u != ''; u += strlen(u) + 1)
  723. MCadd(p, cs, u);
  724. }
  725. #endif
  726. }
  727. /*
  728.  - p_b_eclass - parse an equivalence-class name and deal with it
  729.  == static void p_b_eclass(register struct parse *p, register cset *cs);
  730.  *
  731.  * This implementation is incomplete. xxx
  732.  */
  733. static void
  734. p_b_eclass(p, cs)
  735. register struct parse *p;
  736. register cset *cs;
  737. {
  738. register char c;
  739. c = p_b_coll_elem(p, '=');
  740. CHadd(cs, c);
  741. }
  742. /*
  743.  - p_b_symbol - parse a character or [..]ed multicharacter collating symbol
  744.  == static char p_b_symbol(register struct parse *p);
  745.  */
  746. static char /* value of symbol */
  747. p_b_symbol(p)
  748. register struct parse *p;
  749. {
  750. register char value;
  751. if(REQUIRE(MORE(), REG_EBRACK)) {}
  752. if (!EATTWO('[', '.'))
  753. return(GETNEXT());
  754. /* collating symbol */
  755. value = p_b_coll_elem(p, '.');
  756. if(REQUIRE(EATTWO('.', ']'), REG_ECOLLATE)) {}
  757. return(value);
  758. }
  759. /*
  760.  - p_b_coll_elem - parse a collating-element name and look it up
  761.  == static char p_b_coll_elem(register struct parse *p, int endc);
  762.  */
  763. static char /* value of collating element */
  764. p_b_coll_elem(p, endc)
  765. register struct parse *p;
  766. int endc; /* name ended by endc,']' */
  767. {
  768. register char *sp = p->next;
  769. register struct cname *cp;
  770. #ifdef _WIN64
  771. register __int64 len;
  772. #else
  773. register int len;
  774. #endif
  775. while (MORE() && !SEETWO(endc, ']'))
  776. NEXT();
  777. if (!MORE()) {
  778. SETERROR(REG_EBRACK);
  779. return(0);
  780. }
  781. len = p->next - sp;
  782. for (cp = cnames; cp->name != NULL; cp++)
  783. if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '')
  784. return(cp->code); /* known name */
  785. if (len == 1)
  786. return(*sp); /* single character */
  787. SETERROR(REG_ECOLLATE); /* neither */
  788. return(0);
  789. }
  790. /*
  791.  - othercase - return the case counterpart of an alphabetic
  792.  == static char othercase(int ch);
  793.  */
  794. static char /* if no counterpart, return ch */
  795. othercase(charset,ch)
  796. CHARSET_INFO *charset;
  797. int ch;
  798. {
  799. /*
  800.   In MySQL some multi-byte character sets
  801.   have 'ctype' array but don't have 'to_lower'
  802.   and 'to_upper' arrays. In this case we handle
  803.   only basic latin letters a..z and A..Z.
  804.   
  805.   If 'to_lower' and 'to_upper' arrays are empty in a character set,
  806.   then my_isalpha(cs, ch) should never return TRUE for characters
  807.   other than basic latin letters. Otherwise it should be
  808.   considered as a mistake in character set definition.
  809. */
  810. assert(my_isalpha(charset,ch));
  811. if (my_isupper(charset,ch))
  812. {
  813. return(charset->to_lower ? my_tolower(charset,ch) :
  814.                           ch - 'A' + 'a');
  815. }
  816. else if (my_islower(charset,ch))
  817. {
  818. return(charset->to_upper ? my_toupper(charset,ch) :
  819.                           ch - 'a' + 'A');
  820. }
  821. else /* peculiar, but could happen */
  822. return(ch);
  823. }
  824. /*
  825.  - bothcases - emit a dualcase version of a two-case character
  826.  == static void bothcases(register struct parse *p, int ch);
  827.  *
  828.  * Boy, is this implementation ever a kludge...
  829.  */
  830. static void
  831. bothcases(p, ch)
  832. register struct parse *p;
  833. int ch;
  834. {
  835. register char *oldnext = p->next;
  836. register char *oldend = p->end;
  837. char bracket[3];
  838. assert(othercase(p->charset, ch) != ch); /* p_bracket() would recurse */
  839. p->next = bracket;
  840. p->end = bracket+2;
  841. bracket[0] = ch;
  842. bracket[1] = ']';
  843. bracket[2] = '';
  844. p_bracket(p);
  845. assert(p->next == bracket+2);
  846. p->next = oldnext;
  847. p->end = oldend;
  848. }
  849. /*
  850.  - ordinary - emit an ordinary character
  851.  == static void ordinary(register struct parse *p, register int ch);
  852.  */
  853. static void
  854. ordinary(p, ch)
  855. register struct parse *p;
  856. register int ch;
  857. {
  858. register cat_t *cap = p->g->categories;
  859. if ((p->g->cflags&REG_ICASE) && my_isalpha(p->charset,ch) && 
  860.      othercase(p->charset,ch) != ch)
  861. bothcases(p, ch);
  862. else {
  863. EMIT(OCHAR, (unsigned char)ch);
  864. if (cap[ch] == 0)
  865. cap[ch] = p->g->ncategories++;
  866. }
  867. }
  868. /*
  869.  - nonnewline - emit REG_NEWLINE version of OANY
  870.  == static void nonnewline(register struct parse *p);
  871.  *
  872.  * Boy, is this implementation ever a kludge...
  873.  */
  874. static void
  875. nonnewline(p)
  876. register struct parse *p;
  877. {
  878. register char *oldnext = p->next;
  879. register char *oldend = p->end;
  880. char bracket[4];
  881. p->next = bracket;
  882. p->end = bracket+3;
  883. bracket[0] = '^';
  884. bracket[1] = 'n';
  885. bracket[2] = ']';
  886. bracket[3] = '';
  887. p_bracket(p);
  888. assert(p->next == bracket+3);
  889. p->next = oldnext;
  890. p->end = oldend;
  891. }
  892. /*
  893.  - repeat - generate code for a bounded repetition, recursively if needed
  894.  == static void repeat(register struct parse *p, sopno start, int from, int to);
  895.  */
  896. static void
  897. repeat(p, start, from, to)
  898. register struct parse *p;
  899. sopno start; /* operand from here to end of strip */
  900. int from; /* repeated from this number */
  901. int to; /* to this number of times (maybe RE_INFINITY) */
  902. {
  903. register sopno finish = HERE();
  904. # define N 2
  905. # define INF 3
  906. # define REP(f, t) ((f)*8 + (t))
  907. # define MAP(n) (((n) <= 1) ? (n) : ((n) == RE_INFINITY) ? INF : N)
  908. register sopno copy;
  909. if (p->error != 0) /* head off possible runaway recursion */
  910. return;
  911. assert(from <= to);
  912. switch (REP(MAP(from), MAP(to))) {
  913. case REP(0, 0): /* must be user doing this */
  914. DROP(finish-start); /* drop the operand */
  915. break;
  916. case REP(0, 1): /* as x{1,1}? */
  917. case REP(0, N): /* as x{1,n}? */
  918. case REP(0, INF): /* as x{1,}? */
  919. /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
  920. INSERT(OCH_, start); /* offset is wrong... */
  921. repeat(p, start+1, 1, to);
  922. ASTERN(OOR1, start);
  923. AHEAD(start); /* ... fix it */
  924. EMIT(OOR2, 0);
  925. AHEAD(THERE());
  926. ASTERN(O_CH, THERETHERE());
  927. break;
  928. case REP(1, 1): /* trivial case */
  929. /* done */
  930. break;
  931. case REP(1, N): /* as x?x{1,n-1} */
  932. /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
  933. INSERT(OCH_, start);
  934. ASTERN(OOR1, start);
  935. AHEAD(start);
  936. EMIT(OOR2, 0); /* offset very wrong... */
  937. AHEAD(THERE()); /* ...so fix it */
  938. ASTERN(O_CH, THERETHERE());
  939. copy = dupl(p, start+1, finish+1);
  940. assert(copy == finish+4);
  941. repeat(p, copy, 1, to-1);
  942. break;
  943. case REP(1, INF): /* as x+ */
  944. INSERT(OPLUS_, start);
  945. ASTERN(O_PLUS, start);
  946. break;
  947. case REP(N, N): /* as xx{m-1,n-1} */
  948. copy = dupl(p, start, finish);
  949. repeat(p, copy, from-1, to-1);
  950. break;
  951. case REP(N, INF): /* as xx{n-1,INF} */
  952. copy = dupl(p, start, finish);
  953. repeat(p, copy, from-1, to);
  954. break;
  955. default: /* "can't happen" */
  956. SETERROR(REG_ASSERT); /* just in case */
  957. break;
  958. }
  959. }
  960. /*
  961.  - seterr - set an error condition
  962.  == static int seterr(register struct parse *p, int e);
  963.  */
  964. static int /* useless but makes type checking happy */
  965. seterr(p, e)
  966. register struct parse *p;
  967. int e;
  968. {
  969. if (p->error == 0) /* keep earliest error condition */
  970. p->error = e;
  971. p->next = nuls; /* try to bring things to a halt */
  972. p->end = nuls;
  973. return(0); /* make the return value well-defined */
  974. }
  975. /*
  976.  - allocset - allocate a set of characters for []
  977.  == static cset *allocset(register struct parse *p);
  978.  */
  979. static cset *
  980. allocset(p)
  981. register struct parse *p;
  982. {
  983. register int no = p->g->ncsets++;
  984. register size_t nc;
  985. register size_t nbytes;
  986. register cset *cs;
  987. register size_t css = (size_t)p->g->csetsize;
  988. register int i;
  989. if (no >= p->ncsalloc) { /* need another column of space */
  990. p->ncsalloc += CHAR_BIT;
  991. nc = p->ncsalloc;
  992. assert(nc % CHAR_BIT == 0);
  993. nbytes = nc / CHAR_BIT * css;
  994. if (p->g->sets == NULL)
  995. p->g->sets = (cset *)malloc(nc * sizeof(cset));
  996. else
  997. p->g->sets = (cset *)realloc((char *)p->g->sets,
  998. nc * sizeof(cset));
  999. if (p->g->setbits == NULL)
  1000. p->g->setbits = (uch *)malloc(nbytes);
  1001. else {
  1002. p->g->setbits = (uch *)realloc((char *)p->g->setbits,
  1003. nbytes);
  1004. /* xxx this isn't right if setbits is now NULL */
  1005. for (i = 0; i < no; i++)
  1006. p->g->sets[i].ptr = p->g->setbits + css*(i/CHAR_BIT);
  1007. }
  1008. if (p->g->sets != NULL && p->g->setbits != NULL)
  1009. (void) memset((char *)p->g->setbits + (nbytes - css),
  1010. 0, css);
  1011. else {
  1012. no = 0;
  1013. SETERROR(REG_ESPACE);
  1014. /* caller's responsibility not to do set ops */
  1015. }
  1016. }
  1017. assert(p->g->sets != NULL); /* xxx */
  1018. cs = &p->g->sets[no];
  1019. cs->ptr = p->g->setbits + css*((no)/CHAR_BIT);
  1020. cs->mask = 1 << ((no) % CHAR_BIT);
  1021. cs->hash = 0;
  1022. cs->smultis = 0;
  1023. cs->multis = NULL;
  1024. return(cs);
  1025. }
  1026. /*
  1027.  - freeset - free a now-unused set
  1028.  == static void freeset(register struct parse *p, register cset *cs);
  1029.  */
  1030. static void
  1031. freeset(p, cs)
  1032. register struct parse *p;
  1033. register cset *cs;
  1034. {
  1035. register size_t i;
  1036. register cset *top = &p->g->sets[p->g->ncsets];
  1037. register size_t css = (size_t)p->g->csetsize;
  1038. for (i = 0; i < css; i++)
  1039.   CHsub(cs, i);
  1040. if (cs == top-1) /* recover only the easy case */
  1041.   p->g->ncsets--;
  1042. }
  1043. /*
  1044.  - freezeset - final processing on a set of characters
  1045.  == static int freezeset(register struct parse *p, register cset *cs);
  1046.  *
  1047.  * The main task here is merging identical sets.  This is usually a waste
  1048.  * of time (although the hash code minimizes the overhead), but can win
  1049.  * big if REG_ICASE is being used.  REG_ICASE, by the way, is why the hash
  1050.  * is done using addition rather than xor -- all ASCII [aA] sets xor to
  1051.  * the same value!
  1052.  */
  1053. static int /* set number */
  1054. freezeset(p, cs)
  1055. register struct parse *p;
  1056. register cset *cs;
  1057. {
  1058. register uch h = cs->hash;
  1059. register size_t i;
  1060. register cset *top = &p->g->sets[p->g->ncsets];
  1061. register cset *cs2;
  1062. register size_t css = (size_t)p->g->csetsize;
  1063. /* look for an earlier one which is the same */
  1064. for (cs2 = &p->g->sets[0]; cs2 < top; cs2++)
  1065. if (cs2->hash == h && cs2 != cs) {
  1066. /* maybe */
  1067. for (i = 0; i < css; i++)
  1068. if (!!CHIN(cs2, i) != !!CHIN(cs, i))
  1069. break; /* no */
  1070. if (i == css)
  1071. break; /* yes */
  1072. }
  1073. if (cs2 < top) { /* found one */
  1074. freeset(p, cs);
  1075. cs = cs2;
  1076. }
  1077. return((int)(cs - p->g->sets));
  1078. }
  1079. /*
  1080.  - firstch - return first character in a set (which must have at least one)
  1081.  == static int firstch(register struct parse *p, register cset *cs);
  1082.  */
  1083. static int /* character; there is no "none" value */
  1084. firstch(p, cs)
  1085. register struct parse *p;
  1086. register cset *cs;
  1087. {
  1088. register size_t i;
  1089. register size_t css = (size_t)p->g->csetsize;
  1090. for (i = 0; i < css; i++)
  1091. if (CHIN(cs, i))
  1092. return((char)i);
  1093. assert(never);
  1094. return(0); /* arbitrary */
  1095. }
  1096. /*
  1097.  - nch - number of characters in a set
  1098.  == static int nch(register struct parse *p, register cset *cs);
  1099.  */
  1100. static int
  1101. nch(p, cs)
  1102. register struct parse *p;
  1103. register cset *cs;
  1104. {
  1105. register size_t i;
  1106. register size_t css = (size_t)p->g->csetsize;
  1107. register int n = 0;
  1108. for (i = 0; i < css; i++)
  1109. if (CHIN(cs, i))
  1110. n++;
  1111. return(n);
  1112. }
  1113. #ifdef USE_ORIG_REGEX_CODE
  1114. /*
  1115.  - mcadd - add a collating element to a cset
  1116.  == static void mcadd(register struct parse *p, register cset *cs, 
  1117.  == register char *cp);
  1118.  */
  1119. static void
  1120. mcadd(p, cs, cp)
  1121. register struct parse *p;
  1122. register cset *cs;
  1123. register char *cp;
  1124. {
  1125. register size_t oldend = cs->smultis;
  1126. cs->smultis += strlen(cp) + 1;
  1127. if (cs->multis == NULL)
  1128. cs->multis = malloc(cs->smultis);
  1129. else
  1130. cs->multis = realloc(cs->multis, cs->smultis);
  1131. if (cs->multis == NULL) {
  1132. SETERROR(REG_ESPACE);
  1133. return;
  1134. }
  1135. (void) strcpy(cs->multis + oldend - 1, cp);
  1136. cs->multis[cs->smultis - 1] = '';
  1137. }
  1138. #endif
  1139. #ifdef NOT_USED
  1140. /*
  1141.  - mcsub - subtract a collating element from a cset
  1142.  == static void mcsub(register cset *cs, register char *cp);
  1143.  */
  1144. static void
  1145. mcsub(cs, cp)
  1146. register cset *cs;
  1147. register char *cp;
  1148. {
  1149. register char *fp = mcfind(cs, cp);
  1150. register size_t len = strlen(fp);
  1151. assert(fp != NULL);
  1152. (void) memmove(fp, fp + len + 1,
  1153. cs->smultis - (fp + len + 1 - cs->multis));
  1154. cs->smultis -= len;
  1155. if (cs->smultis == 0) {
  1156. free(cs->multis);
  1157. cs->multis = NULL;
  1158. return;
  1159. }
  1160. cs->multis = realloc(cs->multis, cs->smultis);
  1161. assert(cs->multis != NULL);
  1162. }
  1163. /*
  1164.  - mcin - is a collating element in a cset?
  1165.  == static int mcin(register cset *cs, register char *cp);
  1166.  */
  1167. static int
  1168. mcin(cs, cp)
  1169. register cset *cs;
  1170. register char *cp;
  1171. {
  1172. return(mcfind(cs, cp) != NULL);
  1173. }
  1174. /*
  1175.  - mcfind - find a collating element in a cset
  1176.  == static char *mcfind(register cset *cs, register char *cp);
  1177.  */
  1178. static char *
  1179. mcfind(cs, cp)
  1180. register cset *cs;
  1181. register char *cp;
  1182. {
  1183. register char *p;
  1184. if (cs->multis == NULL)
  1185. return(NULL);
  1186. for (p = cs->multis; *p != ''; p += strlen(p) + 1)
  1187. if (strcmp(cp, p) == 0)
  1188. return(p);
  1189. return(NULL);
  1190. }
  1191. #endif
  1192. /*
  1193.  - mcinvert - invert the list of collating elements in a cset
  1194.  == static void mcinvert(register struct parse *p, register cset *cs);
  1195.  *
  1196.  * This would have to know the set of possibilities.  Implementation
  1197.  * is deferred.
  1198.  */
  1199. static void
  1200. mcinvert(p, cs)
  1201.   register struct parse *p __attribute__((unused));
  1202.   register cset *cs __attribute__((unused));
  1203. {
  1204. assert(cs->multis == NULL); /* xxx */
  1205. }
  1206. /*
  1207.  - mccase - add case counterparts of the list of collating elements in a cset
  1208.  == static void mccase(register struct parse *p, register cset *cs);
  1209.  *
  1210.  * This would have to know the set of possibilities.  Implementation
  1211.  * is deferred.
  1212.  */
  1213. static void
  1214. mccase(p, cs)
  1215. register struct parse *p __attribute__((unused));
  1216. register cset *cs __attribute__((unused));
  1217. {
  1218. assert(cs->multis == NULL); /* xxx */
  1219. }
  1220. /*
  1221.  - isinsets - is this character in any sets?
  1222.  == static int isinsets(register struct re_guts *g, int c);
  1223.  */
  1224. static int /* predicate */
  1225. isinsets(g, c)
  1226. register struct re_guts *g;
  1227. int c;
  1228. {
  1229. register uch *col;
  1230. register int i;
  1231. register int ncols = (g->ncsets+(CHAR_BIT-1)) / CHAR_BIT;
  1232. register unsigned uc = (unsigned char)c;
  1233. for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize)
  1234. if (col[uc] != 0)
  1235. return(1);
  1236. return(0);
  1237. }
  1238. /*
  1239.  - samesets - are these two characters in exactly the same sets?
  1240.  == static int samesets(register struct re_guts *g, int c1, int c2);
  1241.  */
  1242. static int /* predicate */
  1243. samesets(g, c1, c2)
  1244. register struct re_guts *g;
  1245. int c1;
  1246. int c2;
  1247. {
  1248. register uch *col;
  1249. register int i;
  1250. register int ncols = (g->ncsets+(CHAR_BIT-1)) / CHAR_BIT;
  1251. register unsigned uc1 = (unsigned char)c1;
  1252. register unsigned uc2 = (unsigned char)c2;
  1253. for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize)
  1254. if (col[uc1] != col[uc2])
  1255. return(0);
  1256. return(1);
  1257. }
  1258. /*
  1259.  - categorize - sort out character categories
  1260.  == static void categorize(struct parse *p, register struct re_guts *g);
  1261.  */
  1262. static void
  1263. categorize(p, g)
  1264. struct parse *p;
  1265. register struct re_guts *g;
  1266. {
  1267. register cat_t *cats = g->categories;
  1268. register int c;
  1269. register int c2;
  1270. register cat_t cat;
  1271. /* avoid making error situations worse */
  1272. if (p->error != 0)
  1273. return;
  1274. for (c = CHAR_MIN; c <= CHAR_MAX; c++)
  1275. if (cats[c] == 0 && isinsets(g, c)) {
  1276. cat = g->ncategories++;
  1277. cats[c] = cat;
  1278. for (c2 = c+1; c2 <= CHAR_MAX; c2++)
  1279. if (cats[c2] == 0 && samesets(g, c, c2))
  1280. cats[c2] = cat;
  1281. }
  1282. }
  1283. /*
  1284.  - dupl - emit a duplicate of a bunch of sops
  1285.  == static sopno dupl(register struct parse *p, sopno start, sopno finish);
  1286.  */
  1287. static sopno /* start of duplicate */
  1288. dupl(p, start, finish)
  1289. register struct parse *p;
  1290. sopno start; /* from here */
  1291. sopno finish; /* to this less one */
  1292. {
  1293. register sopno ret = HERE();
  1294. register sopno len = finish - start;
  1295. assert(finish >= start);
  1296. if (len == 0)
  1297. return(ret);
  1298. enlarge(p, p->ssize + len); /* this many unexpected additions */
  1299. assert(p->ssize >= p->slen + len);
  1300. (void) memcpy((char *)(p->strip + p->slen),
  1301. (char *)(p->strip + start), (size_t)len*sizeof(sop));
  1302. p->slen += len;
  1303. return(ret);
  1304. }
  1305. /*
  1306.  - doemit - emit a strip operator
  1307.  == static void doemit(register struct parse *p, sop op, size_t opnd);
  1308.  *
  1309.  * It might seem better to implement this as a macro with a function as
  1310.  * hard-case backup, but it's just too big and messy unless there are
  1311.  * some changes to the data structures.  Maybe later.
  1312.  */
  1313. static void
  1314. doemit(p, op, opnd)
  1315. register struct parse *p;
  1316. sop op;
  1317. size_t opnd;
  1318. {
  1319. /* avoid making error situations worse */
  1320. if (p->error != 0)
  1321. return;
  1322. /* deal with oversize operands ("can't happen", more or less) */
  1323. assert(opnd < 1<<OPSHIFT);
  1324. /* deal with undersized strip */
  1325. if (p->slen >= p->ssize)
  1326. enlarge(p, (p->ssize+1) / 2 * 3); /* +50% */
  1327. assert(p->slen < p->ssize);
  1328. /* finally, it's all reduced to the easy case */
  1329. p->strip[p->slen++] = SOP(op, opnd);
  1330. }
  1331. /*
  1332.  - doinsert - insert a sop into the strip
  1333.  == static void doinsert(register struct parse *p, sop op, size_t opnd, sopno pos);
  1334.  */
  1335. static void
  1336. doinsert(p, op, opnd, pos)
  1337. register struct parse *p;
  1338. sop op;
  1339. size_t opnd;
  1340. sopno pos;
  1341. {
  1342. register sopno sn;
  1343. register sop s;
  1344. register int i;
  1345. /* avoid making error situations worse */
  1346. if (p->error != 0)
  1347. return;
  1348. sn = HERE();
  1349. EMIT(op, opnd); /* do checks, ensure space */
  1350. assert(HERE() == sn+1);
  1351. s = p->strip[sn];
  1352. /* adjust paren pointers */
  1353. assert(pos > 0);
  1354. for (i = 1; i < NPAREN; i++) {
  1355. if (p->pbegin[i] >= pos) {
  1356. p->pbegin[i]++;
  1357. }
  1358. if (p->pend[i] >= pos) {
  1359. p->pend[i]++;
  1360. }
  1361. }
  1362. {
  1363.           int length=(HERE()-pos-1)*sizeof(sop);
  1364.           bmove_upp((char *) &p->strip[pos+1]+length,
  1365.                     (char *) &p->strip[pos]+length,
  1366.                     length);
  1367.         }
  1368. #ifdef OLD_CODE
  1369.         memmove((char *)&p->strip[pos+1], (char *)&p->strip[pos],
  1370.                                                 (HERE()-pos-1)*sizeof(sop));
  1371. #endif
  1372. p->strip[pos] = s;
  1373. }
  1374. /*
  1375.  - dofwd - complete a forward reference
  1376.  == static void dofwd(register struct parse *p, sopno pos, sop value);
  1377.  */
  1378. static void
  1379. dofwd(p, pos, value)
  1380. register struct parse *p;
  1381. register sopno pos;
  1382. sop value;
  1383. {
  1384. /* avoid making error situations worse */
  1385. if (p->error != 0)
  1386. return;
  1387. assert(value < 1<<OPSHIFT);
  1388. p->strip[pos] = OP(p->strip[pos]) | value;
  1389. }
  1390. /*
  1391.  - enlarge - enlarge the strip
  1392.  == static void enlarge(register struct parse *p, sopno size);
  1393.  */
  1394. static void
  1395. enlarge(p, size)
  1396. register struct parse *p;
  1397. register sopno size;
  1398. {
  1399. register sop *sp;
  1400. if (p->ssize >= size)
  1401. return;
  1402. sp = (sop *)realloc(p->strip, size*sizeof(sop));
  1403. if (sp == NULL) {
  1404. SETERROR(REG_ESPACE);
  1405. return;
  1406. }
  1407. p->strip = sp;
  1408. p->ssize = size;
  1409. }
  1410. /*
  1411.  - stripsnug - compact the strip
  1412.  == static void stripsnug(register struct parse *p, register struct re_guts *g);
  1413.  */
  1414. static void
  1415. stripsnug(p, g)
  1416. register struct parse *p;
  1417. register struct re_guts *g;
  1418. {
  1419. g->nstates = p->slen;
  1420. g->strip = (sop *)realloc((char *)p->strip, p->slen * sizeof(sop));
  1421. if (g->strip == NULL) {
  1422. SETERROR(REG_ESPACE);
  1423. g->strip = p->strip;
  1424. }
  1425. }
  1426. /*
  1427.  - findmust - fill in must and mlen with longest mandatory literal string
  1428.  == static void findmust(register struct parse *p, register struct re_guts *g);
  1429.  *
  1430.  * This algorithm could do fancy things like analyzing the operands of |
  1431.  * for common subsequences.  Someday.  This code is simple and finds most
  1432.  * of the interesting cases.
  1433.  *
  1434.  * Note that must and mlen got initialized during setup.
  1435.  */
  1436. static void
  1437. findmust(p, g)
  1438. struct parse *p;
  1439. register struct re_guts *g;
  1440. {
  1441. register sop *scan;
  1442. sop *start;
  1443. register sop *newstart;
  1444. register sopno newlen;
  1445. register sop s;
  1446. register char *cp;
  1447. register sopno i;
  1448. LINT_INIT(start); LINT_INIT(newstart);
  1449. /* avoid making error situations worse */
  1450. if (p->error != 0)
  1451. return;
  1452. /* find the longest OCHAR sequence in strip */
  1453. newlen = 0;
  1454. scan = g->strip + 1;
  1455. do {
  1456. s = *scan++;
  1457. switch (OP(s)) {
  1458. case OCHAR: /* sequence member */
  1459. if (newlen == 0) /* new sequence */
  1460. newstart = scan - 1;
  1461. newlen++;
  1462. break;
  1463. case OPLUS_: /* things that don't break one */
  1464. case OLPAREN:
  1465. case ORPAREN:
  1466. break;
  1467. case OQUEST_: /* things that must be skipped */
  1468. case OCH_:
  1469. scan--;
  1470. do {
  1471. scan += OPND(s);
  1472. s = *scan;
  1473. /* assert() interferes w debug printouts */
  1474. if (OP(s) != O_QUEST && OP(s) != O_CH &&
  1475. OP(s) != OOR2) {
  1476. g->iflags |= BAD;
  1477. return;
  1478. }
  1479. } while (OP(s) != O_QUEST && OP(s) != O_CH);
  1480. /* fallthrough */
  1481. default: /* things that break a sequence */
  1482. if (newlen > g->mlen) { /* ends one */
  1483. start = newstart;
  1484. g->mlen = newlen;
  1485. }
  1486. newlen = 0;
  1487. break;
  1488. }
  1489. } while (OP(s) != OEND);
  1490. if (g->mlen == 0) /* there isn't one */
  1491. return;
  1492. /* turn it into a character string */
  1493. g->must = malloc((size_t)g->mlen + 1);
  1494. if (g->must == NULL) { /* argh; just forget it */
  1495. g->mlen = 0;
  1496. return;
  1497. }
  1498. cp = g->must;
  1499. scan = start;
  1500. for (i = g->mlen; i > 0; i--) {
  1501. while (OP(s = *scan++) != OCHAR)
  1502. continue;
  1503. assert(cp < g->must + g->mlen);
  1504. *cp++ = (char)OPND(s);
  1505. }
  1506. assert(cp == g->must + g->mlen);
  1507. *cp++ = ''; /* just on general principles */
  1508. }
  1509. /*
  1510.  - pluscount - count + nesting
  1511.  == static sopno pluscount(register struct parse *p, register struct re_guts *g);
  1512.  */
  1513. static sopno /* nesting depth */
  1514. pluscount(p, g)
  1515. struct parse *p;
  1516. register struct re_guts *g;
  1517. {
  1518. register sop *scan;
  1519. register sop s;
  1520. register sopno plusnest = 0;
  1521. register sopno maxnest = 0;
  1522. if (p->error != 0)
  1523. return(0); /* there may not be an OEND */
  1524. scan = g->strip + 1;
  1525. do {
  1526. s = *scan++;
  1527. switch (OP(s)) {
  1528. case OPLUS_:
  1529. plusnest++;
  1530. break;
  1531. case O_PLUS:
  1532. if (plusnest > maxnest)
  1533. maxnest = plusnest;
  1534. plusnest--;
  1535. break;
  1536. }
  1537. } while (OP(s) != OEND);
  1538. if (plusnest != 0)
  1539. g->iflags |= BAD;
  1540. return(maxnest);
  1541. }