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

源码开发语言/平台
当前位置：首页 > 源码/资料 > 嵌入式/单片机编程 > 查看源码
regcomp.c
资源名称：vxWorks_src.rar　[点击查看]
上传用户：baixin
上传日期：2008-03-13
资源大小：4795k
文件大小：45k
源码类别：

嵌入式/单片机编程

开发平台：

MultiPlatform

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