开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数据库系统 > MySQL数据库 > 查看源码
regcomp.c
资源名称：mysql-3.23.35.tar.gz　[点击查看]
上传用户：tsgydb
上传日期：2007-04-14
资源大小：10674k
文件大小：37k
源码类别：

MySQL数据库

开发平台：

Visual C++

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