engine.c
上传用户:romrleung
上传日期:2022-05-23
资源大小:18897k
文件大小:26k
源码类别:

MySQL数据库

开发平台:

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