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

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

MySQL数据库

开发平台：

Visual C++

engine.c：源码内容
  1. /*
  2.  * The matching engine and friends.  This file is #included by regexec.c
  3.  * after suitable #defines of a variety of macros used herein, so that
  4.  * different state representations can be used without duplicating masses
  5.  * of code.
  6.  */
  8. #ifdef SNAMES
  9. #define matcher smatcher
  10. #define fast sfast
  11. #define slow sslow
  12. #define dissect sdissect
  13. #define backref sbackref
  14. #define step sstep
  15. #define print sprint
  16. #define at sat
  17. #define match smat
  18. #endif
  19. #ifdef LNAMES
  20. #define matcher lmatcher
  21. #define fast lfast
  22. #define slow lslow
  23. #define dissect ldissect
  24. #define backref lbackref
  25. #define step lstep
  26. #define print lprint
  27. #define at lat
  28. #define match lmat
  29. #endif
  31. /* another structure passed up and down to avoid zillions of parameters */
  32. struct match {
  33. struct re_guts *g;
  34. int eflags;
  35. regmatch_t *pmatch; /* [nsub+1] (0 element unused) */
  36. char *offp; /* offsets work from here */
  37. char *beginp; /* start of string -- virtual NUL precedes */
  38. char *endp; /* end of string -- virtual NUL here */
  39. char *coldp; /* can be no match starting before here */
  40. char **lastpos; /* [nplus+1] */
  41. STATEVARS;
  42. states st; /* current states */
  43. states fresh; /* states for a fresh start */
  44. states tmp; /* temporary */
  45. states empty; /* empty set of states */
  46. };
  48. #include "engine.ih"
  50. #ifdef REDEBUG
  51. #define SP(t, s, c) print(m, t, s, c, stdout)
  52. #define AT(t, p1, p2, s1, s2) at(m, t, p1, p2, s1, s2)
  53. #define NOTE(str) { if (m->eflags&REG_TRACE) printf("=%sn", (str)); }
  54. #else
  55. #define SP(t, s, c) /* nothing */
  56. #define AT(t, p1, p2, s1, s2) /* nothing */
  57. #define NOTE(s) /* nothing */
  58. #endif
  60. /*
  61.  - matcher - the actual matching engine
  62.  == static int matcher(register struct re_guts *g, char *string, 
  63.  == size_t nmatch, regmatch_t pmatch[], int eflags);
  64.  */
  65. static int /* 0 success, REG_NOMATCH failure */
  66. matcher(g, str, nmatch, pmatch, eflags)
  67. register struct re_guts *g;
  68. char *str;
  69. size_t nmatch;
  70. regmatch_t pmatch[];
  71. int eflags;
  72. {
  73. register char *endp;
  74. register uint i;
  75. struct match mv;
  76. register struct match *m = &mv;
  77. register char *dp;
  78. register const sopno gf = g->firststate+1; /* +1 for OEND */
  79. register const sopno gl = g->laststate;
  80. char *start;
  81. char *stop;
  83. /* simplify the situation where possible */
  84. if (g->cflags&REG_NOSUB)
  85. nmatch = 0;
  86. if (eflags&REG_STARTEND) {
  87. start = str + pmatch[0].rm_so;
  88. stop = str + pmatch[0].rm_eo;
  89. } else {
  90. start = str;
  91. stop = start + strlen(start);
  92. }
  93. if (stop < start)
  94. return(REG_INVARG);
  96. /* prescreening; this does wonders for this rather slow code */
  97. if (g->must != NULL) {
  98. for (dp = start; dp < stop; dp++)
  99. if (*dp == g->must[0] && stop - dp >= g->mlen &&
  100. memcmp(dp, g->must, (size_t)g->mlen) == 0)
  101. break;
  102. if (dp == stop) /* we didn't find g->must */
  103. return(REG_NOMATCH);
  104. }
  106. /* match struct setup */
  107. m->g = g;
  108. m->eflags = eflags;
  109. m->pmatch = NULL;
  110. m->lastpos = NULL;
  111. m->offp = str;
  112. m->beginp = start;
  113. m->endp = stop;
  114. STATESETUP(m, 4);
  115. SETUP(m->st);
  116. SETUP(m->fresh);
  117. SETUP(m->tmp);
  118. SETUP(m->empty);
  119. CLEAR(m->empty);
  121. /* this loop does only one repetition except for backrefs */
  122. for (;;) {
  123. endp = fast(m, start, stop, gf, gl);
  124. if (endp == NULL) { /* a miss */
  125.   if (m->pmatch != NULL)
  126.     free((char *)m->pmatch);
  127.   if (m->lastpos != NULL)
  128.     free((char *)m->lastpos);
  129.   STATETEARDOWN(m);
  130.   return(REG_NOMATCH);
  131. }
  132. if (nmatch == 0 && !g->backrefs)
  133. break; /* no further info needed */
  135. /* where? */
  136. assert(m->coldp != NULL);
  137. for (;;) {
  138. NOTE("finding start");
  139. endp = slow(m, m->coldp, stop, gf, gl);
  140. if (endp != NULL)
  141. break;
  142. assert(m->coldp < m->endp);
  143. m->coldp++;
  144. }
  145. if (nmatch == 1 && !g->backrefs)
  146. break; /* no further info needed */
  148. /* oh my, he wants the subexpressions... */
  149. if (m->pmatch == NULL)
  150. m->pmatch = (regmatch_t *)malloc((m->g->nsub + 1) *
  151. sizeof(regmatch_t));
  152. if (m->pmatch == NULL) {
  153.    if (m->lastpos != NULL)
  154.      free((char *)m->lastpos);
  155. STATETEARDOWN(m);
  156. return(REG_ESPACE);
  157. }
  158. for (i = 1; i <= m->g->nsub; i++)
  159. m->pmatch[i].rm_so = m->pmatch[i].rm_eo = -1;
  160. if (!g->backrefs && !(m->eflags&REG_BACKR)) {
  161. NOTE("dissecting");
  162. dp = dissect(m, m->coldp, endp, gf, gl);
  163. } else {
  164. if (g->nplus > 0 && m->lastpos == NULL)
  165. m->lastpos = (char **)malloc((g->nplus+1) *
  166. sizeof(char *));
  167. if (g->nplus > 0 && m->lastpos == NULL) {
  168. free(m->pmatch);
  169. STATETEARDOWN(m);
  170. return(REG_ESPACE);
  171. }
  172. NOTE("backref dissect");
  173. dp = backref(m, m->coldp, endp, gf, gl, (sopno)0);
  174. }
  175. if (dp != NULL)
  176. break;
  178. /* uh-oh... we couldn't find a subexpression-level match */
  179. assert(g->backrefs); /* must be back references doing it */
  180. assert(g->nplus == 0 || m->lastpos != NULL);
  181. for (;;) {
  182. if (dp != NULL || endp <= m->coldp)
  183. break; /* defeat */
  184. NOTE("backoff");
  185. endp = slow(m, m->coldp, endp-1, gf, gl);
  186. if (endp == NULL)
  187. break; /* defeat */
  188. /* try it on a shorter possibility */
  189. #ifndef NDEBUG
  190. for (i = 1; i <= m->g->nsub; i++) {
  191. assert(m->pmatch[i].rm_so == -1);
  192. assert(m->pmatch[i].rm_eo == -1);
  193. }
  194. #endif
  195. NOTE("backoff dissect");
  196. dp = backref(m, m->coldp, endp, gf, gl, (sopno)0);
  197. }
  198. assert(dp == NULL || dp == endp);
  199. if (dp != NULL) /* found a shorter one */
  200. break;
  202. /* despite initial appearances, there is no match here */
  203. NOTE("false alarm");
  204. start = m->coldp + 1; /* recycle starting later */
  205. assert(start <= stop);
  206. }
  208. /* fill in the details if requested */
  209. if (nmatch > 0) {
  210. pmatch[0].rm_so = m->coldp - m->offp;
  211. pmatch[0].rm_eo = endp - m->offp;
  212. }
  213. if (nmatch > 1) {
  214. assert(m->pmatch != NULL);
  215. for (i = 1; i < nmatch; i++)
  216. if (i <= m->g->nsub)
  217. pmatch[i] = m->pmatch[i];
  218. else {
  219. pmatch[i].rm_so = -1;
  220. pmatch[i].rm_eo = -1;
  221. }
  222. }
  224. if (m->pmatch != NULL)
  225. free((char *)m->pmatch);
  226. if (m->lastpos != NULL)
  227. free((char *)m->lastpos);
  228. STATETEARDOWN(m);
  229. return(0);
  230. }
  232. /*
  233.  - dissect - figure out what matched what, no back references
  234.  == static char *dissect(register struct match *m, char *start, 
  235.  == char *stop, sopno startst, sopno stopst);
  236.  */
  237. static char * /* == stop (success) always */
  238. dissect(m, start, stop, startst, stopst)
  239. register struct match *m;
  240. char *start;
  241. char *stop;
  242. sopno startst;
  243. sopno stopst;
  244. {
  245. register uint i;
  246. register sopno ss; /* start sop of current subRE */
  247. register sopno es; /* end sop of current subRE */
  248. register char *sp; /* start of string matched by it */
  249. register char *stp; /* string matched by it cannot pass here */
  250. register char *rest; /* start of rest of string */
  251. register char *tail; /* string unmatched by rest of RE */
  252. register sopno ssub; /* start sop of subsubRE */
  253. register sopno esub; /* end sop of subsubRE */
  254. register char *ssp; /* start of string matched by subsubRE */
  255. register char *sep; /* end of string matched by subsubRE */
  256. register char *oldssp; /* previous ssp */
  257. register char *dp;
  259. AT("diss", start, stop, startst, stopst);
  260. sp = start;
  261. for (ss = startst; ss < stopst; ss = es) {
  262. /* identify end of subRE */
  263. es = ss;
  264. switch (OP(m->g->strip[es])) {
  265. case OPLUS_:
  266. case OQUEST_:
  267. es += OPND(m->g->strip[es]);
  268. break;
  269. case OCH_:
  270. while (OP(m->g->strip[es]) != O_CH)
  271. es += OPND(m->g->strip[es]);
  272. break;
  273. }
  274. es++;
  276. /* figure out what it matched */
  277. switch (OP(m->g->strip[ss])) {
  278. case OEND:
  279. assert(nope);
  280. break;
  281. case OCHAR:
  282. sp++;
  283. break;
  284. case OBOL:
  285. case OEOL:
  286. case OBOW:
  287. case OEOW:
  288. break;
  289. case OANY:
  290. case OANYOF:
  291. sp++;
  292. break;
  293. case OBACK_:
  294. case O_BACK:
  295. assert(nope);
  296. break;
  297. /* cases where length of match is hard to find */
  298. case OQUEST_:
  299. stp = stop;
  300. for (;;) {
  301. /* how long could this one be? */
  302. rest = slow(m, sp, stp, ss, es);
  303. assert(rest != NULL); /* it did match */
  304. /* could the rest match the rest? */
  305. tail = slow(m, rest, stop, es, stopst);
  306. if (tail == stop)
  307. break; /* yes! */
  308. /* no -- try a shorter match for this one */
  309. stp = rest - 1;
  310. assert(stp >= sp); /* it did work */
  311. }
  312. ssub = ss + 1;
  313. esub = es - 1;
  314. /* did innards match? */
  315. if (slow(m, sp, rest, ssub, esub) != NULL) {
  316. dp = dissect(m, sp, rest, ssub, esub);
  317. assert(dp == rest);
  318. } else /* no */
  319. assert(sp == rest);
  320. sp = rest;
  321. break;
  322. case OPLUS_:
  323. stp = stop;
  324. for (;;) {
  325. /* how long could this one be? */
  326. rest = slow(m, sp, stp, ss, es);
  327. assert(rest != NULL); /* it did match */
  328. /* could the rest match the rest? */
  329. tail = slow(m, rest, stop, es, stopst);
  330. if (tail == stop)
  331. break; /* yes! */
  332. /* no -- try a shorter match for this one */
  333. stp = rest - 1;
  334. assert(stp >= sp); /* it did work */
  335. }
  336. ssub = ss + 1;
  337. esub = es - 1;
  338. ssp = sp;
  339. oldssp = ssp;
  340. for (;;) { /* find last match of innards */
  341. sep = slow(m, ssp, rest, ssub, esub);
  342. if (sep == NULL || sep == ssp)
  343. break; /* failed or matched null */
  344. oldssp = ssp; /* on to next try */
  345. ssp = sep;
  346. }
  347. if (sep == NULL) {
  348. /* last successful match */
  349. sep = ssp;
  350. ssp = oldssp;
  351. }
  352. assert(sep == rest); /* must exhaust substring */
  353. assert(slow(m, ssp, sep, ssub, esub) == rest);
  354. dp = dissect(m, ssp, sep, ssub, esub);
  355. assert(dp == sep);
  356. sp = rest;
  357. break;
  358. case OCH_:
  359. stp = stop;
  360. for (;;) {
  361. /* how long could this one be? */
  362. rest = slow(m, sp, stp, ss, es);
  363. assert(rest != NULL); /* it did match */
  364. /* could the rest match the rest? */
  365. tail = slow(m, rest, stop, es, stopst);
  366. if (tail == stop)
  367. break; /* yes! */
  368. /* no -- try a shorter match for this one */
  369. stp = rest - 1;
  370. assert(stp >= sp); /* it did work */
  371. }
  372. ssub = ss + 1;
  373. esub = ss + OPND(m->g->strip[ss]) - 1;
  374. assert(OP(m->g->strip[esub]) == OOR1);
  375. for (;;) { /* find first matching branch */
  376. if (slow(m, sp, rest, ssub, esub) == rest)
  377. break; /* it matched all of it */
  378. /* that one missed, try next one */
  379. assert(OP(m->g->strip[esub]) == OOR1);
  380. esub++;
  381. assert(OP(m->g->strip[esub]) == OOR2);
  382. ssub = esub + 1;
  383. esub += OPND(m->g->strip[esub]);
  384. if (OP(m->g->strip[esub]) == OOR2)
  385. esub--;
  386. else
  387. assert(OP(m->g->strip[esub]) == O_CH);
  388. }
  389. dp = dissect(m, sp, rest, ssub, esub);
  390. assert(dp == rest);
  391. sp = rest;
  392. break;
  393. case O_PLUS:
  394. case O_QUEST:
  395. case OOR1:
  396. case OOR2:
  397. case O_CH:
  398. assert(nope);
  399. break;
  400. case OLPAREN:
  401. i = OPND(m->g->strip[ss]);
  402. assert(0 < i && i <= m->g->nsub);
  403. m->pmatch[i].rm_so = sp - m->offp;
  404. break;
  405. case ORPAREN:
  406. i = OPND(m->g->strip[ss]);
  407. assert(0 < i && i <= m->g->nsub);
  408. m->pmatch[i].rm_eo = sp - m->offp;
  409. break;
  410. default: /* uh oh */
  411. assert(nope);
  412. break;
  413. }
  414. }
  416. assert(sp == stop);
  417. return(sp);
  418. }
  420. /*
  421.  - backref - figure out what matched what, figuring in back references
  422.  == static char *backref(register struct match *m, char *start, 
  423.  == char *stop, sopno startst, sopno stopst, sopno lev);
  424.  */
  425. static char * /* == stop (success) or NULL (failure) */
  426. backref(m, start, stop, startst, stopst, lev)
  427. register struct match *m;
  428. char *start;
  429. char *stop;
  430. sopno startst;
  431. sopno stopst;
  432. sopno lev; /* PLUS nesting level */
  433. {
  434. register uint i;
  435. register sopno ss; /* start sop of current subRE */
  436. register char *sp; /* start of string matched by it */
  437. register sopno ssub; /* start sop of subsubRE */
  438. register sopno esub; /* end sop of subsubRE */
  439. register char *ssp; /* start of string matched by subsubRE */
  440. register char *dp;
  441. register size_t len;
  442. register int hard;
  443. register sop s;
  444. register regoff_t offsave;
  445. register cset *cs;
  447. AT("back", start, stop, startst, stopst);
  448. sp = start;
  450. /* get as far as we can with easy stuff */
  451. hard = 0;
  452. for (ss = startst; !hard && ss < stopst; ss++)
  453. switch (OP(s = m->g->strip[ss])) {
  454. case OCHAR:
  455. if (sp == stop || *sp++ != (char)OPND(s))
  456. return(NULL);
  457. break;
  458. case OANY:
  459. if (sp == stop)
  460. return(NULL);
  461. sp++;
  462. break;
  463. case OANYOF:
  464. cs = &m->g->sets[OPND(s)];
  465. if (sp == stop || !CHIN(cs, *sp++))
  466. return(NULL);
  467. break;
  468. case OBOL:
  469. if ( (sp == m->beginp && !(m->eflags&REG_NOTBOL)) ||
  470. (sp < m->endp && *(sp-1) == 'n' &&
  471. (m->g->cflags&REG_NEWLINE)) )
  472. { /* yes */ }
  473. else
  474. return(NULL);
  475. break;
  476. case OEOL:
  477. if ( (sp == m->endp && !(m->eflags&REG_NOTEOL)) ||
  478. (sp < m->endp && *sp == 'n' &&
  479. (m->g->cflags&REG_NEWLINE)) )
  480. { /* yes */ }
  481. else
  482. return(NULL);
  483. break;
  484. case OBOW:
  485. if (( (sp == m->beginp && !(m->eflags&REG_NOTBOL)) ||
  486. (sp < m->endp && *(sp-1) == 'n' &&
  487. (m->g->cflags&REG_NEWLINE)) ||
  488. (sp > m->beginp &&
  489. !ISWORD(*(sp-1))) ) &&
  490. (sp < m->endp && ISWORD(*sp)) )
  491. { /* yes */ }
  492. else
  493. return(NULL);
  494. break;
  495. case OEOW:
  496. if (( (sp == m->endp && !(m->eflags&REG_NOTEOL)) ||
  497. (sp < m->endp && *sp == 'n' &&
  498. (m->g->cflags&REG_NEWLINE)) ||
  499. (sp < m->endp && !ISWORD(*sp)) ) &&
  500. (sp > m->beginp && ISWORD(*(sp-1))) )
  501. { /* yes */ }
  502. else
  503. return(NULL);
  504. break;
  505. case O_QUEST:
  506. break;
  507. case OOR1: /* matches null but needs to skip */
  508. ss++;
  509. s = m->g->strip[ss];
  510. do {
  511. assert(OP(s) == OOR2);
  512. ss += OPND(s);
  513. } while (OP(s = m->g->strip[ss]) != O_CH);
  514. /* note that the ss++ gets us past the O_CH */
  515. break;
  516. default: /* have to make a choice */
  517. hard = 1;
  518. break;
  519. }
  520. if (!hard) { /* that was it! */
  521. if (sp != stop)
  522. return(NULL);
  523. return(sp);
  524. }
  525. ss--; /* adjust for the for's final increment */
  527. /* the hard stuff */
  528. AT("hard", sp, stop, ss, stopst);
  529. s = m->g->strip[ss];
  530. switch (OP(s)) {
  531. case OBACK_: /* the vilest depths */
  532. i = OPND(s);
  533. assert(0 < i && i <= m->g->nsub);
  534. if (m->pmatch[i].rm_eo == -1)
  535. return(NULL);
  536. assert(m->pmatch[i].rm_so != -1);
  537. len = m->pmatch[i].rm_eo - m->pmatch[i].rm_so;
  538. assert((size_t) (stop - m->beginp) >= len);
  539. if (sp > stop - len)
  540. return(NULL); /* not enough left to match */
  541. ssp = m->offp + m->pmatch[i].rm_so;
  542. if (memcmp(sp, ssp, len) != 0)
  543. return(NULL);
  544. while (m->g->strip[ss] != SOP(O_BACK, i))
  545. ss++;
  546. return(backref(m, sp+len, stop, ss+1, stopst, lev));
  547. break;
  548. case OQUEST_: /* to null or not */
  549. dp = backref(m, sp, stop, ss+1, stopst, lev);
  550. if (dp != NULL)
  551. return(dp); /* not */
  552. return(backref(m, sp, stop, ss+OPND(s)+1, stopst, lev));
  553. break;
  554. case OPLUS_:
  555. assert(m->lastpos != NULL);
  556. assert(lev+1 <= m->g->nplus);
  557. m->lastpos[lev+1] = sp;
  558. return(backref(m, sp, stop, ss+1, stopst, lev+1));
  559. break;
  560. case O_PLUS:
  561. if (sp == m->lastpos[lev]) /* last pass matched null */
  562. return(backref(m, sp, stop, ss+1, stopst, lev-1));
  563. /* try another pass */
  564. m->lastpos[lev] = sp;
  565. dp = backref(m, sp, stop, ss-OPND(s)+1, stopst, lev);
  566. if (dp == NULL)
  567. return(backref(m, sp, stop, ss+1, stopst, lev-1));
  568. else
  569. return(dp);
  570. break;
  571. case OCH_: /* find the right one, if any */
  572. ssub = ss + 1;
  573. esub = ss + OPND(s) - 1;
  574. assert(OP(m->g->strip[esub]) == OOR1);
  575. for (;;) { /* find first matching branch */
  576. dp = backref(m, sp, stop, ssub, esub, lev);
  577. if (dp != NULL)
  578. return(dp);
  579. /* that one missed, try next one */
  580. if (OP(m->g->strip[esub]) == O_CH)
  581. return(NULL); /* there is none */
  582. esub++;
  583. assert(OP(m->g->strip[esub]) == OOR2);
  584. ssub = esub + 1;
  585. esub += OPND(m->g->strip[esub]);
  586. if (OP(m->g->strip[esub]) == OOR2)
  587. esub--;
  588. else
  589. assert(OP(m->g->strip[esub]) == O_CH);
  590. }
  591. break;
  592. case OLPAREN: /* must undo assignment if rest fails */
  593. i = OPND(s);
  594. assert(0 < i && i <= m->g->nsub);
  595. offsave = m->pmatch[i].rm_so;
  596. m->pmatch[i].rm_so = sp - m->offp;
  597. dp = backref(m, sp, stop, ss+1, stopst, lev);
  598. if (dp != NULL)
  599. return(dp);
  600. m->pmatch[i].rm_so = offsave;
  601. return(NULL);
  602. break;
  603. case ORPAREN: /* must undo assignment if rest fails */
  604. i = OPND(s);
  605. assert(0 < i && i <= m->g->nsub);
  606. offsave = m->pmatch[i].rm_eo;
  607. m->pmatch[i].rm_eo = sp - m->offp;
  608. dp = backref(m, sp, stop, ss+1, stopst, lev);
  609. if (dp != NULL)
  610. return(dp);
  611. m->pmatch[i].rm_eo = offsave;
  612. return(NULL);
  613. break;
  614. default: /* uh oh */
  615. assert(nope);
  616. break;
  617. }
  619. /* "can't happen" */
  620. assert(nope);
  621. /* NOTREACHED */
  622. return 0; /* Keep gcc happy */
  623. }
  625. /*
  626.  - fast - step through the string at top speed
  627.  == static char *fast(register struct match *m, char *start, 
  628.  == char *stop, sopno startst, sopno stopst);
  629.  */
  630. static char * /* where tentative match ended, or NULL */
  631. fast(m, start, stop, startst, stopst)
  632. register struct match *m;
  633. char *start;
  634. char *stop;
  635. sopno startst;
  636. sopno stopst;
  637. {
  638. register states st = m->st;
  639. register states fresh = m->fresh;
  640. register states tmp = m->tmp;
  641. register char *p = start;
  642. register int c = (start == m->beginp) ? OUT : *(start-1);
  643. register int lastc; /* previous c */
  644. register int flagch;
  645. register int i;
  646. register char *coldp; /* last p after which no match was underway */
  648. CLEAR(st);
  649. SET1(st, startst);
  650. st = step(m->g, startst, stopst, st, NOTHING, st);
  651. ASSIGN(fresh, st);
  652. SP("start", st, *p);
  653. coldp = NULL;
  654. for (;;) {
  655. /* next character */
  656. lastc = c;
  657. c = (p == m->endp) ? OUT : *p;
  658. if (EQ(st, fresh))
  659. coldp = p;
  661. /* is there an EOL and/or BOL between lastc and c? */
  662. flagch = '';
  663. i = 0;
  664. if ( (lastc == 'n' && m->g->cflags&REG_NEWLINE) ||
  665. (lastc == OUT && !(m->eflags&REG_NOTBOL)) ) {
  666. flagch = BOL;
  667. i = m->g->nbol;
  668. }
  669. if ( (c == 'n' && m->g->cflags&REG_NEWLINE) ||
  670. (c == OUT && !(m->eflags&REG_NOTEOL)) ) {
  671. flagch = (flagch == BOL) ? BOLEOL : EOL;
  672. i += m->g->neol;
  673. }
  674. if (i != 0) {
  675. for (; i > 0; i--)
  676. st = step(m->g, startst, stopst, st, flagch, st);
  677. SP("boleol", st, c);
  678. }
  680. /* how about a word boundary? */
  681. if ( (flagch == BOL || (lastc != OUT && !ISWORD(lastc))) &&
  682. (c != OUT && ISWORD(c)) ) {
  683. flagch = BOW;
  684. }
  685. if ( (lastc != OUT && ISWORD(lastc)) &&
  686. (flagch == EOL || (c != OUT && !ISWORD(c))) ) {
  687. flagch = EOW;
  688. }
  689. if (flagch == BOW || flagch == EOW) {
  690. st = step(m->g, startst, stopst, st, flagch, st);
  691. SP("boweow", st, c);
  692. }
  694. /* are we done? */
  695. if (ISSET(st, stopst) || p == stop)
  696. break; /* NOTE BREAK OUT */
  698. /* no, we must deal with this character */
  699. ASSIGN(tmp, st);
  700. ASSIGN(st, fresh);
  701. assert(c != OUT);
  702. st = step(m->g, startst, stopst, tmp, c, st);
  703. SP("aft", st, c);
  704. assert(EQ(step(m->g, startst, stopst, st, NOTHING, st), st));
  705. p++;
  706. }
  708. assert(coldp != NULL);
  709. m->coldp = coldp;
  710. if (ISSET(st, stopst))
  711. return(p+1);
  712. else
  713. return(NULL);
  714. }
  716. /*
  717.  - slow - step through the string more deliberately
  718.  == static char *slow(register struct match *m, char *start, 
  719.  == char *stop, sopno startst, sopno stopst);
  720.  */
  721. static char * /* where it ended */
  722. slow(m, start, stop, startst, stopst)
  723. register struct match *m;
  724. char *start;
  725. char *stop;
  726. sopno startst;
  727. sopno stopst;
  728. {
  729. register states st = m->st;
  730. register states empty = m->empty;
  731. register states tmp = m->tmp;
  732. register char *p = start;
  733. register int c = (start == m->beginp) ? OUT : *(start-1);
  734. register int lastc; /* previous c */
  735. register int flagch;
  736. register int i;
  737. register char *matchp; /* last p at which a match ended */
  739. AT("slow", start, stop, startst, stopst);
  740. CLEAR(st);
  741. SET1(st, startst);
  742. SP("sstart", st, *p);
  743. st = step(m->g, startst, stopst, st, NOTHING, st);
  744. matchp = NULL;
  745. for (;;) {
  746. /* next character */
  747. lastc = c;
  748. c = (p == m->endp) ? OUT : *p;
  750. /* is there an EOL and/or BOL between lastc and c? */
  751. flagch = '';
  752. i = 0;
  753. if ( (lastc == 'n' && m->g->cflags&REG_NEWLINE) ||
  754. (lastc == OUT && !(m->eflags&REG_NOTBOL)) ) {
  755. flagch = BOL;
  756. i = m->g->nbol;
  757. }
  758. if ( (c == 'n' && m->g->cflags&REG_NEWLINE) ||
  759. (c == OUT && !(m->eflags&REG_NOTEOL)) ) {
  760. flagch = (flagch == BOL) ? BOLEOL : EOL;
  761. i += m->g->neol;
  762. }
  763. if (i != 0) {
  764. for (; i > 0; i--)
  765. st = step(m->g, startst, stopst, st, flagch, st);
  766. SP("sboleol", st, c);
  767. }
  769. /* how about a word boundary? */
  770. if ( (flagch == BOL || (lastc != OUT && !ISWORD(lastc))) &&
  771. (c != OUT && ISWORD(c)) ) {
  772. flagch = BOW;
  773. }
  774. if ( (lastc != OUT && ISWORD(lastc)) &&
  775. (flagch == EOL || (c != OUT && !ISWORD(c))) ) {
  776. flagch = EOW;
  777. }
  778. if (flagch == BOW || flagch == EOW) {
  779. st = step(m->g, startst, stopst, st, flagch, st);
  780. SP("sboweow", st, c);
  781. }
  783. /* are we done? */
  784. if (ISSET(st, stopst))
  785. matchp = p;
  786. if (EQ(st, empty) || p == stop)
  787. break; /* NOTE BREAK OUT */
  789. /* no, we must deal with this character */
  790. ASSIGN(tmp, st);
  791. ASSIGN(st, empty);
  792. assert(c != OUT);
  793. st = step(m->g, startst, stopst, tmp, c, st);
  794. SP("saft", st, c);
  795. assert(EQ(step(m->g, startst, stopst, st, NOTHING, st), st));
  796. p++;
  797. }
  799. return(matchp);
  800. }
  803. /*
  804.  - step - map set of states reachable before char to set reachable after
  805.  == static states step(register struct re_guts *g, sopno start, sopno stop, 
  806.  == register states bef, int ch, register states aft);
  807.  == #define BOL (OUT+1)
  808.  == #define EOL (BOL+1)
  809.  == #define BOLEOL (BOL+2)
  810.  == #define NOTHING (BOL+3)
  811.  == #define BOW (BOL+4)
  812.  == #define EOW (BOL+5)
  813.  == #define CODEMAX (BOL+5) // highest code used
  814.  == #define NONCHAR(c) ((c) > CHAR_MAX)
  815.  == #define NNONCHAR (CODEMAX-CHAR_MAX)
  816.  */
  817. static states
  818. step(g, start, stop, bef, ch, aft)
  819. register struct re_guts *g;
  820. sopno start; /* start state within strip */
  821. sopno stop; /* state after stop state within strip */
  822. register states bef; /* states reachable before */
  823. int ch; /* character or NONCHAR code */
  824. register states aft; /* states already known reachable after */
  825. {
  826. register cset *cs;
  827. register sop s;
  828. register sopno pc;
  829. register onestate here; /* note, macros know this name */
  830. register sopno look;
  831. register int i;
  833. for (pc = start, INIT(here, pc); pc != stop; pc++, INC(here)) {
  834. s = g->strip[pc];
  835. switch (OP(s)) {
  836. case OEND:
  837. assert(pc == stop-1);
  838. break;
  839. case OCHAR:
  840. /* only characters can match */
  841. assert(!NONCHAR(ch) || ch != (char)OPND(s));
  842. if (ch == (char)OPND(s))
  843. FWD(aft, bef, 1);
  844. break;
  845. case OBOL:
  846. if (ch == BOL || ch == BOLEOL)
  847. FWD(aft, bef, 1);
  848. break;
  849. case OEOL:
  850. if (ch == EOL || ch == BOLEOL)
  851. FWD(aft, bef, 1);
  852. break;
  853. case OBOW:
  854. if (ch == BOW)
  855. FWD(aft, bef, 1);
  856. break;
  857. case OEOW:
  858. if (ch == EOW)
  859. FWD(aft, bef, 1);
  860. break;
  861. case OANY:
  862. if (!NONCHAR(ch))
  863. FWD(aft, bef, 1);
  864. break;
  865. case OANYOF:
  866. cs = &g->sets[OPND(s)];
  867. if (!NONCHAR(ch) && CHIN(cs, ch))
  868. FWD(aft, bef, 1);
  869. break;
  870. case OBACK_: /* ignored here */
  871. case O_BACK:
  872. FWD(aft, aft, 1);
  873. break;
  874. case OPLUS_: /* forward, this is just an empty */
  875. FWD(aft, aft, 1);
  876. break;
  877. case O_PLUS: /* both forward and back */
  878. FWD(aft, aft, 1);
  879. i = ISSETBACK(aft, OPND(s));
  880. BACK(aft, aft, OPND(s));
  881. if (!i && ISSETBACK(aft, OPND(s))) {
  882. /* oho, must reconsider loop body */
  883. pc -= OPND(s) + 1;
  884. INIT(here, pc);
  885. }
  886. break;
  887. case OQUEST_: /* two branches, both forward */
  888. FWD(aft, aft, 1);
  889. FWD(aft, aft, OPND(s));
  890. break;
  891. case O_QUEST: /* just an empty */
  892. FWD(aft, aft, 1);
  893. break;
  894. case OLPAREN: /* not significant here */
  895. case ORPAREN:
  896. FWD(aft, aft, 1);
  897. break;
  898. case OCH_: /* mark the first two branches */
  899. FWD(aft, aft, 1);
  900. assert(OP(g->strip[pc+OPND(s)]) == OOR2);
  901. FWD(aft, aft, OPND(s));
  902. break;
  903. case OOR1: /* done a branch, find the O_CH */
  904. if (ISSTATEIN(aft, here)) {
  905. for (look = 1;
  906. OP(s = g->strip[pc+look]) != O_CH;
  907. look += OPND(s))
  908. assert(OP(s) == OOR2);
  909. FWD(aft, aft, look);
  910. }
  911. break;
  912. case OOR2: /* propagate OCH_'s marking */
  913. FWD(aft, aft, 1);
  914. if (OP(g->strip[pc+OPND(s)]) != O_CH) {
  915. assert(OP(g->strip[pc+OPND(s)]) == OOR2);
  916. FWD(aft, aft, OPND(s));
  917. }
  918. break;
  919. case O_CH: /* just empty */
  920. FWD(aft, aft, 1);
  921. break;
  922. default: /* ooooops... */
  923. assert(nope);
  924. break;
  925. }
  926. }
  928. return(aft);
  929. }
  931. #ifdef REDEBUG
  932. /*
  933.  - print - print a set of states
  934.  == #ifdef REDEBUG
  935.  == static void print(struct match *m, char *caption, states st, 
  936.  == int ch, FILE *d);
  937.  == #endif
  938.  */
  939. static void
  940. print(m, caption, st, ch, d)
  941. struct match *m;
  942. char *caption;
  943. states st;
  944. int ch;
  945. FILE *d;
  946. {
  947. register struct re_guts *g = m->g;
  948. register int i;
  949. register int first = 1;
  950. char buf[10];
  952. if (!(m->eflags&REG_TRACE))
  953. return;
  955. fprintf(d, "%s", caption);
  956. if (ch != '')
  957. fprintf(d, " %s", printchar(ch,buf));
  958. for (i = 0; i < g->nstates; i++)
  959. if (ISSET(st, i)) {
  960. fprintf(d, "%s%d", (first) ? "t" : ", ", i);
  961. first = 0;
  962. }
  963. fprintf(d, "n");
  964. }
  966. /*
  967.  - at - print current situation
  968.  == #ifdef REDEBUG
  969.  == static void at(struct match *m, char *title, char *start, char *stop, 
  970.  == sopno startst, sopno stopst);
  971.  == #endif
  972.  */
  973. static void
  974. at(m, title, start, stop, startst, stopst)
  975. struct match *m;
  976. char *title;
  977. char *start;
  978. char *stop;
  979. sopno startst;
  980. sopno stopst;
  981. {
  982. char buf[10];
  983. if (!(m->eflags&REG_TRACE))
  984. return;
  986. printf("%s %s-", title, printchar(*start,buf));
  987. printf("%s ", printchar(*stop,buf));
  988. printf("%ld-%ldn", (long)startst, (long)stopst,buf);
  989. }
  991. #ifndef PCHARDONE
  992. #define PCHARDONE /* never again */
  993. /*
  994.  - printchar - make a character printable
  995.  == #ifdef REDEBUG
  996.  == static char *printchar(int ch);
  997.  == #endif
  998.  *
  999.  * Is this identical to regchar() over in debug.c?  Well, yes.  But a
  1000.  * duplicate here avoids having a debugging-capable regexec.o tied to
  1001.  * a matching debug.o, and this is convenient.  It all disappears in
  1002.  * the non-debug compilation anyway, so it doesn't matter much.
  1003.  */
  1004. static char * /* -> representation */
  1005. printchar(ch,pbuf)
  1006. int ch;
  1007. char *pbuf;
  1008. {
  1009. if (isprint(ch) || ch == ' ')
  1010. sprintf(pbuf, "%c", ch);
  1011. else
  1012. sprintf(pbuf, "\%o", ch);
  1013. return(pbuf);
  1014. }
  1015. #endif
  1016. #endif
  1018. #undef matcher
  1019. #undef fast
  1020. #undef slow
  1021. #undef dissect
  1022. #undef backref
  1023. #undef step
  1024. #undef print
  1025. #undef at
  1026. #undef match