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

源码开发语言/平台
当前位置：首页 > 源码/资料 > 嵌入式/单片机编程 > VxWorks > 查看源码
regcore.c
资源名称：vxwork_src.rar　[点击查看]
上传用户：nvosite88
上传日期：2007-01-17
资源大小：4983k
文件大小：29k
源码类别：

VxWorks

开发平台：

C/C++

regcore.c：源码内容
  1. /* regcore.c - regular expression handling */
  3. /*
  4. modification history
  5. --------------------
  6. 01c,02mar98,pcn  Removed warnings.
  7. 01b,30sep96,elp   put in share, adapted to be compiled on target side
  8.   (SPR# 6775).
  9. 01a,10jan95,jcf   created.
  10. */
  12. /*
  13. DESCRIPTION
  15. This library is *not* the original BSD distribution.  Though the changes
  16. were completely cosmetic (file naming, and such), the user of this library
  17. is forewarned.
  19. AUTHOR: Henry Spencer
  20. */
  22. /*-
  23.  * Copyright (c) 1992, 1993, 1994 Henry Spencer.
  24.  * Copyright (c) 1992, 1993, 1994
  25.  * The Regents of the University of California.  All rights reserved.
  26.  *
  27.  * This code is derived from software contributed to Berkeley by
  28.  * Henry Spencer.
  29.  *
  30.  * Redistribution and use in source and binary forms, with or without
  31.  * modification, are permitted provided that the following conditions
  32.  * are met:
  33.  * 1. Redistributions of source code must retain the above copyright
  34.  *    notice, this list of conditions and the following disclaimer.
  35.  * 2. Redistributions in binary form must reproduce the above copyright
  36.  *    notice, this list of conditions and the following disclaimer in the
  37.  *    documentation and/or other materials provided with the distribution.
  38.  * 3. All advertising materials mentioning features or use of this software
  39.  *    must display the following acknowledgement:
  40.  * This product includes software developed by the University of
  41.  * California, Berkeley and its contributors.
  42.  * 4. Neither the name of the University nor the names of its contributors
  43.  *    may be used to endorse or promote products derived from this software
  44.  *    without specific prior written permission.
  45.  *
  46.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  47.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  48.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  49.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  50.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  51.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  52.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  53.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  54.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  55.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  56.  * SUCH DAMAGE.
  57.  *
  58.  * @(#)engine.c 8.5 (Berkeley) 3/20/94
  59.  */
  61. /*
  62.  * The matching engine and friends.  This file is #included by regexec.c
  63.  * after suitable #defines of a variety of macros used herein, so that
  64.  * different state representations can be used without duplicating masses
  65.  * of code.
  66.  */
  68. #ifdef SNAMES
  69. #define matcher smatcher
  70. #define fast sfast
  71. #define slow sslow
  72. #define dissect sdissect
  73. #define backref sbackref
  74. #define step sstep
  75. #define print sprint
  76. #define at sat
  77. #define match smat
  78. #endif
  79. #ifdef LNAMES
  80. #define matcher lmatcher
  81. #define fast lfast
  82. #define slow lslow
  83. #define dissect ldissect
  84. #define backref lbackref
  85. #define step lstep
  86. #define print lprint
  87. #define at lat
  88. #define match lmat
  89. #endif
  91. /* another structure passed up and down to avoid zillions of parameters */
  92. struct match {
  93. struct re_guts *g;
  94. int eflags;
  95. regmatch_t *pmatch; /* [nsub+1] (0 element unused) */
  96. char *offp; /* offsets work from here */
  97. char *beginp; /* start of string -- virtual NUL precedes */
  98. char *endp; /* end of string -- virtual NUL here */
  99. char *coldp; /* can be no match starting before here */
  100. char **lastpos; /* [nplus+1] */
  101. STATEVARS;
  102. states st; /* current states */
  103. states fresh; /* states for a fresh start */
  104. states tmp; /* temporary */
  105. states empty; /* empty set of states */
  106. };
  108. /* ========= begin header generated by ./mkh ========= */
  109. #ifdef __cplusplus
  110. extern "C" {
  111. #endif
  113. /* === engine.c === */
  114. static int matcher __P((struct re_guts *g, char *string, size_t nmatch, regmatch_t pmatch[], int eflags));
  115. static char *dissect __P((struct match *m, char *start, char *stop, sopno startst, sopno stopst));
  116. static char *backref __P((struct match *m, char *start, char *stop, sopno startst, sopno stopst, sopno lev));
  117. static char *fast __P((struct match *m, char *start, char *stop, sopno startst, sopno stopst));
  118. static char *slow __P((struct match *m, char *start, char *stop, sopno startst, sopno stopst));
  119. static states step __P((struct re_guts *g, sopno start, sopno stop, states bef, int ch, states aft));
  120. #define BOL (OUT+1)
  121. #define EOL (BOL+1)
  122. #define BOLEOL (BOL+2)
  123. #define NOTHING (BOL+3)
  124. #define BOW (BOL+4)
  125. #define EOW (BOL+5)
  126. #define CODEMAX (BOL+5) /* highest code used */
  127. #define NONCHAR(c) ((c) > CHAR_MAX)
  128. #define NNONCHAR (CODEMAX-CHAR_MAX)
  129. #ifdef REDEBUG
  130. static void print __P((struct match *m, char *caption, states st, int ch, FILE *d));
  131. #endif
  132. #ifdef REDEBUG
  133. static void at __P((struct match *m, char *title, char *start, char *stop, sopno startst, sopno stopst));
  134. #endif
  135. #ifdef REDEBUG
  136. static char *pchar __P((int ch));
  137. #endif
  139. #ifdef __cplusplus
  140. }
  141. #endif
  142. /* ========= end header generated by ./mkh ========= */
  144. #ifdef REDEBUG
  145. #define SP(t, s, c) print(m, t, s, c, stdout)
  146. #define AT(t, p1, p2, s1, s2) at(m, t, p1, p2, s1, s2)
  147. #define NOTE(str) { if (m->eflags&REG_TRACE) printf("=%sn", (str)); }
  148. #else
  149. #define SP(t, s, c) /* nothing */
  150. #define AT(t, p1, p2, s1, s2) /* nothing */
  151. #define NOTE(s) /* nothing */
  152. #endif
  154. /*
  155.  - matcher - the actual matching engine
  156.  == static int matcher(register struct re_guts *g, char *string, 
  157.  == size_t nmatch, regmatch_t pmatch[], int eflags);
  158.  */
  159. static int /* 0 success, REG_NOMATCH failure */
  160. matcher(g, string, nmatch, pmatch, eflags)
  161. register struct re_guts *g;
  162. char *string;
  163. size_t nmatch;
  164. regmatch_t pmatch[];
  165. int eflags;
  166. {
  167. register char *endp;
  168. register int i;
  169. struct match mv;
  170. register struct match *m = &mv;
  171. register char *dp;
  172. register const sopno gf = g->firststate+1; /* +1 for OEND */
  173. register const sopno gl = g->laststate;
  174. char *start;
  175. char *stop;
  177. /* simplify the situation where possible */
  178. if (g->cflags&REG_NOSUB)
  179. nmatch = 0;
  180. if (eflags&REG_STARTEND) {
  181. start = string + pmatch[0].rm_so;
  182. stop = string + pmatch[0].rm_eo;
  183. } else {
  184. start = string;
  185. stop = start + strlen(start);
  186. }
  187. if (stop < start)
  188. return(REG_INVARG);
  190. /* prescreening; this does wonders for this rather slow code */
  191. if (g->must != NULL) {
  192. for (dp = start; dp < stop; dp++)
  193. if (*dp == g->must[0] && stop - dp >= g->mlen &&
  194. memcmp(dp, g->must, (size_t)g->mlen) == 0)
  195. break;
  196. if (dp == stop) /* we didn't find g->must */
  197. return(REG_NOMATCH);
  198. }
  200. /* match struct setup */
  201. m->g = g;
  202. m->eflags = eflags;
  203. m->pmatch = NULL;
  204. m->lastpos = NULL;
  205. m->offp = string;
  206. m->beginp = start;
  207. m->endp = stop;
  208. STATESETUP(m, 4);
  209. SETUP(m->st);
  210. SETUP(m->fresh);
  211. SETUP(m->tmp);
  212. SETUP(m->empty);
  213. CLEAR(m->empty);
  215. /* this loop does only one repetition except for backrefs */
  216. for (;;) {
  217. endp = fast(m, start, stop, gf, gl);
  218. if (endp == NULL) { /* a miss */
  219. STATETEARDOWN(m);
  220. return(REG_NOMATCH);
  221. }
  222. if (nmatch == 0 && !g->backrefs)
  223. break; /* no further info needed */
  225. /* where? */
  226. assert(m->coldp != NULL);
  227. for (;;) {
  228. NOTE("finding start");
  229. endp = slow(m, m->coldp, stop, gf, gl);
  230. if (endp != NULL)
  231. break;
  232. assert(m->coldp < m->endp);
  233. m->coldp++;
  234. }
  235. if (nmatch == 1 && !g->backrefs)
  236. break; /* no further info needed */
  238. /* oh my, he wants the subexpressions... */
  239. if (m->pmatch == NULL)
  240. m->pmatch = (regmatch_t *)malloc((m->g->nsub + 1) *
  241. sizeof(regmatch_t));
  242. if (m->pmatch == NULL) {
  243. STATETEARDOWN(m);
  244. return(REG_ESPACE);
  245. }
  246. for (i = 1; i <= (int)(m->g->nsub); i++)
  247. m->pmatch[i].rm_so = m->pmatch[i].rm_eo = -1;
  248. if (!g->backrefs && !(m->eflags&REG_BACKR)) {
  249. NOTE("dissecting");
  250. dp = dissect(m, m->coldp, endp, gf, gl);
  251. } else {
  252. if (g->nplus > 0 && m->lastpos == NULL)
  253. m->lastpos = (char **)malloc((g->nplus+1) *
  254. sizeof(char *));
  255. if (g->nplus > 0 && m->lastpos == NULL) {
  256. free(m->pmatch);
  257. STATETEARDOWN(m);
  258. return(REG_ESPACE);
  259. }
  260. NOTE("backref dissect");
  261. dp = backref(m, m->coldp, endp, gf, gl, (sopno)0);
  262. }
  263. if (dp != NULL)
  264. break;
  266. /* uh-oh... we couldn't find a subexpression-level match */
  267. assert(g->backrefs); /* must be back references doing it */
  268. assert(g->nplus == 0 || m->lastpos != NULL);
  269. for (;;) {
  270. if (dp != NULL || endp <= m->coldp)
  271. break; /* defeat */
  272. NOTE("backoff");
  273. endp = slow(m, m->coldp, endp-1, gf, gl);
  274. if (endp == NULL)
  275. break; /* defeat */
  276. /* try it on a shorter possibility */
  277. #ifndef NDEBUG
  278. for (i = 1; i <= m->g->nsub; i++) {
  279. assert(m->pmatch[i].rm_so == -1);
  280. assert(m->pmatch[i].rm_eo == -1);
  281. }
  282. #endif
  283. NOTE("backoff dissect");
  284. dp = backref(m, m->coldp, endp, gf, gl, (sopno)0);
  285. }
  286. assert(dp == NULL || dp == endp);
  287. if (dp != NULL) /* found a shorter one */
  288. break;
  290. /* despite initial appearances, there is no match here */
  291. NOTE("false alarm");
  292. start = m->coldp + 1; /* recycle starting later */
  293. assert(start <= stop);
  294. }
  296. /* fill in the details if requested */
  297. if (nmatch > 0) {
  298. pmatch[0].rm_so = m->coldp - m->offp;
  299. pmatch[0].rm_eo = endp - m->offp;
  300. }
  301. if (nmatch > 1) {
  302. assert(m->pmatch != NULL);
  303. for (i = 1; i < (int)nmatch; i++)
  304. if (i <= (int)(m->g->nsub))
  305. pmatch[i] = m->pmatch[i];
  306. else {
  307. pmatch[i].rm_so = -1;
  308. pmatch[i].rm_eo = -1;
  309. }
  310. }
  312. if (m->pmatch != NULL)
  313. free((char *)m->pmatch);
  314. if (m->lastpos != NULL)
  315. free((char *)m->lastpos);
  316. STATETEARDOWN(m);
  317. return(0);
  318. }
  320. /*
  321.  - dissect - figure out what matched what, no back references
  322.  == static char *dissect(register struct match *m, char *start, 
  323.  == char *stop, sopno startst, sopno stopst);
  324.  */
  325. static char * /* == stop (success) always */
  326. dissect(m, start, stop, startst, stopst)
  327. register struct match *m;
  328. char *start;
  329. char *stop;
  330. sopno startst;
  331. sopno stopst;
  332. {
  333. register int i;
  334. register sopno ss; /* start sop of current subRE */
  335. register sopno es; /* end sop of current subRE */
  336. register char *sp; /* start of string matched by it */
  337. register char *stp; /* string matched by it cannot pass here */
  338. register char *rest; /* start of rest of string */
  339. register char *tail; /* string unmatched by rest of RE */
  340. register sopno ssub; /* start sop of subsubRE */
  341. register sopno esub; /* end sop of subsubRE */
  342. register char *ssp; /* start of string matched by subsubRE */
  343. register char *sep; /* end of string matched by subsubRE */
  344. register char *oldssp; /* previous ssp */
  345. register char *dp;
  347. AT("diss", start, stop, startst, stopst);
  348. sp = start;
  349. for (ss = startst; ss < stopst; ss = es) {
  350. /* identify end of subRE */
  351. es = ss;
  352. switch (OP(m->g->strip[es])) {
  353. case OPLUS_:
  354. case OQUEST_:
  355. es += OPND(m->g->strip[es]);
  356. break;
  357. case OCH_:
  358. while ((int)OP(m->g->strip[es]) != O_CH)
  359. es += OPND(m->g->strip[es]);
  360. break;
  361. }
  362. es++;
  364. /* figure out what it matched */
  365. switch (OP(m->g->strip[ss])) {
  366. case OEND:
  367. assert(nope);
  368. break;
  369. case OCHAR:
  370. sp++;
  371. break;
  372. case OBOL:
  373. case OEOL:
  374. case OBOW:
  375. case OEOW:
  376. break;
  377. case OANY:
  378. case OANYOF:
  379. sp++;
  380. break;
  381. case OBACK_:
  382. case O_BACK:
  383. assert(nope);
  384. break;
  385. /* cases where length of match is hard to find */
  386. case OQUEST_:
  387. stp = stop;
  388. for (;;) {
  389. /* how long could this one be? */
  390. rest = slow(m, sp, stp, ss, es);
  391. assert(rest != NULL); /* it did match */
  392. /* could the rest match the rest? */
  393. tail = slow(m, rest, stop, es, stopst);
  394. if (tail == stop)
  395. break; /* yes! */
  396. /* no -- try a shorter match for this one */
  397. stp = rest - 1;
  398. assert(stp >= sp); /* it did work */
  399. }
  400. ssub = ss + 1;
  401. esub = es - 1;
  402. /* did innards match? */
  403. if (slow(m, sp, rest, ssub, esub) != NULL) {
  404. dp = dissect(m, sp, rest, ssub, esub);
  405. assert(dp == rest);
  406. } else /* no */
  407. assert(sp == rest);
  408. sp = rest;
  409. break;
  410. case OPLUS_:
  411. stp = stop;
  412. for (;;) {
  413. /* how long could this one be? */
  414. rest = slow(m, sp, stp, ss, es);
  415. assert(rest != NULL); /* it did match */
  416. /* could the rest match the rest? */
  417. tail = slow(m, rest, stop, es, stopst);
  418. if (tail == stop)
  419. break; /* yes! */
  420. /* no -- try a shorter match for this one */
  421. stp = rest - 1;
  422. assert(stp >= sp); /* it did work */
  423. }
  424. ssub = ss + 1;
  425. esub = es - 1;
  426. ssp = sp;
  427. oldssp = ssp;
  428. for (;;) { /* find last match of innards */
  429. sep = slow(m, ssp, rest, ssub, esub);
  430. if (sep == NULL || sep == ssp)
  431. break; /* failed or matched null */
  432. oldssp = ssp; /* on to next try */
  433. ssp = sep;
  434. }
  435. if (sep == NULL) {
  436. /* last successful match */
  437. sep = ssp;
  438. ssp = oldssp;
  439. }
  440. assert(sep == rest); /* must exhaust substring */
  441. assert(slow(m, ssp, sep, ssub, esub) == rest);
  442. dp = dissect(m, ssp, sep, ssub, esub);
  443. assert(dp == sep);
  444. sp = rest;
  445. break;
  446. case OCH_:
  447. stp = stop;
  448. for (;;) {
  449. /* how long could this one be? */
  450. rest = slow(m, sp, stp, ss, es);
  451. assert(rest != NULL); /* it did match */
  452. /* could the rest match the rest? */
  453. tail = slow(m, rest, stop, es, stopst);
  454. if (tail == stop)
  455. break; /* yes! */
  456. /* no -- try a shorter match for this one */
  457. stp = rest - 1;
  458. assert(stp >= sp); /* it did work */
  459. }
  460. ssub = ss + 1;
  461. esub = ss + OPND(m->g->strip[ss]) - 1;
  462. assert(OP(m->g->strip[esub]) == OOR1);
  463. for (;;) { /* find first matching branch */
  464. if (slow(m, sp, rest, ssub, esub) == rest)
  465. break; /* it matched all of it */
  466. /* that one missed, try next one */
  467. assert(OP(m->g->strip[esub]) == OOR1);
  468. esub++;
  469. assert(OP(m->g->strip[esub]) == OOR2);
  470. ssub = esub + 1;
  471. esub += OPND(m->g->strip[esub]);
  472. if ((int)OP(m->g->strip[esub]) == OOR2)
  473. esub--;
  474. else
  475. assert(OP(m->g->strip[esub]) == O_CH);
  476. }
  477. dp = dissect(m, sp, rest, ssub, esub);
  478. assert(dp == rest);
  479. sp = rest;
  480. break;
  481. case O_PLUS:
  482. case O_QUEST:
  483. case OOR1:
  484. case OOR2:
  485. case O_CH:
  486. assert(nope);
  487. break;
  488. case OLPAREN:
  489. i = OPND(m->g->strip[ss]);
  490. assert(0 < i && i <= m->g->nsub);
  491. m->pmatch[i].rm_so = sp - m->offp;
  492. break;
  493. case ORPAREN:
  494. i = OPND(m->g->strip[ss]);
  495. assert(0 < i && i <= m->g->nsub);
  496. m->pmatch[i].rm_eo = sp - m->offp;
  497. break;
  498. default: /* uh oh */
  499. assert(nope);
  500. break;
  501. }
  502. }
  504. assert(sp == stop);
  505. return(sp);
  506. }
  508. /*
  509.  - backref - figure out what matched what, figuring in back references
  510.  == static char *backref(register struct match *m, char *start, 
  511.  == char *stop, sopno startst, sopno stopst, sopno lev);
  512.  */
  513. static char * /* == stop (success) or NULL (failure) */
  514. backref(m, start, stop, startst, stopst, lev)
  515. register struct match *m;
  516. char *start;
  517. char *stop;
  518. sopno startst;
  519. sopno stopst;
  520. sopno lev; /* PLUS nesting level */
  521. {
  522. register int i;
  523. register sopno ss; /* start sop of current subRE */
  524. register char *sp; /* start of string matched by it */
  525. register sopno ssub; /* start sop of subsubRE */
  526. register sopno esub; /* end sop of subsubRE */
  527. register char *ssp; /* start of string matched by subsubRE */
  528. register char *dp;
  529. register size_t len;
  530. register int hard;
  531. register sop s;
  532. register regoff_t offsave;
  533. register cset *cs;
  535. AT("back", start, stop, startst, stopst);
  536. sp = start;
  538. /* get as far as we can with easy stuff */
  539. hard = 0;
  540. for (ss = startst; !hard && ss < stopst; ss++)
  541. switch (OP(s = m->g->strip[ss])) {
  542. case OCHAR:
  543. if (sp == stop || *sp++ != (char)OPND(s))
  544. return(NULL);
  545. break;
  546. case OANY:
  547. if (sp == stop)
  548. return(NULL);
  549. sp++;
  550. break;
  551. case OANYOF:
  552. cs = &m->g->sets[OPND(s)];
  553. if (sp == stop || !CHIN(cs, *sp++))
  554. return(NULL);
  555. break;
  556. case OBOL:
  557. if ( (sp == m->beginp && !(m->eflags&REG_NOTBOL)) ||
  558. (sp < m->endp && *(sp-1) == 'n' &&
  559. (m->g->cflags&REG_NEWLINE)) )
  560. { /* yes */ }
  561. else
  562. return(NULL);
  563. break;
  564. case OEOL:
  565. if ( (sp == m->endp && !(m->eflags&REG_NOTEOL)) ||
  566. (sp < m->endp && *sp == 'n' &&
  567. (m->g->cflags&REG_NEWLINE)) )
  568. { /* yes */ }
  569. else
  570. return(NULL);
  571. break;
  572. case OBOW:
  573. if (( (sp == m->beginp && !(m->eflags&REG_NOTBOL)) ||
  574. (sp < m->endp && *(sp-1) == 'n' &&
  575. (m->g->cflags&REG_NEWLINE)) ||
  576. (sp > m->beginp &&
  577. !ISWORD(*(sp-1))) ) &&
  578. (sp < m->endp && ISWORD(*sp)) )
  579. { /* yes */ }
  580. else
  581. return(NULL);
  582. break;
  583. case OEOW:
  584. if (( (sp == m->endp && !(m->eflags&REG_NOTEOL)) ||
  585. (sp < m->endp && *sp == 'n' &&
  586. (m->g->cflags&REG_NEWLINE)) ||
  587. (sp < m->endp && !ISWORD(*sp)) ) &&
  588. (sp > m->beginp && ISWORD(*(sp-1))) )
  589. { /* yes */ }
  590. else
  591. return(NULL);
  592. break;
  593. case O_QUEST:
  594. break;
  595. case OOR1: /* matches null but needs to skip */
  596. ss++;
  597. s = m->g->strip[ss];
  598. do {
  599. assert(OP(s) == OOR2);
  600. ss += OPND(s);
  601. } while ((int)OP(s = m->g->strip[ss]) != O_CH);
  602. /* note that the ss++ gets us past the O_CH */
  603. break;
  604. default: /* have to make a choice */
  605. hard = 1;
  606. break;
  607. }
  608. if (!hard) { /* that was it! */
  609. if (sp != stop)
  610. return(NULL);
  611. return(sp);
  612. }
  613. ss--; /* adjust for the for's final increment */
  615. /* the hard stuff */
  616. AT("hard", sp, stop, ss, stopst);
  617. s = m->g->strip[ss];
  618. switch (OP(s)) {
  619. case OBACK_: /* the vilest depths */
  620. i = OPND(s);
  621. assert(0 < i && i <= m->g->nsub);
  622. if (m->pmatch[i].rm_eo == -1)
  623. return(NULL);
  624. assert(m->pmatch[i].rm_so != -1);
  625. len = m->pmatch[i].rm_eo - m->pmatch[i].rm_so;
  626. assert(stop - m->beginp >= len);
  627. if (sp > stop - len)
  628. return(NULL); /* not enough left to match */
  629. ssp = m->offp + m->pmatch[i].rm_so;
  630. if (memcmp(sp, ssp, len) != 0)
  631. return(NULL);
  632. while ((int)(m->g->strip[ss]) != SOP(O_BACK, i))
  633. ss++;
  634. return(backref(m, sp+len, stop, ss+1, stopst, lev));
  635. break;
  636. case OQUEST_: /* to null or not */
  637. dp = backref(m, sp, stop, ss+1, stopst, lev);
  638. if (dp != NULL)
  639. return(dp); /* not */
  640. return(backref(m, sp, stop, ss+OPND(s)+1, stopst, lev));
  641. break;
  642. case OPLUS_:
  643. assert(m->lastpos != NULL);
  644. assert(lev+1 <= m->g->nplus);
  645. m->lastpos[lev+1] = sp;
  646. return(backref(m, sp, stop, ss+1, stopst, lev+1));
  647. break;
  648. case O_PLUS:
  649. if (sp == m->lastpos[lev]) /* last pass matched null */
  650. return(backref(m, sp, stop, ss+1, stopst, lev-1));
  651. /* try another pass */
  652. m->lastpos[lev] = sp;
  653. dp = backref(m, sp, stop, ss-OPND(s)+1, stopst, lev);
  654. if (dp == NULL)
  655. return(backref(m, sp, stop, ss+1, stopst, lev-1));
  656. else
  657. return(dp);
  658. break;
  659. case OCH_: /* find the right one, if any */
  660. ssub = ss + 1;
  661. esub = ss + OPND(s) - 1;
  662. assert(OP(m->g->strip[esub]) == OOR1);
  663. for (;;) { /* find first matching branch */
  664. dp = backref(m, sp, stop, ssub, esub, lev);
  665. if (dp != NULL)
  666. return(dp);
  667. /* that one missed, try next one */
  668. if ((int)OP(m->g->strip[esub]) == O_CH)
  669. return(NULL); /* there is none */
  670. esub++;
  671. assert(OP(m->g->strip[esub]) == OOR2);
  672. ssub = esub + 1;
  673. esub += OPND(m->g->strip[esub]);
  674. if ((int)OP(m->g->strip[esub]) == OOR2)
  675. esub--;
  676. else
  677. assert(OP(m->g->strip[esub]) == O_CH);
  678. }
  679. break;
  680. case OLPAREN: /* must undo assignment if rest fails */
  681. i = OPND(s);
  682. assert(0 < i && i <= m->g->nsub);
  683. offsave = m->pmatch[i].rm_so;
  684. m->pmatch[i].rm_so = sp - m->offp;
  685. dp = backref(m, sp, stop, ss+1, stopst, lev);
  686. if (dp != NULL)
  687. return(dp);
  688. m->pmatch[i].rm_so = offsave;
  689. return(NULL);
  690. break;
  691. case ORPAREN: /* must undo assignment if rest fails */
  692. i = OPND(s);
  693. assert(0 < i && i <= m->g->nsub);
  694. offsave = m->pmatch[i].rm_eo;
  695. m->pmatch[i].rm_eo = sp - m->offp;
  696. dp = backref(m, sp, stop, ss+1, stopst, lev);
  697. if (dp != NULL)
  698. return(dp);
  699. m->pmatch[i].rm_eo = offsave;
  700. return(NULL);
  701. break;
  702. default: /* uh oh */
  703. assert(nope);
  704. break;
  705. }
  707. /* "can't happen" */
  708. assert(nope);
  709. /* NOTREACHED */
  710.         return(NULL);
  711. }
  713. /*
  714.  - fast - step through the string at top speed
  715.  == static char *fast(register struct match *m, char *start, 
  716.  == char *stop, sopno startst, sopno stopst);
  717.  */
  718. static char * /* where tentative match ended, or NULL */
  719. fast(m, start, stop, startst, stopst)
  720. register struct match *m;
  721. char *start;
  722. char *stop;
  723. sopno startst;
  724. sopno stopst;
  725. {
  726. register states st = m->st;
  727. register states fresh = m->fresh;
  728. register states tmp = m->tmp;
  729. register char *p = start;
  730. register int c = (start == m->beginp) ? OUT : *(start-1);
  731. register int lastc; /* previous c */
  732. register int flagch;
  733. register int i;
  734. register char *coldp; /* last p after which no match was underway */
  736. CLEAR(st);
  737. SET1(st, startst);
  738. st = step(m->g, startst, stopst, st, NOTHING, st);
  739. ASSIGN(fresh, st);
  740. SP("start", st, *p);
  741. coldp = NULL;
  742. for (;;) {
  743. /* next character */
  744. lastc = c;
  745. c = (p == m->endp) ? OUT : *p;
  746. if (EQ(st, fresh))
  747. coldp = p;
  749. /* is there an EOL and/or BOL between lastc and c? */
  750. flagch = '';
  751. i = 0;
  752. if ( (lastc == 'n' && m->g->cflags&REG_NEWLINE) ||
  753. (lastc == OUT && !(m->eflags&REG_NOTBOL)) ) {
  754. flagch = BOL;
  755. i = m->g->nbol;
  756. }
  757. if ( (c == 'n' && m->g->cflags&REG_NEWLINE) ||
  758. (c == OUT && !(m->eflags&REG_NOTEOL)) ) {
  759. flagch = (flagch == BOL) ? BOLEOL : EOL;
  760. i += m->g->neol;
  761. }
  762. if (i != 0) {
  763. for (; i > 0; i--)
  764. st = step(m->g, startst, stopst, st, flagch, st);
  765. SP("boleol", st, c);
  766. }
  768. /* how about a word boundary? */
  769. if ( (flagch == BOL || (lastc != OUT && !ISWORD(lastc))) &&
  770. (c != OUT && ISWORD(c)) ) {
  771. flagch = BOW;
  772. }
  773. if ( (lastc != OUT && ISWORD(lastc)) &&
  774. (flagch == EOL || (c != OUT && !ISWORD(c))) ) {
  775. flagch = EOW;
  776. }
  777. if (flagch == BOW || flagch == EOW) {
  778. st = step(m->g, startst, stopst, st, flagch, st);
  779. SP("boweow", st, c);
  780. }
  782. /* are we done? */
  783. if (ISSET(st, stopst) || p == stop)
  784. break; /* NOTE BREAK OUT */
  786. /* no, we must deal with this character */
  787. ASSIGN(tmp, st);
  788. ASSIGN(st, fresh);
  789. assert(c != OUT);
  790. st = step(m->g, startst, stopst, tmp, c, st);
  791. SP("aft", st, c);
  792. assert(EQ(step(m->g, startst, stopst, st, NOTHING, st), st));
  793. p++;
  794. }
  796. assert(coldp != NULL);
  797. m->coldp = coldp;
  798. if (ISSET(st, stopst))
  799. return(p+1);
  800. else
  801. return(NULL);
  802. }
  804. /*
  805.  - slow - step through the string more deliberately
  806.  == static char *slow(register struct match *m, char *start, 
  807.  == char *stop, sopno startst, sopno stopst);
  808.  */
  809. static char * /* where it ended */
  810. slow(m, start, stop, startst, stopst)
  811. register struct match *m;
  812. char *start;
  813. char *stop;
  814. sopno startst;
  815. sopno stopst;
  816. {
  817. register states st = m->st;
  818. register states empty = m->empty;
  819. register states tmp = m->tmp;
  820. register char *p = start;
  821. register int c = (start == m->beginp) ? OUT : *(start-1);
  822. register int lastc; /* previous c */
  823. register int flagch;
  824. register int i;
  825. register char *matchp; /* last p at which a match ended */
  827. AT("slow", start, stop, startst, stopst);
  828. CLEAR(st);
  829. SET1(st, startst);
  830. SP("sstart", st, *p);
  831. st = step(m->g, startst, stopst, st, NOTHING, st);
  832. matchp = NULL;
  833. for (;;) {
  834. /* next character */
  835. lastc = c;
  836. c = (p == m->endp) ? OUT : *p;
  838. /* is there an EOL and/or BOL between lastc and c? */
  839. flagch = '';
  840. i = 0;
  841. if ( (lastc == 'n' && m->g->cflags&REG_NEWLINE) ||
  842. (lastc == OUT && !(m->eflags&REG_NOTBOL)) ) {
  843. flagch = BOL;
  844. i = m->g->nbol;
  845. }
  846. if ( (c == 'n' && m->g->cflags&REG_NEWLINE) ||
  847. (c == OUT && !(m->eflags&REG_NOTEOL)) ) {
  848. flagch = (flagch == BOL) ? BOLEOL : EOL;
  849. i += m->g->neol;
  850. }
  851. if (i != 0) {
  852. for (; i > 0; i--)
  853. st = step(m->g, startst, stopst, st, flagch, st);
  854. SP("sboleol", st, c);
  855. }
  857. /* how about a word boundary? */
  858. if ( (flagch == BOL || (lastc != OUT && !ISWORD(lastc))) &&
  859. (c != OUT && ISWORD(c)) ) {
  860. flagch = BOW;
  861. }
  862. if ( (lastc != OUT && ISWORD(lastc)) &&
  863. (flagch == EOL || (c != OUT && !ISWORD(c))) ) {
  864. flagch = EOW;
  865. }
  866. if (flagch == BOW || flagch == EOW) {
  867. st = step(m->g, startst, stopst, st, flagch, st);
  868. SP("sboweow", st, c);
  869. }
  871. /* are we done? */
  872. if (ISSET(st, stopst))
  873. matchp = p;
  874. if (EQ(st, empty) || p == stop)
  875. break; /* NOTE BREAK OUT */
  877. /* no, we must deal with this character */
  878. ASSIGN(tmp, st);
  879. ASSIGN(st, empty);
  880. assert(c != OUT);
  881. st = step(m->g, startst, stopst, tmp, c, st);
  882. SP("saft", st, c);
  883. assert(EQ(step(m->g, startst, stopst, st, NOTHING, st), st));
  884. p++;
  885. }
  887. return(matchp);
  888. }
  891. /*
  892.  - step - map set of states reachable before char to set reachable after
  893.  == static states step(register struct re_guts *g, sopno start, sopno stop, 
  894.  == register states bef, int ch, register states aft);
  895.  == #define BOL (OUT+1)
  896.  == #define EOL (BOL+1)
  897.  == #define BOLEOL (BOL+2)
  898.  == #define NOTHING (BOL+3)
  899.  == #define BOW (BOL+4)
  900.  == #define EOW (BOL+5)
  901.  == #define CODEMAX (BOL+5) // highest code used
  902.  == #define NONCHAR(c) ((c) > CHAR_MAX)
  903.  == #define NNONCHAR (CODEMAX-CHAR_MAX)
  904.  */
  905. static states
  906. step(g, start, stop, bef, ch, aft)
  907. register struct re_guts *g;
  908. sopno start; /* start state within strip */
  909. sopno stop; /* state after stop state within strip */
  910. register states bef; /* states reachable before */
  911. int ch; /* character or NONCHAR code */
  912. register states aft; /* states already known reachable after */
  913. {
  914. register cset *cs;
  915. register sop s;
  916. register sopno pc;
  917. register onestate here; /* note, macros know this name */
  918. register sopno look;
  919. register int i;
  921. for (pc = start, INIT(here, pc); pc != stop; pc++, INC(here)) {
  922. s = g->strip[pc];
  923. switch (OP(s)) {
  924. case OEND:
  925. assert(pc == stop-1);
  926. break;
  927. case OCHAR:
  928. /* only characters can match */
  929. assert(!NONCHAR(ch) || ch != (char)OPND(s));
  930. if (ch == (char)OPND(s))
  931. FWD(aft, bef, 1);
  932. break;
  933. case OBOL:
  934. if (ch == BOL || ch == BOLEOL)
  935. FWD(aft, bef, 1);
  936. break;
  937. case OEOL:
  938. if (ch == EOL || ch == BOLEOL)
  939. FWD(aft, bef, 1);
  940. break;
  941. case OBOW:
  942. if (ch == BOW)
  943. FWD(aft, bef, 1);
  944. break;
  945. case OEOW:
  946. if (ch == EOW)
  947. FWD(aft, bef, 1);
  948. break;
  949. case OANY:
  950. if (!NONCHAR(ch))
  951. FWD(aft, bef, 1);
  952. break;
  953. case OANYOF:
  954. cs = &g->sets[OPND(s)];
  955. if (!NONCHAR(ch) && CHIN(cs, ch))
  956. FWD(aft, bef, 1);
  957. break;
  958. case OBACK_: /* ignored here */
  959. case O_BACK:
  960. FWD(aft, aft, 1);
  961. break;
  962. case OPLUS_: /* forward, this is just an empty */
  963. FWD(aft, aft, 1);
  964. break;
  965. case O_PLUS: /* both forward and back */
  966. FWD(aft, aft, 1);
  967. i = ISSETBACK(aft, OPND(s));
  968. BACK(aft, aft, OPND(s));
  969. if (!i && ISSETBACK(aft, OPND(s))) {
  970. /* oho, must reconsider loop body */
  971. pc -= OPND(s) + 1;
  972. INIT(here, pc);
  973. }
  974. break;
  975. case OQUEST_: /* two branches, both forward */
  976. FWD(aft, aft, 1);
  977. FWD(aft, aft, OPND(s));
  978. break;
  979. case O_QUEST: /* just an empty */
  980. FWD(aft, aft, 1);
  981. break;
  982. case OLPAREN: /* not significant here */
  983. case ORPAREN:
  984. FWD(aft, aft, 1);
  985. break;
  986. case OCH_: /* mark the first two branches */
  987. FWD(aft, aft, 1);
  988. assert(OP(g->strip[pc+OPND(s)]) == OOR2);
  989. FWD(aft, aft, OPND(s));
  990. break;
  991. case OOR1: /* done a branch, find the O_CH */
  992. if (ISSTATEIN(aft, here)) {
  993. for (look = 1;
  994.      (int)OP(s = g->strip[pc+look]) != O_CH;
  995. look += OPND(s))
  996. assert(OP(s) == OOR2);
  997. FWD(aft, aft, look);
  998. }
  999. break;
  1000. case OOR2: /* propagate OCH_'s marking */
  1001. FWD(aft, aft, 1);
  1002. if ((int)OP(g->strip[pc+OPND(s)]) != O_CH) {
  1003. assert(OP(g->strip[pc+OPND(s)]) == OOR2);
  1004. FWD(aft, aft, OPND(s));
  1005. }
  1006. break;
  1007. case O_CH: /* just empty */
  1008. FWD(aft, aft, 1);
  1009. break;
  1010. default: /* ooooops... */
  1011. assert(nope);
  1012. break;
  1013. }
  1014. }
  1016. return(aft);
  1017. }
  1019. #ifdef REDEBUG
  1020. /*
  1021.  - print - print a set of states
  1022.  == #ifdef REDEBUG
  1023.  == static void print(struct match *m, char *caption, states st, 
  1024.  == int ch, FILE *d);
  1025.  == #endif
  1026.  */
  1027. static void
  1028. print(m, caption, st, ch, d)
  1029. struct match *m;
  1030. char *caption;
  1031. states st;
  1032. int ch;
  1033. FILE *d;
  1034. {
  1035. register struct re_guts *g = m->g;
  1036. register int i;
  1037. register int first = 1;
  1039. if (!(m->eflags&REG_TRACE))
  1040. return;
  1042. fprintf(d, "%s", caption);
  1043. if (ch != '')
  1044. fprintf(d, " %s", pchar(ch));
  1045. for (i = 0; i < g->nstates; i++)
  1046. if (ISSET(st, i)) {
  1047. fprintf(d, "%s%d", (first) ? "t" : ", ", i);
  1048. first = 0;
  1049. }
  1050. fprintf(d, "n");
  1051. }
  1053. /* 
  1054.  - at - print current situation
  1055.  == #ifdef REDEBUG
  1056.  == static void at(struct match *m, char *title, char *start, char *stop, 
  1057.  == sopno startst, sopno stopst);
  1058.  == #endif
  1059.  */
  1060. static void
  1061. at(m, title, start, stop, startst, stopst)
  1062. struct match *m;
  1063. char *title;
  1064. char *start;
  1065. char *stop;
  1066. sopno startst;
  1067. sopno stopst;
  1068. {
  1069. if (!(m->eflags&REG_TRACE))
  1070. return;
  1072. printf("%s %s-", title, pchar(*start));
  1073. printf("%s ", pchar(*stop));
  1074. printf("%ld-%ldn", (long)startst, (long)stopst);
  1075. }
  1077. #ifndef PCHARDONE
  1078. #define PCHARDONE /* never again */
  1079. /*
  1080.  - pchar - make a character printable
  1081.  == #ifdef REDEBUG
  1082.  == static char *pchar(int ch);
  1083.  == #endif
  1084.  *
  1085.  * Is this identical to regchar() over in debug.c?  Well, yes.  But a
  1086.  * duplicate here avoids having a debugging-capable regexec.o tied to
  1087.  * a matching debug.o, and this is convenient.  It all disappears in
  1088.  * the non-debug compilation anyway, so it doesn't matter much.
  1089.  */
  1090. static char * /* -> representation */
  1091. pchar(ch)
  1092. int ch;
  1093. {
  1094. static char pbuf[10];
  1096. if (isprint(ch) || ch == ' ')
  1097. sprintf(pbuf, "%c", ch);
  1098. else
  1099. sprintf(pbuf, "\%o", ch);
  1100. return(pbuf);
  1101. }
  1102. #endif
  1103. #endif
  1105. #undef matcher
  1106. #undef fast
  1107. #undef slow
  1108. #undef dissect
  1109. #undef backref
  1110. #undef step
  1111. #undef print
  1112. #undef at
  1113. #undef match