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

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数据库系统 > 查看源码
regcomp.c
资源名称：postgresql-6.5.2.tar.gz　[点击查看]
上传用户：blenddy
上传日期：2007-01-07
资源大小：6495k
文件大小：42k
源码类别：

数据库系统

开发平台：

Unix_Linux

regcomp.c：源码内容
  1. /*-
  2.  * Copyright (c) 1992, 1993, 1994 Henry Spencer.
  3.  * Copyright (c) 1992, 1993, 1994
  4.  * The Regents of the University of California.  All rights reserved.
  5.  *
  6.  * This code is derived from software contributed to Berkeley by
  7.  * Henry Spencer.
  8.  *
  9.  * Redistribution and use in source and binary forms, with or without
  10.  * modification, are permitted provided that the following conditions
  11.  * are met:
  12.  * 1. Redistributions of source code must retain the above copyright
  13.  *   notice, this list of conditions and the following disclaimer.
  14.  * 2. Redistributions in binary form must reproduce the above copyright
  15.  *   notice, this list of conditions and the following disclaimer in the
  16.  *   documentation and/or other materials provided with the distribution.
  17.  * 3. All advertising materials mentioning features or use of this software
  18.  *   must display the following acknowledgement:
  19.  * This product includes software developed by the University of
  20.  * California, Berkeley and its contributors.
  21.  * 4. Neither the name of the University nor the names of its contributors
  22.  *   may be used to endorse or promote products derived from this software
  23.  *   without specific prior written permission.
  24.  *
  25.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  26.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  27.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  28.  * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  29.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  30.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  31.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  32.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  33.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  34.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  35.  * SUCH DAMAGE.
  36.  *
  37.  * @(#)regcomp.c 8.5 (Berkeley) 3/20/94
  38.  */
  40. #if defined(LIBC_SCCS) && !defined(lint)
  41. static char sccsid[] = "@(#)regcomp.c 8.5 (Berkeley) 3/20/94";
  43. #endif  /* LIBC_SCCS and not lint */
  45. #include <sys/types.h>
  46. #include <stdio.h>
  47. #include <string.h>
  48. #include <ctype.h>
  49. #include <limits.h>
  50. #include <stdlib.h>
  51. #include <assert.h>
  53. #include <regex/regex.h>
  54. #include <regex/utils.h>
  55. #include <regex/regex2.h>
  56. #include <regex/cclass.h>
  57. #include <regex/cname.h>
  59. /*
  60.  * parse structure, passed up and down to avoid global variables and
  61.  * other clumsinesses
  62.  */
  63. struct parse
  64. {
  65. pg_wchar   *next; /* next character in RE */
  66. pg_wchar   *end; /* end of string (-> NUL normally) */
  67. int error; /* has an error been seen? */
  68. sop    *strip; /* malloced strip */
  69. sopno ssize; /* malloced strip size (allocated) */
  70. sopno slen; /* malloced strip length (used) */
  71. int ncsalloc; /* number of csets allocated */
  72. struct re_guts *g;
  73. #define  NPAREN  10 /* we need to remember () 1-9 for back
  74.  * refs */
  75. sopno pbegin[NPAREN]; /* -> ( ([0] unused) */
  76. sopno pend[NPAREN]; /* -> ) ([0] unused) */
  77. };
  79. /* ========= begin header generated by ./mkh ========= */
  80. #ifdef __cplusplus
  81. extern "C"
  82. {
  83. #endif
  85. /* === regcomp.c === */
  86. static void p_ere(struct parse * p, int stop);
  87. static void p_ere_exp(struct parse * p);
  88. static void p_str(struct parse * p);
  89. static void p_bre(struct parse * p, int end1, int end2);
  90. static int p_simp_re(struct parse * p, int starordinary);
  91. static int p_count(struct parse * p);
  92. static void p_bracket(struct parse * p);
  93. static void p_b_term(struct parse * p, cset *cs);
  94. static void p_b_cclass(struct parse * p, cset *cs);
  95. static void p_b_eclass(struct parse * p, cset *cs);
  96. static pg_wchar p_b_symbol(struct parse * p);
  97. static char p_b_coll_elem(struct parse * p, int endc);
  98. #ifdef MULTIBYTE
  99. static unsigned char othercase(int ch);
  100. #else
  101. static char othercase(int ch);
  102. #endif
  103. static void bothcases(struct parse * p, int ch);
  104. static void ordinary(struct parse * p, int ch);
  105. static void nonnewline(struct parse * p);
  106. static void repeat(struct parse * p, sopno start, int from, int to);
  107. static int seterr(struct parse * p, int e);
  108. static cset *allocset(struct parse * p);
  109. static void freeset(struct parse * p, cset *cs);
  110. static int freezeset(struct parse * p, cset *cs);
  111. static int firstch(struct parse * p, cset *cs);
  112. static int nch(struct parse * p, cset *cs);
  113. static void mcadd(struct parse * p, cset *cs, char *cp);
  114. static void mcinvert(struct parse * p, cset *cs);
  115. static void mccase(struct parse * p, cset *cs);
  116. static int isinsets(struct re_guts * g, int c);
  117. static int samesets(struct re_guts * g, int c1, int c2);
  118. static void categorize(struct parse * p, struct re_guts * g);
  119. static sopno dupl(struct parse * p, sopno start, sopno finish);
  120. static void doemit(struct parse * p, sop op, size_t opnd);
  121. static void doinsert(struct parse * p, sop op, size_t opnd, sopno pos);
  122. static void dofwd(struct parse * p, sopno pos, sop value);
  123. static void enlarge(struct parse * p, sopno size);
  124. static void stripsnug(struct parse * p, struct re_guts * g);
  125. static void findmust(struct parse * p, struct re_guts * g);
  126. static sopno pluscount(struct parse * p, struct re_guts * g);
  127. static int pg_isdigit(int c);
  128. static int pg_isalpha(int c);
  129. static int pg_isupper(int c);
  130. static int pg_islower(int c);
  132. #ifdef __cplusplus
  133. }
  135. #endif
  136. /* ========= end header generated by ./mkh ========= */
  138. static pg_wchar nuls[10]; /* place to point scanner in event of
  139.  * error */
  141. /*
  142.  * macros for use with parse structure
  143.  * BEWARE: these know that the parse structure is named `p' !!!
  144.  */
  145. #define PEEK() (*p->next)
  146. #define PEEK2() (*(p->next+1))
  147. #define MORE() (p->next < p->end)
  148. #define MORE2() (p->next+1 < p->end)
  149. #define SEE(c) (MORE() && PEEK() == (c))
  150. #define SEETWO(a, b) (MORE() && MORE2() && PEEK() == (a) && PEEK2() == (b))
  151. #define EAT(c) ((SEE(c)) ? (NEXT(), 1) : 0)
  152. #define EATTWO(a, b) ((SEETWO(a, b)) ? (NEXT2(), 1) : 0)
  153. #define NEXT() (p->next++)
  154. #define NEXT2() (p->next += 2)
  155. #define NEXTn(n) (p->next += (n))
  156. #define GETNEXT() (*p->next++)
  157. #define SETERROR(e) seterr(p, (e))
  158. #define REQUIRE(co, e) if (!(co)) SETERROR(e)
  159. #define MUSTSEE(c, e) REQUIRE(MORE() && PEEK() == (c), e)
  160. #define MUSTEAT(c, e) REQUIRE(MORE() && GETNEXT() == (c), e)
  161. #define MUSTNOTSEE(c, e) REQUIRE(!MORE() || PEEK() != (c), e)
  162. #define EMIT(op, sopnd) doemit(p, (sop)(op), (size_t)(sopnd))
  163. #define INSERT(op, pos) doinsert(p, (sop)(op), HERE()-(pos)+1, pos)
  164. #define AHEAD(pos) dofwd(p, pos, HERE()-(pos))
  165. #define ASTERN(sop, pos) EMIT(sop, HERE()-pos)
  166. #define HERE() (p->slen)
  167. #define THERE() (p->slen - 1)
  168. #define THERETHERE() (p->slen - 2)
  169. #define DROP(n) (p->slen -= (n))
  171. #ifndef NDEBUG
  172. static int never = 0; /* for use in asserts; shuts lint up */
  174. #else
  175. #define never 0 /* some <assert.h>s have bugs too */
  176. #endif
  178. /*
  179.  - regcomp - interface for parser and compilation
  180.  = extern int regcomp(regex_t *, const char *, int);
  181.  = #define REG_BASIC 0000
  182.  = #define REG_EXTENDED 0001
  183.  = #define REG_ICASE 0002
  184.  = #define REG_NOSUB 0004
  185.  = #define REG_NEWLINE 0010
  186.  = #define REG_NOSPEC 0020
  187.  = #define REG_PEND 0040
  188.  = #define REG_DUMP 0200
  189.  */
  190. int /* 0 success, otherwise REG_something */
  191. pg95_regcomp(preg, pattern, cflags)
  192. regex_t    *preg;
  193. const char *pattern;
  194. int cflags;
  195. {
  196. struct parse pa;
  197. struct re_guts *g;
  198. struct parse *p = &pa;
  199. int i;
  200. size_t len;
  202. #ifdef MULTIBYTE
  203. pg_wchar   *wcp;
  205. #endif
  207. #ifdef REDEBUG
  208. #define  GOODFLAGS(f)  (f)
  209. #else
  210. #define  GOODFLAGS(f)  ((f)&~REG_DUMP)
  211. #endif
  213. cflags = GOODFLAGS(cflags);
  214. if ((cflags & REG_EXTENDED) && (cflags & REG_NOSPEC))
  215. return REG_INVARG;
  217. if (cflags & REG_PEND)
  218. {
  219. #ifdef MULTIBYTE
  220. wcp = preg->patsave;
  221. if (preg->re_endp < wcp)
  222. return REG_INVARG;
  223. len = preg->re_endp - wcp;
  224. #else
  225. if (preg->re_endp < pattern)
  226. return REG_INVARG;
  227. len = preg->re_endp - pattern;
  228. #endif
  229. }
  230. else
  231. {
  232. #ifdef MULTIBYTE
  233. wcp = (pg_wchar *) malloc((strlen(pattern) + 1) * sizeof(pg_wchar));
  234. if (wcp == NULL)
  235. return REG_ESPACE;
  236. preg->patsave = wcp;
  237. (void) pg_mb2wchar((unsigned char *) pattern, wcp);
  238. len = pg_wchar_strlen(wcp);
  239. #else
  241. len = strlen((char *) pattern);
  242. #endif
  243. }
  245. /* do the mallocs early so failure handling is easy */
  246. g = (struct re_guts *) malloc(sizeof(struct re_guts) +
  247.   (NC - 1) * sizeof(cat_t));
  248. if (g == NULL)
  249. return REG_ESPACE;
  250. p->ssize = len / (size_t) 2 *(size_t) 3 + (size_t) 1; /* ugh */
  252. p->strip = (sop *) malloc(p->ssize * sizeof(sop));
  253. p->slen = 0;
  254. if (p->strip == NULL)
  255. {
  256. free((char *) g);
  257. return REG_ESPACE;
  258. }
  260. /* set things up */
  261. p->g = g;
  262. #ifdef MULTIBYTE
  263. p->next = wcp;
  264. #else
  265. p->next = (pg_wchar *) pattern; /* convenience; we do not modify
  266.  * it */
  267. #endif
  268. p->end = p->next + len;
  269. p->error = 0;
  270. p->ncsalloc = 0;
  271. for (i = 0; i < NPAREN; i++)
  272. {
  273. p->pbegin[i] = 0;
  274. p->pend[i] = 0;
  275. }
  276. g->csetsize = NC;
  277. g->sets = NULL;
  278. g->setbits = NULL;
  279. g->ncsets = 0;
  280. g->cflags = cflags;
  281. g->iflags = 0;
  282. g->nbol = 0;
  283. g->neol = 0;
  284. g->must = NULL;
  285. g->mlen = 0;
  286. g->nsub = 0;
  287. g->ncategories = 1; /* category 0 is "everything else" */
  288. g->categories = &g->catspace[-(CHAR_MIN)];
  289. memset((char *) g->catspace, 0, NC * sizeof(cat_t));
  290. g->backrefs = 0;
  292. /* do it */
  293. EMIT(OEND, 0);
  294. g->firststate = THERE();
  295. if (cflags & REG_EXTENDED)
  296. p_ere(p, OUT);
  297. else if (cflags & REG_NOSPEC)
  298. p_str(p);
  299. else
  300. p_bre(p, OUT, OUT);
  301. EMIT(OEND, 0);
  302. g->laststate = THERE();
  304. /* tidy up loose ends and fill things in */
  305. categorize(p, g);
  306. stripsnug(p, g);
  307. findmust(p, g);
  308. g->nplus = pluscount(p, g);
  309. g->magic = MAGIC2;
  310. preg->re_nsub = g->nsub;
  311. preg->re_g = g;
  312. preg->re_magic = MAGIC1;
  313. #ifndef REDEBUG
  314. /* not debugging, so can't rely on the assert() in regexec() */
  315. if (g->iflags & BAD)
  316. SETERROR(REG_ASSERT);
  317. #endif
  319. /* win or lose, we're done */
  320. if (p->error != 0) /* lose */
  321. pg95_regfree(preg);
  322. return p->error;
  323. }
  325. /*
  326.  - p_ere - ERE parser top level, concatenation and alternation
  327.  == static void p_ere(struct parse *p, int stop);
  328.  */
  329. static void
  330. p_ere(p, stop)
  331. struct parse *p;
  332. int stop; /* character this ERE should end at */
  333. {
  334. char c;
  335. sopno prevback = 0;
  336. sopno prevfwd = 0;
  337. sopno conc;
  338. int first = 1; /* is this the first alternative? */
  340. for (;;)
  341. {
  342. /* do a bunch of concatenated expressions */
  343. conc = HERE();
  344. while (MORE() && (c = PEEK()) != '|' && c != stop)
  345. p_ere_exp(p);
  346. REQUIRE(HERE() != conc, REG_EMPTY); /* require nonempty */
  348. if (!EAT('|'))
  349. break; /* NOTE BREAK OUT */
  351. if (first)
  352. {
  353. INSERT(OCH_, conc); /* offset is wrong */
  354. prevfwd = conc;
  355. prevback = conc;
  356. first = 0;
  357. }
  358. ASTERN(OOR1, prevback);
  359. prevback = THERE();
  360. AHEAD(prevfwd); /* fix previous offset */
  361. prevfwd = HERE();
  362. EMIT(OOR2, 0); /* offset is very wrong */
  363. }
  365. if (!first)
  366. { /* tail-end fixups */
  367. AHEAD(prevfwd);
  368. ASTERN(O_CH, prevback);
  369. }
  371. assert(!MORE() || SEE(stop));
  372. }
  374. /*
  375.  - p_ere_exp - parse one subERE, an atom possibly followed by a repetition op
  376.  == static void p_ere_exp(struct parse *p);
  377.  */
  378. static void
  379. p_ere_exp(p)
  380. struct parse *p;
  381. {
  382. pg_wchar c;
  383. sopno pos;
  384. int count;
  385. int count2;
  386. sopno subno;
  387. int wascaret = 0;
  389. assert(MORE()); /* caller should have ensured this */
  390. c = GETNEXT();
  392. pos = HERE();
  393. switch (c)
  394. {
  395. case '(':
  396. REQUIRE(MORE(), REG_EPAREN);
  397. p->g->nsub++;
  398. subno = p->g->nsub;
  399. if (subno < NPAREN)
  400. p->pbegin[subno] = HERE();
  401. EMIT(OLPAREN, subno);
  402. if (!SEE(')'))
  403. p_ere(p, ')');
  404. if (subno < NPAREN)
  405. {
  406. p->pend[subno] = HERE();
  407. assert(p->pend[subno] != 0);
  408. }
  409. EMIT(ORPAREN, subno);
  410. MUSTEAT(')', REG_EPAREN);
  411. break;
  412. #ifndef POSIX_MISTAKE
  413. case ')': /* happens only if no current unmatched ( */
  415. /*
  416.  * You may ask, why the ifndef?  Because I didn't notice this
  417.  * until slightly too late for 1003.2, and none of the other
  418.  * 1003.2 regular-expression reviewers noticed it at all.  So
  419.  * an unmatched ) is legal POSIX, at least until we can get it
  420.  * fixed.
  421.  */
  422. SETERROR(REG_EPAREN);
  423. break;
  424. #endif
  425. case '^':
  426. EMIT(OBOL, 0);
  427. p->g->iflags |= USEBOL;
  428. p->g->nbol++;
  429. wascaret = 1;
  430. break;
  431. case '$':
  432. EMIT(OEOL, 0);
  433. p->g->iflags |= USEEOL;
  434. p->g->neol++;
  435. break;
  436. case '|':
  437. SETERROR(REG_EMPTY);
  438. break;
  439. case '*':
  440. case '+':
  441. case '?':
  442. SETERROR(REG_BADRPT);
  443. break;
  444. case '.':
  445. if (p->g->cflags & REG_NEWLINE)
  446. nonnewline(p);
  447. else
  448. EMIT(OANY, 0);
  449. break;
  450. case '[':
  451. p_bracket(p);
  452. break;
  453. case '\':
  454. REQUIRE(MORE(), REG_EESCAPE);
  455. c = GETNEXT();
  456. ordinary(p, c);
  457. break;
  458. case '{': /* okay as ordinary except if digit
  459.  * follows */
  460. REQUIRE(!MORE() || !pg_isdigit(PEEK()), REG_BADRPT);
  461. /* FALLTHROUGH */
  462. default:
  463. ordinary(p, c);
  464. break;
  465. }
  467. if (!MORE())
  468. return;
  469. c = PEEK();
  470. /* we call { a repetition if followed by a digit */
  471. if (!(c == '*' || c == '+' || c == '?' ||
  472.   (c == '{' && MORE2() && pg_isdigit(PEEK2()))))
  473. return; /* no repetition, we're done */
  474. NEXT();
  476. REQUIRE(!wascaret, REG_BADRPT);
  477. switch (c)
  478. {
  479. case '*': /* implemented as +? */
  480. /* this case does not require the (y|) trick, noKLUDGE */
  481. INSERT(OPLUS_, pos);
  482. ASTERN(O_PLUS, pos);
  483. INSERT(OQUEST_, pos);
  484. ASTERN(O_QUEST, pos);
  485. break;
  486. case '+':
  487. INSERT(OPLUS_, pos);
  488. ASTERN(O_PLUS, pos);
  489. break;
  490. case '?':
  491. /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
  492. INSERT(OCH_, pos); /* offset slightly wrong */
  493. ASTERN(OOR1, pos); /* this one's right */
  494. AHEAD(pos); /* fix the OCH_ */
  495. EMIT(OOR2, 0); /* offset very wrong... */
  496. AHEAD(THERE()); /* ...so fix it */
  497. ASTERN(O_CH, THERETHERE());
  498. break;
  499. case '{':
  500. count = p_count(p);
  501. if (EAT(','))
  502. {
  503. if (pg_isdigit(PEEK()))
  504. {
  505. count2 = p_count(p);
  506. REQUIRE(count <= count2, REG_BADBR);
  507. }
  508. else
  509. /* single number with comma */
  510. count2 = INFINITY;
  511. }
  512. else
  513. /* just a single number */
  514. count2 = count;
  515. repeat(p, pos, count, count2);
  516. if (!EAT('}'))
  517. { /* error heuristics */
  518. while (MORE() && PEEK() != '}')
  519. NEXT();
  520. REQUIRE(MORE(), REG_EBRACE);
  521. SETERROR(REG_BADBR);
  522. }
  523. break;
  524. }
  526. if (!MORE())
  527. return;
  528. c = PEEK();
  529. if (!(c == '*' || c == '+' || c == '?' ||
  530.   (c == '{' && MORE2() && pg_isdigit(PEEK2()))))
  531. return;
  532. SETERROR(REG_BADRPT);
  533. }
  535. /*
  536.  - p_str - string (no metacharacters) "parser"
  537.  == static void p_str(struct parse *p);
  538.  */
  539. static void
  540. p_str(p)
  541. struct parse *p;
  542. {
  543. REQUIRE(MORE(), REG_EMPTY);
  544. while (MORE())
  545. ordinary(p, GETNEXT());
  546. }
  548. /*
  549.  - p_bre - BRE parser top level, anchoring and concatenation
  550.  == static void p_bre(struct parse *p, int end1, 
  551.  == int end2);
  552.  * Giving end1 as OUT essentially eliminates the end1/end2 check.
  553.  *
  554.  * This implementation is a bit of a kludge, in that a trailing $ is first
  555.  * taken as an ordinary character and then revised to be an anchor.  The
  556.  * only undesirable side effect is that '$' gets included as a character
  557.  * category in such cases. This is fairly harmless; not worth fixing.
  558.  * The amount of lookahead needed to avoid this kludge is excessive.
  559.  */
  560. static void
  561. p_bre(p, end1, end2)
  562. struct parse *p;
  563. int end1; /* first terminating character */
  564. int end2; /* second terminating character */
  565. {
  566. sopno start = HERE();
  567. int first = 1; /* first subexpression? */
  568. int wasdollar = 0;
  570. if (EAT('^'))
  571. {
  572. EMIT(OBOL, 0);
  573. p->g->iflags |= USEBOL;
  574. p->g->nbol++;
  575. }
  576. while (MORE() && !SEETWO(end1, end2))
  577. {
  578. wasdollar = p_simp_re(p, first);
  579. first = 0;
  580. }
  581. if (wasdollar)
  582. { /* oops, that was a trailing anchor */
  583. DROP(1);
  584. EMIT(OEOL, 0);
  585. p->g->iflags |= USEEOL;
  586. p->g->neol++;
  587. }
  589. REQUIRE(HERE() != start, REG_EMPTY); /* require nonempty */
  590. }
  592. /*
  593.  - p_simp_re - parse a simple RE, an atom possibly followed by a repetition
  594.  == static int p_simp_re(struct parse *p, int starordinary);
  595.  */
  596. static int /* was the simple RE an unbackslashed $? */
  597. p_simp_re(p, starordinary)
  598. struct parse *p;
  599. int starordinary; /* is a leading * an ordinary character? */
  600. {
  601. int c;
  602. int count;
  603. int count2;
  604. sopno pos;
  605. int i;
  606. sopno subno;
  608. #define  BACKSL  (1<<24)
  610. pos = HERE(); /* repetion op, if any, covers from here */
  612. assert(MORE()); /* caller should have ensured this */
  613. c = GETNEXT();
  614. if (c == '\')
  615. {
  616. REQUIRE(MORE(), REG_EESCAPE);
  617. #ifdef MULTIBYTE
  618. c = BACKSL | (pg_wchar) GETNEXT();
  619. #else
  620. c = BACKSL | (unsigned char) GETNEXT();
  621. #endif
  622. }
  623. switch (c)
  624. {
  625. case '.':
  626. if (p->g->cflags & REG_NEWLINE)
  627. nonnewline(p);
  628. else
  629. EMIT(OANY, 0);
  630. break;
  631. case '[':
  632. p_bracket(p);
  633. break;
  634. case BACKSL | '{':
  635. SETERROR(REG_BADRPT);
  636. break;
  637. case BACKSL | '(':
  638. p->g->nsub++;
  639. subno = p->g->nsub;
  640. if (subno < NPAREN)
  641. p->pbegin[subno] = HERE();
  642. EMIT(OLPAREN, subno);
  643. /* the MORE here is an error heuristic */
  644. if (MORE() && !SEETWO('\', ')'))
  645. p_bre(p, '\', ')');
  646. if (subno < NPAREN)
  647. {
  648. p->pend[subno] = HERE();
  649. assert(p->pend[subno] != 0);
  650. }
  651. EMIT(ORPAREN, subno);
  652. REQUIRE(EATTWO('\', ')'), REG_EPAREN);
  653. break;
  654. case BACKSL | ')': /* should not get here -- must be user */
  655. case BACKSL | '}':
  656. SETERROR(REG_EPAREN);
  657. break;
  658. case BACKSL | '1':
  659. case BACKSL | '2':
  660. case BACKSL | '3':
  661. case BACKSL | '4':
  662. case BACKSL | '5':
  663. case BACKSL | '6':
  664. case BACKSL | '7':
  665. case BACKSL | '8':
  666. case BACKSL | '9':
  667. i = (c & ~BACKSL) - '0';
  668. assert(i < NPAREN);
  669. if (p->pend[i] != 0)
  670. {
  671. assert(i <= p->g->nsub);
  672. EMIT(OBACK_, i);
  673. assert(p->pbegin[i] != 0);
  674. assert(OP(p->strip[p->pbegin[i]]) == OLPAREN);
  675. assert(OP(p->strip[p->pend[i]]) == ORPAREN);
  676. dupl(p, p->pbegin[i] + 1, p->pend[i]);
  677. EMIT(O_BACK, i);
  678. }
  679. else
  680. SETERROR(REG_ESUBREG);
  681. p->g->backrefs = 1;
  682. break;
  683. case '*':
  684. REQUIRE(starordinary, REG_BADRPT);
  685. /* FALLTHROUGH */
  686. default:
  687. ordinary(p, c & ~BACKSL);
  688. break;
  689. }
  691. if (EAT('*'))
  692. { /* implemented as +? */
  693. /* this case does not require the (y|) trick, noKLUDGE */
  694. INSERT(OPLUS_, pos);
  695. ASTERN(O_PLUS, pos);
  696. INSERT(OQUEST_, pos);
  697. ASTERN(O_QUEST, pos);
  698. }
  699. else if (EATTWO('\', '{'))
  700. {
  701. count = p_count(p);
  702. if (EAT(','))
  703. {
  704. if (MORE() && pg_isdigit(PEEK()))
  705. {
  706. count2 = p_count(p);
  707. REQUIRE(count <= count2, REG_BADBR);
  708. }
  709. else
  710. /* single number with comma */
  711. count2 = INFINITY;
  712. }
  713. else
  714. /* just a single number */
  715. count2 = count;
  716. repeat(p, pos, count, count2);
  717. if (!EATTWO('\', '}'))
  718. { /* error heuristics */
  719. while (MORE() && !SEETWO('\', '}'))
  720. NEXT();
  721. REQUIRE(MORE(), REG_EBRACE);
  722. SETERROR(REG_BADBR);
  723. }
  724. }
  725. else if (c == (unsigned char) '$') /* $ (but not $) ends it */
  726. return 1;
  728. return 0;
  729. }
  731. /*
  732.  - p_count - parse a repetition count
  733.  == static int p_count(struct parse *p);
  734.  */
  735. static int /* the value */
  736. p_count(p)
  737. struct parse *p;
  738. {
  739. int count = 0;
  740. int ndigits = 0;
  742. while (MORE() && pg_isdigit(PEEK()) && count <= DUPMAX)
  743. {
  744. count = count * 10 + (GETNEXT() - '0');
  745. ndigits++;
  746. }
  748. REQUIRE(ndigits > 0 && count <= DUPMAX, REG_BADBR);
  749. return count;
  750. }
  752. /*
  753.  - p_bracket - parse a bracketed character list
  754.  == static void p_bracket(struct parse *p);
  755.  *
  756.  * Note a significant property of this code:  if the allocset() did SETERROR,
  757.  * no set operations are done.
  758.  */
  759. static void
  760. p_bracket(p)
  761. struct parse *p;
  762. {
  763. cset    *cs = allocset(p);
  764. int invert = 0;
  766. #ifdef MULTIBYTE
  767. pg_wchar sp1[] = {'[', ':', '<', ':', ']', ']'};
  768. pg_wchar sp2[] = {'[', ':', '>', ':', ']', ']'};
  770. #endif
  772. /* Dept of Truly Sickening Special-Case Kludges */
  773. #ifdef MULTIBYTE
  774. if (p->next + 5 < p->end && pg_wchar_strncmp(p->next, sp1, 6) == 0)
  775. #else
  776. if (p->next + 5 < p->end && strncmp(p->next, "[:<:]]", 6) == 0)
  777. #endif
  778. {
  779. EMIT(OBOW, 0);
  780. NEXTn(6);
  781. return;
  782. }
  783. #ifdef MULTIBYTE
  784. if (p->next + 5 < p->end && pg_wchar_strncmp(p->next, sp2, 6) == 0)
  785. #else
  786. if (p->next + 5 < p->end && strncmp(p->next, "[:>:]]", 6) == 0)
  787. #endif
  788. {
  789. EMIT(OEOW, 0);
  790. NEXTn(6);
  791. return;
  792. }
  794. if (EAT('^'))
  795. invert++; /* make note to invert set at end */
  796. if (EAT(']'))
  797. CHadd(cs, ']');
  798. else if (EAT('-'))
  799. CHadd(cs, '-');
  800. while (MORE() && PEEK() != ']' && !SEETWO('-', ']'))
  801. p_b_term(p, cs);
  802. if (EAT('-'))
  803. CHadd(cs, '-');
  804. MUSTEAT(']', REG_EBRACK);
  806. if (p->error != 0) /* don't mess things up further */
  807. return;
  809. if (p->g->cflags & REG_ICASE)
  810. {
  811. int i;
  812. int ci;
  814. for (i = p->g->csetsize - 1; i >= 0; i--)
  815. if (CHIN(cs, i) && pg_isalpha(i))
  816. {
  817. ci = othercase(i);
  818. if (ci != i)
  819. CHadd(cs, ci);
  820. }
  821. if (cs->multis != NULL)
  822. mccase(p, cs);
  823. }
  824. if (invert)
  825. {
  826. int i;
  828. for (i = p->g->csetsize - 1; i >= 0; i--)
  829. if (CHIN(cs, i))
  830. CHsub(cs, i);
  831. else
  832. CHadd(cs, i);
  833. if (p->g->cflags & REG_NEWLINE)
  834. CHsub(cs, 'n');
  835. if (cs->multis != NULL)
  836. mcinvert(p, cs);
  837. }
  839. assert(cs->multis == NULL); /* xxx */
  841. if (nch(p, cs) == 1)
  842. { /* optimize singleton sets */
  843. ordinary(p, firstch(p, cs));
  844. freeset(p, cs);
  845. }
  846. else
  847. EMIT(OANYOF, freezeset(p, cs));
  848. }
  850. /*
  851.  - p_b_term - parse one term of a bracketed character list
  852.  == static void p_b_term(struct parse *p, cset *cs);
  853.  */
  854. static void
  855. p_b_term(p, cs)
  856. struct parse *p;
  857. cset    *cs;
  858. {
  859. pg_wchar c;
  860. pg_wchar start,
  861. finish;
  862. int i;
  864. /* classify what we've got */
  865. switch ((MORE()) ? PEEK() : '')
  866. {
  867. case '[':
  868. c = (MORE2()) ? PEEK2() : '';
  869. break;
  870. case '-':
  871. SETERROR(REG_ERANGE);
  872. return; /* NOTE RETURN */
  873. break;
  874. default:
  875. c = '';
  876. break;
  877. }
  879. switch (c)
  880. {
  881. case ':': /* character class */
  882. NEXT2();
  883. REQUIRE(MORE(), REG_EBRACK);
  884. c = PEEK();
  885. REQUIRE(c != '-' && c != ']', REG_ECTYPE);
  886. p_b_cclass(p, cs);
  887. REQUIRE(MORE(), REG_EBRACK);
  888. REQUIRE(EATTWO(':', ']'), REG_ECTYPE);
  889. break;
  890. case '=': /* equivalence class */
  891. NEXT2();
  892. REQUIRE(MORE(), REG_EBRACK);
  893. c = PEEK();
  894. REQUIRE(c != '-' && c != ']', REG_ECOLLATE);
  895. p_b_eclass(p, cs);
  896. REQUIRE(MORE(), REG_EBRACK);
  897. REQUIRE(EATTWO('=', ']'), REG_ECOLLATE);
  898. break;
  899. default: /* symbol, ordinary character, or range */
  900. /* xxx revision needed for multichar stuff */
  901. start = p_b_symbol(p);
  902. if (SEE('-') && MORE2() && PEEK2() != ']')
  903. {
  904. /* range */
  905. NEXT();
  906. if (EAT('-'))
  907. finish = '-';
  908. else
  909. finish = p_b_symbol(p);
  910. }
  911. else
  912. finish = start;
  913. /* xxx what about signed chars here... */
  914. REQUIRE(start <= finish, REG_ERANGE);
  915. #ifdef MULTIBYTE
  916. if (CHlc(start) != CHlc(finish))
  917. SETERROR(REG_ERANGE);
  918. #endif
  919. for (i = start; i <= finish; i++)
  920. CHadd(cs, i);
  921. break;
  922. }
  923. }
  925. /*
  926.  - p_b_cclass - parse a character-class name and deal with it
  927.  == static void p_b_cclass(struct parse *p, cset *cs);
  928.  */
  929. static void
  930. p_b_cclass(p, cs)
  931. struct parse *p;
  932. cset    *cs;
  933. {
  934. pg_wchar   *sp = p->next;
  935. struct cclass *cp;
  936. size_t len;
  937. char    *u;
  938. char c;
  940. while (MORE() && pg_isalpha(PEEK()))
  941. NEXT();
  942. len = p->next - sp;
  943. for (cp = cclasses; cp->name != NULL; cp++)
  944. #ifdef MULTIBYTE
  945. if (pg_char_and_wchar_strncmp(cp->name, sp, len) == 0 && cp->name[len] == '')
  946. #else
  947. if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '')
  948. #endif
  949. break;
  950. if (cp->name == NULL)
  951. {
  952. /* oops, didn't find it */
  953. SETERROR(REG_ECTYPE);
  954. return;
  955. }
  957. u = cp->chars;
  958. while ((c = *u++) != '')
  959. CHadd(cs, c);
  960. for (u = cp->multis; *u != ''; u += strlen(u) + 1)
  961. MCadd(p, cs, u);
  962. }
  964. /*
  965.  - p_b_eclass - parse an equivalence-class name and deal with it
  966.  == static void p_b_eclass(struct parse *p, cset *cs);
  967.  *
  968.  * This implementation is incomplete. xxx
  969.  */
  970. static void
  971. p_b_eclass(p, cs)
  972. struct parse *p;
  973. cset    *cs;
  974. {
  975. char c;
  977. c = p_b_coll_elem(p, '=');
  978. CHadd(cs, c);
  979. }
  981. /*
  982.  - p_b_symbol - parse a character or [..]ed multicharacter collating symbol
  983.  == static char p_b_symbol(struct parse *p);
  984.  */
  985. static pg_wchar /* value of symbol */
  986. p_b_symbol(p)
  987. struct parse *p;
  988. {
  989. pg_wchar value;
  991. REQUIRE(MORE(), REG_EBRACK);
  992. if (!EATTWO('[', '.'))
  993. return GETNEXT();
  995. /* collating symbol */
  996. value = p_b_coll_elem(p, '.');
  997. REQUIRE(EATTWO('.', ']'), REG_ECOLLATE);
  998. return value;
  999. }
  1001. /*
  1002.  - p_b_coll_elem - parse a collating-element name and look it up
  1003.  == static char p_b_coll_elem(struct parse *p, int endc);
  1004.  */
  1005. static char /* value of collating element */
  1006. p_b_coll_elem(p, endc)
  1007. struct parse *p;
  1008. int endc; /* name ended by endc,']' */
  1009. {
  1010. pg_wchar   *sp = p->next;
  1011. struct cname *cp;
  1012. int len;
  1014. while (MORE() && !SEETWO(endc, ']'))
  1015. NEXT();
  1016. if (!MORE())
  1017. {
  1018. SETERROR(REG_EBRACK);
  1019. return 0;
  1020. }
  1021. len = p->next - sp;
  1022. for (cp = cnames; cp->name != NULL; cp++)
  1023. #ifdef MULTIBYTE
  1024. if (pg_char_and_wchar_strncmp(cp->name, sp, len) == 0 && cp->name[len] == '')
  1025. #else
  1026. if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '')
  1027. #endif
  1028. return cp->code; /* known name */
  1029. if (len == 1)
  1030. return *sp; /* single character */
  1031. SETERROR(REG_ECOLLATE); /* neither */
  1032. return 0;
  1033. }
  1035. /*
  1036.  - othercase - return the case counterpart of an alphabetic
  1037.  == static char othercase(int ch);
  1038.  */
  1039. #ifdef MULTIBYTE
  1040. static unsigned char /* if no counterpart, return ch */
  1041. #else
  1042. static char /* if no counterpart, return ch */
  1043. #endif
  1044. othercase(ch)
  1045. int ch;
  1046. {
  1047. assert(pg_isalpha(ch));
  1048. if (pg_isupper(ch))
  1049. #ifdef MULTIBYTE
  1050. return (unsigned char) tolower(ch);
  1051. #else
  1052. return tolower(ch);
  1053. #endif
  1054. else if (pg_islower(ch))
  1055. #ifdef MULTIBYTE
  1056. return (unsigned char) toupper(ch);
  1057. #else
  1058. return toupper(ch);
  1059. #endif
  1060. else
  1061. /* peculiar, but could happen */
  1062. #ifdef MULTIBYTE
  1063. return (unsigned char) ch;
  1064. #else
  1065. return ch;
  1066. #endif
  1067. }
  1069. /*
  1070.  - bothcases - emit a dualcase version of a two-case character
  1071.  == static void bothcases(struct parse *p, int ch);
  1072.  *
  1073.  * Boy, is this implementation ever a kludge...
  1074.  */
  1075. static void
  1076. bothcases(p, ch)
  1077. struct parse *p;
  1078. int ch;
  1079. {
  1080. pg_wchar   *oldnext = p->next;
  1081. pg_wchar   *oldend = p->end;
  1082. pg_wchar bracket[3];
  1084. assert(othercase(ch) != ch);/* p_bracket() would recurse */
  1085. p->next = bracket;
  1086. p->end = bracket + 2;
  1087. bracket[0] = ch;
  1088. bracket[1] = ']';
  1089. bracket[2] = '';
  1090. p_bracket(p);
  1091. assert(p->next == bracket + 2);
  1092. p->next = oldnext;
  1093. p->end = oldend;
  1094. }
  1096. /*
  1097.  - ordinary - emit an ordinary character
  1098.  == static void ordinary(struct parse *p, int ch);
  1099.  */
  1100. static void
  1101. ordinary(p, ch)
  1102. struct parse *p;
  1103. int ch;
  1104. {
  1105. cat_t    *cap = p->g->categories;
  1107. if ((p->g->cflags & REG_ICASE) && pg_isalpha(ch) && othercase(ch) != ch)
  1108. bothcases(p, ch);
  1109. else
  1110. {
  1111. #ifdef MULTIBYTE
  1112. EMIT(OCHAR, (pg_wchar) ch);
  1113. #else
  1114. EMIT(OCHAR, (unsigned char) ch);
  1115. #endif
  1116. if (ch >= CHAR_MIN && ch <= CHAR_MAX && cap[ch] == 0)
  1117. cap[ch] = p->g->ncategories++;
  1118. }
  1119. }
  1121. /*
  1122.  - nonnewline - emit REG_NEWLINE version of OANY
  1123.  == static void nonnewline(struct parse *p);
  1124.  *
  1125.  * Boy, is this implementation ever a kludge...
  1126.  */
  1127. static void
  1128. nonnewline(p)
  1129. struct parse *p;
  1130. {
  1131. pg_wchar   *oldnext = p->next;
  1132. pg_wchar   *oldend = p->end;
  1133. pg_wchar bracket[4];
  1135. p->next = bracket;
  1136. p->end = bracket + 3;
  1137. bracket[0] = '^';
  1138. bracket[1] = 'n';
  1139. bracket[2] = ']';
  1140. bracket[3] = '';
  1141. p_bracket(p);
  1142. assert(p->next == bracket + 3);
  1143. p->next = oldnext;
  1144. p->end = oldend;
  1145. }
  1147. /*
  1148.  - repeat - generate code for a bounded repetition, recursively if needed
  1149.  == static void repeat(struct parse *p, sopno start, int from, int to);
  1150.  */
  1151. static void
  1152. repeat(p, start, from, to)
  1153. struct parse *p;
  1154. sopno start; /* operand from here to end of strip */
  1155. int from; /* repeated from this number */
  1156. int to; /* to this number of times (maybe
  1157.  * INFINITY) */
  1158. {
  1159. sopno finish = HERE();
  1161. #define  N  2
  1162. #define  INF  3
  1163. #define  REP(f, t)  ((f)*8 + (t))
  1164. #define  MAP(n)  (((n) <= 1) ? (n) : ((n) == INFINITY) ? INF : N)
  1165. sopno copy;
  1167. if (p->error != 0) /* head off possible runaway recursion */
  1168. return;
  1170. assert(from <= to);
  1172. switch (REP(MAP(from), MAP(to)))
  1173. {
  1174. case REP(0, 0): /* must be user doing this */
  1175. DROP(finish - start); /* drop the operand */
  1176. break;
  1177. case REP(0, 1): /* as x{1,1}? */
  1178. case REP(0, N): /* as x{1,n}? */
  1179. case REP(0, INF): /* as x{1,}? */
  1180. /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
  1181. INSERT(OCH_, start);/* offset is wrong... */
  1182. repeat(p, start + 1, 1, to);
  1183. ASTERN(OOR1, start);
  1184. AHEAD(start); /* ... fix it */
  1185. EMIT(OOR2, 0);
  1186. AHEAD(THERE());
  1187. ASTERN(O_CH, THERETHERE());
  1188. break;
  1189. case REP(1, 1): /* trivial case */
  1190. /* done */
  1191. break;
  1192. case REP(1, N): /* as x?x{1,n-1} */
  1193. /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
  1194. INSERT(OCH_, start);
  1195. ASTERN(OOR1, start);
  1196. AHEAD(start);
  1197. EMIT(OOR2, 0); /* offset very wrong... */
  1198. AHEAD(THERE()); /* ...so fix it */
  1199. ASTERN(O_CH, THERETHERE());
  1200. copy = dupl(p, start + 1, finish + 1);
  1201. assert(copy == finish + 4);
  1202. repeat(p, copy, 1, to - 1);
  1203. break;
  1204. case REP(1, INF): /* as x+ */
  1205. INSERT(OPLUS_, start);
  1206. ASTERN(O_PLUS, start);
  1207. break;
  1208. case REP(N, N): /* as xx{m-1,n-1} */
  1209. copy = dupl(p, start, finish);
  1210. repeat(p, copy, from - 1, to - 1);
  1211. break;
  1212. case REP(N, INF): /* as xx{n-1,INF} */
  1213. copy = dupl(p, start, finish);
  1214. repeat(p, copy, from - 1, to);
  1215. break;
  1216. default: /* "can't happen" */
  1217. SETERROR(REG_ASSERT); /* just in case */
  1218. break;
  1219. }
  1220. }
  1222. /*
  1223.  - seterr - set an error condition
  1224.  == static int seterr(struct parse *p, int e);
  1225.  */
  1226. static int /* useless but makes type checking happy */
  1227. seterr(p, e)
  1228. struct parse *p;
  1229. int e;
  1230. {
  1231. if (p->error == 0) /* keep earliest error condition */
  1232. p->error = e;
  1233. p->next = nuls; /* try to bring things to a halt */
  1234. p->end = nuls;
  1235. return 0; /* make the return value well-defined */
  1236. }
  1238. /*
  1239.  - allocset - allocate a set of characters for []
  1240.  == static cset *allocset(struct parse *p);
  1241.  */
  1242. static cset *
  1243. allocset(p)
  1244. struct parse *p;
  1245. {
  1246. int no = p->g->ncsets++;
  1247. size_t nc;
  1248. size_t nbytes;
  1249. cset    *cs;
  1250. size_t css = (size_t) p->g->csetsize;
  1251. int i;
  1253. if (no >= p->ncsalloc)
  1254. { /* need another column of space */
  1255. p->ncsalloc += CHAR_BIT;
  1256. nc = p->ncsalloc;
  1257. assert(nc % CHAR_BIT == 0);
  1258. nbytes = nc / CHAR_BIT * css;
  1259. if (p->g->sets == NULL)
  1260. p->g->sets = (cset *) malloc(nc * sizeof(cset));
  1261. else
  1262. p->g->sets = (cset *) realloc((char *) p->g->sets,
  1263.   nc * sizeof(cset));
  1264. if (p->g->setbits == NULL)
  1265. p->g->setbits = (uch *) malloc(nbytes);
  1266. else
  1267. {
  1268. p->g->setbits = (uch *) realloc((char *) p->g->setbits,
  1269. nbytes);
  1270. /* xxx this isn't right if setbits is now NULL */
  1271. for (i = 0; i < no; i++)
  1272. p->g->sets[i].ptr = p->g->setbits + css * (i / CHAR_BIT);
  1273. }
  1274. if (p->g->sets != NULL && p->g->setbits != NULL)
  1275. memset((char *) p->g->setbits + (nbytes - css),
  1276.    0, css);
  1277. else
  1278. {
  1279. no = 0;
  1280. SETERROR(REG_ESPACE);
  1281. /* caller's responsibility not to do set ops */
  1282. }
  1283. }
  1285. assert(p->g->sets != NULL); /* xxx */
  1286. cs = &p->g->sets[no];
  1287. cs->ptr = p->g->setbits + css * ((no) / CHAR_BIT);
  1288. cs->mask = 1 << ((no) % CHAR_BIT);
  1289. cs->hash = 0;
  1290. cs->smultis = 0;
  1291. cs->multis = NULL;
  1293. return cs;
  1294. }
  1296. /*
  1297.  - freeset - free a now-unused set
  1298.  == static void freeset(struct parse *p, cset *cs);
  1299.  */
  1300. static void
  1301. freeset(p, cs)
  1302. struct parse *p;
  1303. cset    *cs;
  1304. {
  1305. int i;
  1306. cset    *top = &p->g->sets[p->g->ncsets];
  1307. size_t css = (size_t) p->g->csetsize;
  1309. for (i = 0; i < css; i++)
  1310. CHsub(cs, i);
  1311. if (cs == top - 1) /* recover only the easy case */
  1312. p->g->ncsets--;
  1313. }
  1315. /*
  1316.  - freezeset - final processing on a set of characters
  1317.  == static int freezeset(struct parse *p, cset *cs);
  1318.  *
  1319.  * The main task here is merging identical sets.  This is usually a waste
  1320.  * of time (although the hash code minimizes the overhead), but can win
  1321.  * big if REG_ICASE is being used. REG_ICASE, by the way, is why the hash
  1322.  * is done using addition rather than xor -- all ASCII [aA] sets xor to
  1323.  * the same value!
  1324.  */
  1325. static int /* set number */
  1326. freezeset(p, cs)
  1327. struct parse *p;
  1328. cset    *cs;
  1329. {
  1330. uch h = cs->hash;
  1331. int i;
  1332. cset    *top = &p->g->sets[p->g->ncsets];
  1333. cset    *cs2;
  1334. size_t css = (size_t) p->g->csetsize;
  1336. /* look for an earlier one which is the same */
  1337. for (cs2 = &p->g->sets[0]; cs2 < top; cs2++)
  1338. if (cs2->hash == h && cs2 != cs)
  1339. {
  1340. /* maybe */
  1341. for (i = 0; i < css; i++)
  1342. if (!!CHIN(cs2, i) != !!CHIN(cs, i))
  1343. break; /* no */
  1344. if (i == css)
  1345. break; /* yes */
  1346. }
  1348. if (cs2 < top)
  1349. { /* found one */
  1350. freeset(p, cs);
  1351. cs = cs2;
  1352. }
  1354. return (int) (cs - p->g->sets);
  1355. }
  1357. /*
  1358.  - firstch - return first character in a set (which must have at least one)
  1359.  == static int firstch(struct parse *p, cset *cs);
  1360.  */
  1361. static int /* character; there is no "none" value */
  1362. firstch(p, cs)
  1363. struct parse *p;
  1364. cset    *cs;
  1365. {
  1366. int i;
  1367. size_t css = (size_t) p->g->csetsize;
  1369. for (i = 0; i < css; i++)
  1370. if (CHIN(cs, i))
  1371. return i;
  1372. assert(never);
  1373. return 0; /* arbitrary */
  1374. }
  1376. /*
  1377.  - nch - number of characters in a set
  1378.  == static int nch(struct parse *p, cset *cs);
  1379.  */
  1380. static int
  1381. nch(p, cs)
  1382. struct parse *p;
  1383. cset    *cs;
  1384. {
  1385. int i;
  1386. size_t css = (size_t) p->g->csetsize;
  1387. int n = 0;
  1389. for (i = 0; i < css; i++)
  1390. if (CHIN(cs, i))
  1391. n++;
  1392. return n;
  1393. }
  1395. /*
  1396.  - mcadd - add a collating element to a cset
  1397.  == static void mcadd(struct parse *p, cset *cs, 
  1398.  == char *cp);
  1399.  */
  1400. static void
  1401. mcadd(p, cs, cp)
  1402. struct parse *p;
  1403. cset    *cs;
  1404. char    *cp;
  1405. {
  1406. size_t oldend = cs->smultis;
  1408. cs->smultis += strlen(cp) + 1;
  1409. if (cs->multis == NULL)
  1410. cs->multis = malloc(cs->smultis);
  1411. else
  1412. cs->multis = realloc(cs->multis, cs->smultis);
  1413. if (cs->multis == NULL)
  1414. {
  1415. SETERROR(REG_ESPACE);
  1416. return;
  1417. }
  1419. strcpy(cs->multis + oldend - 1, cp);
  1420. cs->multis[cs->smultis - 1] = '';
  1421. }
  1423. /*
  1424.  - mcsub - subtract a collating element from a cset
  1425.  == static void mcsub(cset *cs, char *cp);
  1426.  */
  1427. /*
  1428. static void
  1429. mcsub(cs, cp)
  1430. cset *cs;
  1431. char *cp;
  1432. {
  1433. char *fp = mcfind(cs, cp);
  1434. size_t len = strlen(fp);
  1436. assert(fp != NULL);
  1437. memmove(fp, fp + len + 1,
  1438. cs->smultis - (fp + len + 1 - cs->multis));
  1439. cs->smultis -= len;
  1441. if (cs->smultis == 0) {
  1442. free(cs->multis);
  1443. cs->multis = NULL;
  1444. return;
  1445. }
  1447. cs->multis = realloc(cs->multis, cs->smultis);
  1448. assert(cs->multis != NULL);
  1449. }
  1450. */
  1452. /*
  1453.  - mcin - is a collating element in a cset?
  1454.  == static int mcin(cset *cs, char *cp);
  1455.  */
  1456. /*
  1457. static int
  1458. mcin(cs, cp)
  1459. cset *cs;
  1460. char *cp;
  1461. {
  1462. return(mcfind(cs, cp) != NULL);
  1463. }
  1464. */
  1466. /*
  1467.  - mcfind - find a collating element in a cset
  1468.  == static char *mcfind(cset *cs, char *cp);
  1469.  */
  1470. /*
  1471. static char *
  1472. mcfind(cs, cp)
  1473. cset *cs;
  1474. char *cp;
  1475. {
  1476. char *p;
  1478. if (cs->multis == NULL)
  1479. return(NULL);
  1480. for (p = cs->multis; *p != ''; p += strlen(p) + 1)
  1481. if (strcmp(cp, p) == 0)
  1482. return(p);
  1483. return(NULL);
  1484. }
  1485. */
  1486. /*
  1487.  - mcinvert - invert the list of collating elements in a cset
  1488.  == static void mcinvert(struct parse *p, cset *cs);
  1489.  *
  1490.  * This would have to know the set of possibilities.  Implementation
  1491.  * is deferred.
  1492.  */
  1493. static void
  1494. mcinvert(p, cs)
  1495. struct parse *p;
  1496. cset    *cs;
  1497. {
  1498. assert(cs->multis == NULL); /* xxx */
  1499. }
  1501. /*
  1502.  - mccase - add case counterparts of the list of collating elements in a cset
  1503.  == static void mccase(struct parse *p, cset *cs);
  1504.  *
  1505.  * This would have to know the set of possibilities.  Implementation
  1506.  * is deferred.
  1507.  */
  1508. static void
  1509. mccase(p, cs)
  1510. struct parse *p;
  1511. cset    *cs;
  1512. {
  1513. assert(cs->multis == NULL); /* xxx */
  1514. }
  1516. /*
  1517.  - isinsets - is this character in any sets?
  1518.  == static int isinsets(struct re_guts *g, int c);
  1519.  */
  1520. static int /* predicate */
  1521. isinsets(g, c)
  1522. struct re_guts *g;
  1523. int c;
  1524. {
  1525. uch    *col;
  1526. int i;
  1527. int ncols = (g->ncsets + (CHAR_BIT - 1)) / CHAR_BIT;
  1528. unsigned uc = (unsigned char) c;
  1530. for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize)
  1531. if (col[uc] != 0)
  1532. return 1;
  1533. return 0;
  1534. }
  1536. /*
  1537.  - samesets - are these two characters in exactly the same sets?
  1538.  == static int samesets(struct re_guts *g, int c1, int c2);
  1539.  */
  1540. static int /* predicate */
  1541. samesets(g, c1, c2)
  1542. struct re_guts *g;
  1543. int c1;
  1544. int c2;
  1545. {
  1546. uch    *col;
  1547. int i;
  1548. int ncols = (g->ncsets + (CHAR_BIT - 1)) / CHAR_BIT;
  1549. unsigned uc1 = (unsigned char) c1;
  1550. unsigned uc2 = (unsigned char) c2;
  1552. for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize)
  1553. if (col[uc1] != col[uc2])
  1554. return 0;
  1555. return 1;
  1556. }
  1558. /*
  1559.  - categorize - sort out character categories
  1560.  == static void categorize(struct parse *p, struct re_guts *g);
  1561.  */
  1562. static void
  1563. categorize(p, g)
  1564. struct parse *p;
  1565. struct re_guts *g;
  1566. {
  1567. cat_t    *cats = g->categories;
  1568. int c;
  1569. int c2;
  1570. cat_t cat;
  1572. /* avoid making error situations worse */
  1573. if (p->error != 0)
  1574. return;
  1576. for (c = CHAR_MIN; c <= CHAR_MAX; c++)
  1577. if (cats[c] == 0 && isinsets(g, c))
  1578. {
  1579. cat = g->ncategories++;
  1580. cats[c] = cat;
  1581. for (c2 = c + 1; c2 <= CHAR_MAX; c2++)
  1582. if (cats[c2] == 0 && samesets(g, c, c2))
  1583. cats[c2] = cat;
  1584. }
  1585. }
  1587. /*
  1588.  - dupl - emit a duplicate of a bunch of sops
  1589.  == static sopno dupl(struct parse *p, sopno start, sopno finish);
  1590.  */
  1591. static sopno /* start of duplicate */
  1592. dupl(p, start, finish)
  1593. struct parse *p;
  1594. sopno start; /* from here */
  1595. sopno finish; /* to this less one */
  1596. {
  1597. sopno ret = HERE();
  1598. sopno len = finish - start;
  1600. assert(finish >= start);
  1601. if (len == 0)
  1602. return ret;
  1603. enlarge(p, p->ssize + len); /* this many unexpected additions */
  1604. assert(p->ssize >= p->slen + len);
  1605. memcpy((char *) (p->strip + p->slen),
  1606.    (char *) (p->strip + start), (size_t) len * sizeof(sop));
  1607. p->slen += len;
  1608. return ret;
  1609. }
  1611. /*
  1612.  - doemit - emit a strip operator
  1613.  == static void doemit(struct parse *p, sop op, size_t opnd);
  1614.  *
  1615.  * It might seem better to implement this as a macro with a function as
  1616.  * hard-case backup, but it's just too big and messy unless there are
  1617.  * some changes to the data structures.  Maybe later.
  1618.  */
  1619. static void
  1620. doemit(p, op, opnd)
  1621. struct parse *p;
  1622. sop op;
  1623. size_t opnd;
  1624. {
  1625. /* avoid making error situations worse */
  1626. if (p->error != 0)
  1627. return;
  1629. /* deal with oversize operands ("can't happen", more or less) */
  1630. assert(opnd < 1 << OPSHIFT);
  1632. /* deal with undersized strip */
  1633. if (p->slen >= p->ssize)
  1634. enlarge(p, (p->ssize + 1) / 2 * 3); /* +50% */
  1635. assert(p->slen < p->ssize);
  1637. /* finally, it's all reduced to the easy case */
  1638. p->strip[p->slen++] = SOP(op, opnd);
  1639. }
  1641. /*
  1642.  - doinsert - insert a sop into the strip
  1643.  == static void doinsert(struct parse *p, sop op, size_t opnd, sopno pos);
  1644.  */
  1645. static void
  1646. doinsert(p, op, opnd, pos)
  1647. struct parse *p;
  1648. sop op;
  1649. size_t opnd;
  1650. sopno pos;
  1651. {
  1652. sopno sn;
  1653. sop s;
  1654. int i;
  1656. /* avoid making error situations worse */
  1657. if (p->error != 0)
  1658. return;
  1660. sn = HERE();
  1661. EMIT(op, opnd); /* do checks, ensure space */
  1662. assert(HERE() == sn + 1);
  1663. s = p->strip[sn];
  1665. /* adjust paren pointers */
  1666. assert(pos > 0);
  1667. for (i = 1; i < NPAREN; i++)
  1668. {
  1669. if (p->pbegin[i] >= pos)
  1670. p->pbegin[i]++;
  1671. if (p->pend[i] >= pos)
  1672. p->pend[i]++;
  1673. }
  1675. memmove((char *) &p->strip[pos + 1], (char *) &p->strip[pos],
  1676. (HERE() - pos - 1) * sizeof(sop));
  1677. p->strip[pos] = s;
  1678. }
  1680. /*
  1681.  - dofwd - complete a forward reference
  1682.  == static void dofwd(struct parse *p, sopno pos, sop value);
  1683.  */
  1684. static void
  1685. dofwd(p, pos, value)
  1686. struct parse *p;
  1687. sopno pos;
  1688. sop value;
  1689. {
  1690. /* avoid making error situations worse */
  1691. if (p->error != 0)
  1692. return;
  1694. assert(value < 1 << OPSHIFT);
  1695. p->strip[pos] = OP(p->strip[pos]) | value;
  1696. }
  1698. /*
  1699.  - enlarge - enlarge the strip
  1700.  == static void enlarge(struct parse *p, sopno size);
  1701.  */
  1702. static void
  1703. enlarge(p, size)
  1704. struct parse *p;
  1705. sopno size;
  1706. {
  1707. sop    *sp;
  1709. if (p->ssize >= size)
  1710. return;
  1712. sp = (sop *) realloc(p->strip, size * sizeof(sop));
  1713. if (sp == NULL)
  1714. {
  1715. SETERROR(REG_ESPACE);
  1716. return;
  1717. }
  1718. p->strip = sp;
  1719. p->ssize = size;
  1720. }
  1722. /*
  1723.  - stripsnug - compact the strip
  1724.  == static void stripsnug(struct parse *p, struct re_guts *g);
  1725.  */
  1726. static void
  1727. stripsnug(p, g)
  1728. struct parse *p;
  1729. struct re_guts *g;
  1730. {
  1731. g->nstates = p->slen;
  1732. g->strip = (sop *) realloc((char *) p->strip, p->slen * sizeof(sop));
  1733. if (g->strip == NULL)
  1734. {
  1735. SETERROR(REG_ESPACE);
  1736. g->strip = p->strip;
  1737. }
  1738. }
  1740. /*
  1741.  - findmust - fill in must and mlen with longest mandatory literal string
  1742.  == static void findmust(struct parse *p, struct re_guts *g);
  1743.  *
  1744.  * This algorithm could do fancy things like analyzing the operands of |
  1745.  * for common subsequences.  Someday.  This code is simple and finds most
  1746.  * of the interesting cases.
  1747.  *
  1748.  * Note that must and mlen got initialized during setup.
  1749.  */
  1750. static void
  1751. findmust(p, g)
  1752. struct parse *p;
  1753. struct re_guts *g;
  1754. {
  1755. sop    *scan;
  1756. sop    *start = 0;
  1757. sop    *newstart = 0;
  1758. sopno newlen;
  1759. sop s;
  1760. pg_wchar   *cp;
  1761. sopno i;
  1763. /* avoid making error situations worse */
  1764. if (p->error != 0)
  1765. return;
  1767. /* find the longest OCHAR sequence in strip */
  1768. newlen = 0;
  1769. scan = g->strip + 1;
  1770. do
  1771. {
  1772. s = *scan++;
  1773. switch (OP(s))
  1774. {
  1775. case OCHAR: /* sequence member */
  1776. if (newlen == 0)/* new sequence */
  1777. newstart = scan - 1;
  1778. newlen++;
  1779. break;
  1780. case OPLUS_: /* things that don't break one */
  1781. case OLPAREN:
  1782. case ORPAREN:
  1783. break;
  1784. case OQUEST_: /* things that must be skipped */
  1785. case OCH_:
  1786. scan--;
  1787. do
  1788. {
  1789. scan += OPND(s);
  1790. s = *scan;
  1791. /* assert() interferes w debug printouts */
  1792. if (OP(s) != O_QUEST && OP(s) != O_CH &&
  1793. OP(s) != OOR2)
  1794. {
  1795. g->iflags |= BAD;
  1796. return;
  1797. }
  1798. } while (OP(s) != O_QUEST && OP(s) != O_CH);
  1799. /* fallthrough */
  1800. default: /* things that break a sequence */
  1801. if (newlen > g->mlen)
  1802. { /* ends one */
  1803. start = newstart;
  1804. g->mlen = newlen;
  1805. }
  1806. newlen = 0;
  1807. break;
  1808. }
  1809. } while (OP(s) != OEND);
  1811. if (g->mlen == 0) /* there isn't one */
  1812. return;
  1814. /* turn it into a character string */
  1815. #ifdef MULTIBYTE
  1816. g->must = (pg_wchar *) malloc((size_t) (g->mlen + 1) * sizeof(pg_wchar));
  1817. #else
  1818. g->must = malloc((size_t) g->mlen + 1);
  1819. #endif
  1820. if (g->must == NULL)
  1821. { /* argh; just forget it */
  1822. g->mlen = 0;
  1823. return;
  1824. }
  1825. cp = g->must;
  1826. scan = start;
  1827. for (i = g->mlen; i > 0; i--)
  1828. {
  1829. while (OP(s = *scan++) != OCHAR)
  1830. continue;
  1831. assert(cp < g->must + g->mlen);
  1832. *cp++ = (pg_wchar) OPND(s);
  1833. }
  1834. assert(cp == g->must + g->mlen);
  1835. *cp++ = ''; /* just on general principles */
  1836. }
  1838. /*
  1839.  - pluscount - count + nesting
  1840.  == static sopno pluscount(struct parse *p, struct re_guts *g);
  1841.  */
  1842. static sopno /* nesting depth */
  1843. pluscount(p, g)
  1844. struct parse *p;
  1845. struct re_guts *g;
  1846. {
  1847. sop    *scan;
  1848. sop s;
  1849. sopno plusnest = 0;
  1850. sopno maxnest = 0;
  1852. if (p->error != 0)
  1853. return 0; /* there may not be an OEND */
  1855. scan = g->strip + 1;
  1856. do
  1857. {
  1858. s = *scan++;
  1859. switch (OP(s))
  1860. {
  1861. case OPLUS_:
  1862. plusnest++;
  1863. break;
  1864. case O_PLUS:
  1865. if (plusnest > maxnest)
  1866. maxnest = plusnest;
  1867. plusnest--;
  1868. break;
  1869. }
  1870. } while (OP(s) != OEND);
  1871. if (plusnest != 0)
  1872. g->iflags |= BAD;
  1873. return maxnest;
  1874. }
  1876. /*
  1877.  * some ctype functions with none-ascii-char guard
  1878.  */
  1879. static int
  1880. pg_isdigit(int c)
  1881. {
  1882. #ifdef MULTIBYTE
  1883. return (c >= 0 && c <= UCHAR_MAX && isdigit(c));
  1884. #else
  1885. return (isdigit(c));
  1886. #endif
  1887. }
  1889. static int
  1890. pg_isalpha(int c)
  1891. {
  1892. #ifdef MULTIBYTE
  1893. return (c >= 0 && c <= UCHAR_MAX && isalpha(c));
  1894. #else
  1895. return (isalpha(c));
  1896. #endif
  1897. }
  1899. static int
  1900. pg_isupper(int c)
  1901. {
  1902. #ifdef MULTIBYTE
  1903. return (c >= 0 && c <= UCHAR_MAX && isupper(c));
  1904. #else
  1905. return (isupper(c));
  1906. #endif
  1907. }
  1909. static int
  1910. pg_islower(int c)
  1911. {
  1912. #ifdef MULTIBYTE
  1913. return (c >= 0 && c <= UCHAR_MAX && islower(c));
  1914. #else
  1915. return (islower(c));
  1916. #endif
  1917. }