regexp.c 27 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <string.h>
  4. #include <setjmp.h>
  5. #include <limits.h>
  6. #include "regexp.h"
  7. #include "utf.h"
  8. #define emit regemit
  9. #define next regnext
  10. #define accept regaccept
  11. #define nelem(a) (int)(sizeof (a) / sizeof (a)[0])
  12. #define REPINF 255
  13. #ifndef REG_MAXPROG
  14. #define REG_MAXPROG (32 << 10)
  15. #endif
  16. #ifndef REG_MAXREC
  17. #define REG_MAXREC 4096
  18. #endif
  19. #ifndef REG_MAXSPAN
  20. #define REG_MAXSPAN 64
  21. #endif
  22. #ifndef REG_MAXCLASS
  23. #define REG_MAXCLASS 128
  24. #endif
  25. /* Max number of instructions to run if REG_RUNAWAY is set. */
  26. #ifndef REG_MAXRUN
  27. #define REG_MAXRUN (1<<20)
  28. #endif
  29. typedef struct Reclass Reclass;
  30. typedef struct Renode Renode;
  31. typedef struct Reinst Reinst;
  32. typedef struct Rethread Rethread;
  33. struct Reclass {
  34. Rune *end;
  35. Rune spans[REG_MAXSPAN];
  36. };
  37. struct Reprog {
  38. Reinst *start, *end;
  39. Reclass *cclass;
  40. int flags;
  41. int nsub;
  42. };
  43. struct cstate {
  44. jmp_buf kaboom;
  45. Reprog *prog;
  46. Renode *pstart, *pend;
  47. const char *source;
  48. int ncclass;
  49. int nsub;
  50. Renode *sub[REG_MAXSUB];
  51. int lookahead;
  52. Rune yychar;
  53. Reclass *yycc;
  54. int yymin, yymax;
  55. const char *error;
  56. Reclass cclass[REG_MAXCLASS];
  57. };
  58. static void die(struct cstate *g, const char *message)
  59. {
  60. g->error = message;
  61. longjmp(g->kaboom, 1);
  62. }
  63. static int canon(Rune c)
  64. {
  65. Rune u = toupperrune(c);
  66. if (c >= 128 && u < 128)
  67. return c;
  68. return u;
  69. }
  70. /* Scan */
  71. enum {
  72. L_CHAR = 256,
  73. L_CCLASS, /* character class */
  74. L_NCCLASS, /* negative character class */
  75. L_NC, /* "(?:" no capture */
  76. L_PLA, /* "(?=" positive lookahead */
  77. L_NLA, /* "(?!" negative lookahead */
  78. L_WORD, /* "\b" word boundary */
  79. L_NWORD, /* "\B" non-word boundary */
  80. L_REF, /* "\1" back-reference */
  81. L_COUNT, /* {M,N} */
  82. };
  83. static int hex(struct cstate *g, int c)
  84. {
  85. if (c >= '0' && c <= '9') return c - '0';
  86. if (c >= 'a' && c <= 'f') return c - 'a' + 0xA;
  87. if (c >= 'A' && c <= 'F') return c - 'A' + 0xA;
  88. die(g, "invalid escape sequence");
  89. return 0;
  90. }
  91. static int dec(struct cstate *g, int c)
  92. {
  93. if (c >= '0' && c <= '9') return c - '0';
  94. die(g, "invalid quantifier");
  95. return 0;
  96. }
  97. #define ESCAPES "BbDdSsWw^$\\.*+?()[]{}|-0123456789"
  98. static int nextrune(struct cstate *g)
  99. {
  100. if (!*g->source) {
  101. g->yychar = EOF;
  102. return 0;
  103. }
  104. g->source += chartorune(&g->yychar, g->source);
  105. if (g->yychar == '\\') {
  106. if (!*g->source)
  107. die(g, "unterminated escape sequence");
  108. g->source += chartorune(&g->yychar, g->source);
  109. switch (g->yychar) {
  110. case 'f': g->yychar = '\f'; return 0;
  111. case 'n': g->yychar = '\n'; return 0;
  112. case 'r': g->yychar = '\r'; return 0;
  113. case 't': g->yychar = '\t'; return 0;
  114. case 'v': g->yychar = '\v'; return 0;
  115. case 'c':
  116. if (!g->source[0])
  117. die(g, "unterminated escape sequence");
  118. g->yychar = (*g->source++) & 31;
  119. return 0;
  120. case 'x':
  121. if (!g->source[0] || !g->source[1])
  122. die(g, "unterminated escape sequence");
  123. g->yychar = hex(g, *g->source++) << 4;
  124. g->yychar += hex(g, *g->source++);
  125. if (g->yychar == 0) {
  126. g->yychar = '0';
  127. return 1;
  128. }
  129. return 1;
  130. case 'u':
  131. if (!g->source[0] || !g->source[1] || !g->source[2] || !g->source[3])
  132. die(g, "unterminated escape sequence");
  133. g->yychar = hex(g, *g->source++) << 12;
  134. g->yychar += hex(g, *g->source++) << 8;
  135. g->yychar += hex(g, *g->source++) << 4;
  136. g->yychar += hex(g, *g->source++);
  137. if (g->yychar == 0) {
  138. g->yychar = '0';
  139. return 1;
  140. }
  141. return 1;
  142. case 0:
  143. g->yychar = '0';
  144. return 1;
  145. }
  146. if (strchr(ESCAPES, g->yychar))
  147. return 1;
  148. /* Annex B identity escape: \a, \_, ... match the character
  149. * itself, as browsers do for non-unicode regular expressions. */
  150. return 0;
  151. }
  152. return 0;
  153. }
  154. /* Annex B: a '{' that does not start a well-formed quantifier is a literal
  155. * brace, so /{}/ and /{,x}/ are valid patterns. */
  156. static int iscount(struct cstate *g)
  157. {
  158. const char *s = g->source;
  159. if (*s < '0' || *s > '9')
  160. return 0;
  161. while (*s >= '0' && *s <= '9')
  162. s++;
  163. if (*s == '}')
  164. return 1;
  165. if (*s != ',')
  166. return 0;
  167. s++;
  168. if (*s == '}')
  169. return 1;
  170. if (*s < '0' || *s > '9')
  171. return 0;
  172. while (*s >= '0' && *s <= '9')
  173. s++;
  174. return *s == '}';
  175. }
  176. static int lexcount(struct cstate *g)
  177. {
  178. g->yychar = *g->source++;
  179. g->yymin = dec(g, g->yychar);
  180. g->yychar = *g->source++;
  181. while (g->yychar != ',' && g->yychar != '}') {
  182. g->yymin = g->yymin * 10 + dec(g, g->yychar);
  183. g->yychar = *g->source++;
  184. if (g->yymin >= REPINF)
  185. die(g, "numeric overflow");
  186. }
  187. if (g->yychar == ',') {
  188. g->yychar = *g->source++;
  189. if (g->yychar == '}') {
  190. g->yymax = REPINF;
  191. } else {
  192. g->yymax = dec(g, g->yychar);
  193. g->yychar = *g->source++;
  194. while (g->yychar != '}') {
  195. g->yymax = g->yymax * 10 + dec(g, g->yychar);
  196. g->yychar = *g->source++;
  197. if (g->yymax >= REPINF)
  198. die(g, "numeric overflow");
  199. }
  200. }
  201. } else {
  202. g->yymax = g->yymin;
  203. }
  204. return L_COUNT;
  205. }
  206. static void newcclass(struct cstate *g)
  207. {
  208. if (g->ncclass >= REG_MAXCLASS)
  209. die(g, "too many character classes");
  210. g->yycc = g->cclass + g->ncclass++;
  211. g->yycc->end = g->yycc->spans;
  212. }
  213. static void addrange(struct cstate *g, Rune a, Rune b)
  214. {
  215. Reclass *cc = g->yycc;
  216. Rune *p;
  217. if (a > b)
  218. die(g, "invalid character class range");
  219. /* extend existing ranges if they overlap */
  220. for (p = cc->spans; p < cc->end; p += 2) {
  221. /* completely inside old range */
  222. if (a >= p[0] && b <= p[1])
  223. return;
  224. /* completely swallows old range */
  225. if (a < p[0] && b >= p[1]) {
  226. p[0] = a;
  227. p[1] = b;
  228. return;
  229. }
  230. /* extend at start */
  231. if (b >= p[0] - 1 && b <= p[1] && a < p[0]) {
  232. p[0] = a;
  233. return;
  234. }
  235. /* extend at end */
  236. if (a >= p[0] && a <= p[1] + 1 && b > p[1]) {
  237. p[1] = b;
  238. return;
  239. }
  240. }
  241. if (cc->end + 2 >= cc->spans + nelem(cc->spans))
  242. die(g, "too many character class ranges");
  243. *cc->end++ = a;
  244. *cc->end++ = b;
  245. }
  246. static void addranges_d(struct cstate *g)
  247. {
  248. addrange(g, '0', '9');
  249. }
  250. static void addranges_D(struct cstate *g)
  251. {
  252. addrange(g, 0, '0'-1);
  253. addrange(g, '9'+1, 0xFFFF);
  254. }
  255. static void addranges_s(struct cstate *g)
  256. {
  257. addrange(g, 0x9, 0xD);
  258. addrange(g, 0x20, 0x20);
  259. addrange(g, 0xA0, 0xA0);
  260. addrange(g, 0x2028, 0x2029);
  261. addrange(g, 0xFEFF, 0xFEFF);
  262. }
  263. static void addranges_S(struct cstate *g)
  264. {
  265. addrange(g, 0, 0x9-1);
  266. addrange(g, 0xD+1, 0x20-1);
  267. addrange(g, 0x20+1, 0xA0-1);
  268. addrange(g, 0xA0+1, 0x2028-1);
  269. addrange(g, 0x2029+1, 0xFEFF-1);
  270. addrange(g, 0xFEFF+1, 0xFFFF);
  271. }
  272. static void addranges_w(struct cstate *g)
  273. {
  274. addrange(g, '0', '9');
  275. addrange(g, 'A', 'Z');
  276. addrange(g, '_', '_');
  277. addrange(g, 'a', 'z');
  278. }
  279. static void addranges_W(struct cstate *g)
  280. {
  281. addrange(g, 0, '0'-1);
  282. addrange(g, '9'+1, 'A'-1);
  283. addrange(g, 'Z'+1, '_'-1);
  284. addrange(g, '_'+1, 'a'-1);
  285. addrange(g, 'z'+1, 0xFFFF);
  286. }
  287. static int lexclass(struct cstate *g)
  288. {
  289. int type = L_CCLASS;
  290. int quoted, havesave, havedash;
  291. Rune save = 0;
  292. newcclass(g);
  293. quoted = nextrune(g);
  294. if (!quoted && g->yychar == '^') {
  295. type = L_NCCLASS;
  296. quoted = nextrune(g);
  297. }
  298. havesave = havedash = 0;
  299. for (;;) {
  300. if (g->yychar == EOF)
  301. die(g, "unterminated character class");
  302. if (!quoted && g->yychar == ']')
  303. break;
  304. if (!quoted && g->yychar == '-') {
  305. if (havesave) {
  306. if (havedash) {
  307. addrange(g, save, '-');
  308. havesave = havedash = 0;
  309. } else {
  310. havedash = 1;
  311. }
  312. } else {
  313. save = '-';
  314. havesave = 1;
  315. }
  316. } else if (quoted && strchr("DSWdsw", g->yychar)) {
  317. if (havesave) {
  318. addrange(g, save, save);
  319. if (havedash)
  320. addrange(g, '-', '-');
  321. }
  322. switch (g->yychar) {
  323. case 'd': addranges_d(g); break;
  324. case 's': addranges_s(g); break;
  325. case 'w': addranges_w(g); break;
  326. case 'D': addranges_D(g); break;
  327. case 'S': addranges_S(g); break;
  328. case 'W': addranges_W(g); break;
  329. }
  330. havesave = havedash = 0;
  331. } else {
  332. if (quoted) {
  333. if (g->yychar == 'b')
  334. g->yychar = '\b';
  335. else if (g->yychar == '0')
  336. g->yychar = 0;
  337. /* else identity escape */
  338. }
  339. if (havesave) {
  340. if (havedash) {
  341. addrange(g, save, g->yychar);
  342. havesave = havedash = 0;
  343. } else {
  344. addrange(g, save, save);
  345. save = g->yychar;
  346. }
  347. } else {
  348. save = g->yychar;
  349. havesave = 1;
  350. }
  351. }
  352. quoted = nextrune(g);
  353. }
  354. if (havesave) {
  355. addrange(g, save, save);
  356. if (havedash)
  357. addrange(g, '-', '-');
  358. }
  359. return type;
  360. }
  361. static int lex(struct cstate *g)
  362. {
  363. int quoted = nextrune(g);
  364. if (quoted) {
  365. switch (g->yychar) {
  366. case 'b': return L_WORD;
  367. case 'B': return L_NWORD;
  368. case 'd': newcclass(g); addranges_d(g); return L_CCLASS;
  369. case 's': newcclass(g); addranges_s(g); return L_CCLASS;
  370. case 'w': newcclass(g); addranges_w(g); return L_CCLASS;
  371. case 'D': newcclass(g); addranges_d(g); return L_NCCLASS;
  372. case 'S': newcclass(g); addranges_s(g); return L_NCCLASS;
  373. case 'W': newcclass(g); addranges_w(g); return L_NCCLASS;
  374. case '0': g->yychar = 0; return L_CHAR;
  375. }
  376. if (g->yychar >= '0' && g->yychar <= '9') {
  377. g->yychar -= '0';
  378. if (*g->source >= '0' && *g->source <= '9')
  379. g->yychar = g->yychar * 10 + *g->source++ - '0';
  380. return L_REF;
  381. }
  382. return L_CHAR;
  383. }
  384. switch (g->yychar) {
  385. case EOF:
  386. case '$': case ')': case '*': case '+':
  387. case '.': case '?': case '^': case '|':
  388. return g->yychar;
  389. }
  390. if (g->yychar == '{') {
  391. if (iscount(g))
  392. return lexcount(g);
  393. return L_CHAR;
  394. }
  395. if (g->yychar == '[')
  396. return lexclass(g);
  397. if (g->yychar == '(') {
  398. if (g->source[0] == '?') {
  399. if (g->source[1] == ':') {
  400. g->source += 2;
  401. return L_NC;
  402. }
  403. if (g->source[1] == '=') {
  404. g->source += 2;
  405. return L_PLA;
  406. }
  407. if (g->source[1] == '!') {
  408. g->source += 2;
  409. return L_NLA;
  410. }
  411. }
  412. return '(';
  413. }
  414. return L_CHAR;
  415. }
  416. /* Parse */
  417. enum {
  418. P_CAT, P_ALT, P_REP,
  419. P_BOL, P_EOL, P_WORD, P_NWORD,
  420. P_PAR, P_PLA, P_NLA,
  421. P_ANY, P_CHAR, P_CCLASS, P_NCCLASS,
  422. P_REF,
  423. };
  424. struct Renode {
  425. unsigned char type;
  426. unsigned char ng, m, n;
  427. Rune c;
  428. int cc;
  429. Renode *x;
  430. Renode *y;
  431. };
  432. static Renode *newnode(struct cstate *g, int type)
  433. {
  434. Renode *node = g->pend++;
  435. node->type = type;
  436. node->cc = -1;
  437. node->c = 0;
  438. node->ng = 0;
  439. node->m = 0;
  440. node->n = 0;
  441. node->x = node->y = NULL;
  442. return node;
  443. }
  444. static int empty(Renode *node)
  445. {
  446. if (!node) return 1;
  447. switch (node->type) {
  448. default: return 1;
  449. case P_CAT: return empty(node->x) && empty(node->y);
  450. case P_ALT: return empty(node->x) || empty(node->y);
  451. case P_REP: return empty(node->x) || node->m == 0;
  452. case P_PAR: return empty(node->x);
  453. case P_REF: return empty(node->x);
  454. case P_ANY: case P_CHAR: case P_CCLASS: case P_NCCLASS: return 0;
  455. }
  456. }
  457. static Renode *newrep(struct cstate *g, Renode *atom, int ng, int min, int max)
  458. {
  459. Renode *rep = newnode(g, P_REP);
  460. if (max == REPINF && empty(atom))
  461. die(g, "infinite loop matching the empty string");
  462. rep->ng = ng;
  463. rep->m = min;
  464. rep->n = max;
  465. rep->x = atom;
  466. return rep;
  467. }
  468. static void next(struct cstate *g)
  469. {
  470. g->lookahead = lex(g);
  471. }
  472. static int accept(struct cstate *g, int t)
  473. {
  474. if (g->lookahead == t) {
  475. next(g);
  476. return 1;
  477. }
  478. return 0;
  479. }
  480. static Renode *parsealt(struct cstate *g);
  481. static Renode *parseatom(struct cstate *g)
  482. {
  483. Renode *atom;
  484. if (g->lookahead == L_CHAR) {
  485. atom = newnode(g, P_CHAR);
  486. atom->c = g->yychar;
  487. next(g);
  488. return atom;
  489. }
  490. if (g->lookahead == L_CCLASS) {
  491. atom = newnode(g, P_CCLASS);
  492. atom->cc = g->yycc - g->cclass;
  493. next(g);
  494. return atom;
  495. }
  496. if (g->lookahead == L_NCCLASS) {
  497. atom = newnode(g, P_NCCLASS);
  498. atom->cc = g->yycc - g->cclass;
  499. next(g);
  500. return atom;
  501. }
  502. if (g->lookahead == L_REF) {
  503. atom = newnode(g, P_REF);
  504. if (g->yychar == 0 || g->yychar >= g->nsub || !g->sub[g->yychar])
  505. die(g, "invalid back-reference");
  506. atom->n = g->yychar;
  507. atom->x = g->sub[g->yychar];
  508. next(g);
  509. return atom;
  510. }
  511. if (accept(g, '.'))
  512. return newnode(g, P_ANY);
  513. if (accept(g, '(')) {
  514. atom = newnode(g, P_PAR);
  515. if (g->nsub == REG_MAXSUB)
  516. die(g, "too many captures");
  517. atom->n = g->nsub++;
  518. atom->x = parsealt(g);
  519. g->sub[atom->n] = atom;
  520. if (!accept(g, ')'))
  521. die(g, "unmatched '('");
  522. return atom;
  523. }
  524. if (accept(g, L_NC)) {
  525. atom = parsealt(g);
  526. if (!accept(g, ')'))
  527. die(g, "unmatched '('");
  528. return atom;
  529. }
  530. if (accept(g, L_PLA)) {
  531. atom = newnode(g, P_PLA);
  532. atom->x = parsealt(g);
  533. if (!accept(g, ')'))
  534. die(g, "unmatched '('");
  535. return atom;
  536. }
  537. if (accept(g, L_NLA)) {
  538. atom = newnode(g, P_NLA);
  539. atom->x = parsealt(g);
  540. if (!accept(g, ')'))
  541. die(g, "unmatched '('");
  542. return atom;
  543. }
  544. die(g, "syntax error");
  545. return NULL;
  546. }
  547. static Renode *parserep(struct cstate *g)
  548. {
  549. Renode *atom;
  550. if (accept(g, '^')) return newnode(g, P_BOL);
  551. if (accept(g, '$')) return newnode(g, P_EOL);
  552. if (accept(g, L_WORD)) return newnode(g, P_WORD);
  553. if (accept(g, L_NWORD)) return newnode(g, P_NWORD);
  554. atom = parseatom(g);
  555. if (g->lookahead == L_COUNT) {
  556. int min = g->yymin, max = g->yymax;
  557. next(g);
  558. if (max < min)
  559. die(g, "invalid quantifier");
  560. return newrep(g, atom, accept(g, '?'), min, max);
  561. }
  562. if (accept(g, '*')) return newrep(g, atom, accept(g, '?'), 0, REPINF);
  563. if (accept(g, '+')) return newrep(g, atom, accept(g, '?'), 1, REPINF);
  564. if (accept(g, '?')) return newrep(g, atom, accept(g, '?'), 0, 1);
  565. return atom;
  566. }
  567. static Renode *parsecat(struct cstate *g)
  568. {
  569. Renode *cat, *head, **tail;
  570. if (g->lookahead != EOF && g->lookahead != '|' && g->lookahead != ')') {
  571. /* Build a right-leaning tree by splicing in new 'cat' at the tail. */
  572. head = parserep(g);
  573. tail = &head;
  574. while (g->lookahead != EOF && g->lookahead != '|' && g->lookahead != ')') {
  575. cat = newnode(g, P_CAT);
  576. cat->x = *tail;
  577. cat->y = parserep(g);
  578. *tail = cat;
  579. tail = &cat->y;
  580. }
  581. return head;
  582. }
  583. return NULL;
  584. }
  585. static Renode *parsealt(struct cstate *g)
  586. {
  587. Renode *alt, *x;
  588. alt = parsecat(g);
  589. while (accept(g, '|')) {
  590. x = alt;
  591. alt = newnode(g, P_ALT);
  592. alt->x = x;
  593. alt->y = parsecat(g);
  594. }
  595. return alt;
  596. }
  597. /* Compile */
  598. enum {
  599. I_END, I_JUMP, I_SPLIT, I_PLA, I_NLA,
  600. I_ANYNL, I_ANY, I_CHAR, I_CCLASS, I_NCCLASS, I_REF,
  601. I_BOL, I_EOL, I_WORD, I_NWORD,
  602. I_LPAR, I_RPAR
  603. };
  604. struct Reinst {
  605. unsigned char opcode;
  606. unsigned char n;
  607. Rune c;
  608. Reclass *cc;
  609. Reinst *x;
  610. Reinst *y;
  611. };
  612. static size_t count(struct cstate *g, Renode *node, int depth)
  613. {
  614. size_t min, max, n;
  615. if (!node) return 0;
  616. if (++depth > REG_MAXREC) die(g, "stack overflow");
  617. switch (node->type) {
  618. default: return 1;
  619. case P_CAT: return count(g, node->x, depth) + count(g, node->y, depth);
  620. case P_ALT: return count(g, node->x, depth) + count(g, node->y, depth) + 2;
  621. case P_REP:
  622. min = node->m;
  623. max = node->n;
  624. if (min == max) n = count(g, node->x, depth) * min;
  625. else if (max < REPINF) n = count(g, node->x, depth) * max + (max - min);
  626. else n = count(g, node->x, depth) * (min + 1) + 2;
  627. if (n > REG_MAXPROG) die(g, "program too large");
  628. return n;
  629. case P_PAR: return count(g, node->x, depth) + 2;
  630. case P_PLA: return count(g, node->x, depth) + 2;
  631. case P_NLA: return count(g, node->x, depth) + 2;
  632. }
  633. }
  634. static Reinst *emit(Reprog *prog, int opcode)
  635. {
  636. Reinst *inst = prog->end++;
  637. inst->opcode = opcode;
  638. inst->n = 0;
  639. inst->c = 0;
  640. inst->cc = NULL;
  641. inst->x = inst->y = NULL;
  642. return inst;
  643. }
  644. static void compile(Reprog *prog, Renode *node)
  645. {
  646. Reinst *inst, *split, *jump;
  647. int i;
  648. loop:
  649. if (!node)
  650. return;
  651. switch (node->type) {
  652. case P_CAT:
  653. compile(prog, node->x);
  654. node = node->y;
  655. goto loop;
  656. case P_ALT:
  657. split = emit(prog, I_SPLIT);
  658. compile(prog, node->x);
  659. jump = emit(prog, I_JUMP);
  660. compile(prog, node->y);
  661. split->x = split + 1;
  662. split->y = jump + 1;
  663. jump->x = prog->end;
  664. break;
  665. case P_REP:
  666. inst = NULL; /* silence compiler warning. assert(node->m > 0). */
  667. for (i = 0; i < node->m; ++i) {
  668. inst = prog->end;
  669. compile(prog, node->x);
  670. }
  671. if (node->m == node->n)
  672. break;
  673. if (node->n < REPINF) {
  674. for (i = node->m; i < node->n; ++i) {
  675. split = emit(prog, I_SPLIT);
  676. compile(prog, node->x);
  677. if (node->ng) {
  678. split->y = split + 1;
  679. split->x = prog->end;
  680. } else {
  681. split->x = split + 1;
  682. split->y = prog->end;
  683. }
  684. }
  685. } else if (node->m == 0) {
  686. split = emit(prog, I_SPLIT);
  687. compile(prog, node->x);
  688. jump = emit(prog, I_JUMP);
  689. if (node->ng) {
  690. split->y = split + 1;
  691. split->x = prog->end;
  692. } else {
  693. split->x = split + 1;
  694. split->y = prog->end;
  695. }
  696. jump->x = split;
  697. } else {
  698. split = emit(prog, I_SPLIT);
  699. if (node->ng) {
  700. split->y = inst;
  701. split->x = prog->end;
  702. } else {
  703. split->x = inst;
  704. split->y = prog->end;
  705. }
  706. }
  707. break;
  708. case P_BOL: emit(prog, I_BOL); break;
  709. case P_EOL: emit(prog, I_EOL); break;
  710. case P_WORD: emit(prog, I_WORD); break;
  711. case P_NWORD: emit(prog, I_NWORD); break;
  712. case P_PAR:
  713. inst = emit(prog, I_LPAR);
  714. inst->n = node->n;
  715. compile(prog, node->x);
  716. inst = emit(prog, I_RPAR);
  717. inst->n = node->n;
  718. break;
  719. case P_PLA:
  720. split = emit(prog, I_PLA);
  721. compile(prog, node->x);
  722. emit(prog, I_END);
  723. split->x = split + 1;
  724. split->y = prog->end;
  725. break;
  726. case P_NLA:
  727. split = emit(prog, I_NLA);
  728. compile(prog, node->x);
  729. emit(prog, I_END);
  730. split->x = split + 1;
  731. split->y = prog->end;
  732. break;
  733. case P_ANY:
  734. emit(prog, I_ANY);
  735. break;
  736. case P_CHAR:
  737. inst = emit(prog, I_CHAR);
  738. inst->c = (prog->flags & REG_ICASE) ? canon(node->c) : node->c;
  739. break;
  740. case P_CCLASS:
  741. inst = emit(prog, I_CCLASS);
  742. inst->cc = prog->cclass + node->cc;
  743. break;
  744. case P_NCCLASS:
  745. inst = emit(prog, I_NCCLASS);
  746. inst->cc = prog->cclass + node->cc;
  747. break;
  748. case P_REF:
  749. inst = emit(prog, I_REF);
  750. inst->n = node->n;
  751. break;
  752. }
  753. }
  754. #ifdef TEST
  755. static void dumpnode(struct cstate *g, Renode *node)
  756. {
  757. Rune *p;
  758. Reclass *cc;
  759. if (!node) { printf("Empty"); return; }
  760. switch (node->type) {
  761. case P_CAT: printf("Cat("); dumpnode(g, node->x); printf(", "); dumpnode(g, node->y); printf(")"); break;
  762. case P_ALT: printf("Alt("); dumpnode(g, node->x); printf(", "); dumpnode(g, node->y); printf(")"); break;
  763. case P_REP:
  764. printf(node->ng ? "NgRep(%d,%d," : "Rep(%d,%d,", node->m, node->n);
  765. dumpnode(g, node->x);
  766. printf(")");
  767. break;
  768. case P_BOL: printf("Bol"); break;
  769. case P_EOL: printf("Eol"); break;
  770. case P_WORD: printf("Word"); break;
  771. case P_NWORD: printf("NotWord"); break;
  772. case P_PAR: printf("Par(%d,", node->n); dumpnode(g, node->x); printf(")"); break;
  773. case P_PLA: printf("PLA("); dumpnode(g, node->x); printf(")"); break;
  774. case P_NLA: printf("NLA("); dumpnode(g, node->x); printf(")"); break;
  775. case P_ANY: printf("Any"); break;
  776. case P_CHAR: printf("Char(%c)", node->c); break;
  777. case P_CCLASS:
  778. printf("Class(");
  779. cc = g->cclass + node->cc;
  780. for (p = cc->spans; p < cc->end; p += 2) printf("%02X-%02X,", p[0], p[1]);
  781. printf(")");
  782. break;
  783. case P_NCCLASS:
  784. printf("NotClass(");
  785. cc = g->cclass + node->cc;
  786. for (p = cc->spans; p < cc->end; p += 2) printf("%02X-%02X,", p[0], p[1]);
  787. printf(")");
  788. break;
  789. case P_REF: printf("Ref(%d)", node->n); break;
  790. }
  791. }
  792. static void dumpcclass(Reclass *cc) {
  793. Rune *p;
  794. for (p = cc->spans; p < cc->end; p += 2) {
  795. if (p[0] > 32 && p[0] < 127)
  796. printf(" %c", p[0]);
  797. else
  798. printf(" \\x%02x", p[0]);
  799. if (p[1] > 32 && p[1] < 127)
  800. printf("-%c", p[1]);
  801. else
  802. printf("-\\x%02x", p[1]);
  803. }
  804. putchar('\n');
  805. }
  806. static void dumpprog(Reprog *prog)
  807. {
  808. Reinst *inst;
  809. int i;
  810. for (i = 0, inst = prog->start; inst < prog->end; ++i, ++inst) {
  811. printf("% 5d: ", i);
  812. switch (inst->opcode) {
  813. case I_END: puts("end"); break;
  814. case I_JUMP: printf("jump %d\n", (int)(inst->x - prog->start)); break;
  815. case I_SPLIT: printf("split %d %d\n", (int)(inst->x - prog->start), (int)(inst->y - prog->start)); break;
  816. case I_PLA: printf("pla %d %d\n", (int)(inst->x - prog->start), (int)(inst->y - prog->start)); break;
  817. case I_NLA: printf("nla %d %d\n", (int)(inst->x - prog->start), (int)(inst->y - prog->start)); break;
  818. case I_ANY: puts("any"); break;
  819. case I_ANYNL: puts("anynl"); break;
  820. case I_CHAR: printf(inst->c >= 32 && inst->c < 127 ? "char '%c'\n" : "char U+%04X\n", inst->c); break;
  821. case I_CCLASS: printf("cclass"); dumpcclass(inst->cc); break;
  822. case I_NCCLASS: printf("ncclass"); dumpcclass(inst->cc); break;
  823. case I_REF: printf("ref %d\n", inst->n); break;
  824. case I_BOL: puts("bol"); break;
  825. case I_EOL: puts("eol"); break;
  826. case I_WORD: puts("word"); break;
  827. case I_NWORD: puts("nword"); break;
  828. case I_LPAR: printf("lpar %d\n", inst->n); break;
  829. case I_RPAR: printf("rpar %d\n", inst->n); break;
  830. }
  831. }
  832. }
  833. #endif
  834. Reprog *regcompx(void *(*alloc)(void *ctx, void *p, int n), void *ctx,
  835. const char *pattern, int cflags, const char **errorp)
  836. {
  837. struct cstate g;
  838. Renode *node;
  839. Reinst *split, *jump;
  840. int i;
  841. size_t n;
  842. g.pstart = NULL;
  843. g.prog = NULL;
  844. if (setjmp(g.kaboom)) {
  845. if (errorp) *errorp = g.error;
  846. alloc(ctx, g.pstart, 0);
  847. if (g.prog) {
  848. alloc(ctx, g.prog->cclass, 0);
  849. alloc(ctx, g.prog->start, 0);
  850. alloc(ctx, g.prog, 0);
  851. }
  852. return NULL;
  853. }
  854. g.prog = alloc(ctx, NULL, sizeof (Reprog));
  855. if (!g.prog)
  856. die(&g, "cannot allocate regular expression");
  857. g.prog->start = NULL;
  858. g.prog->cclass = NULL;
  859. n = strlen(pattern) * 2;
  860. if (n > REG_MAXPROG)
  861. die(&g, "program too large");
  862. if (n > 0) {
  863. g.pstart = g.pend = alloc(ctx, NULL, sizeof (Renode) * n);
  864. if (!g.pstart)
  865. die(&g, "cannot allocate regular expression parse list");
  866. }
  867. g.source = pattern;
  868. g.ncclass = 0;
  869. g.nsub = 1;
  870. for (i = 0; i < REG_MAXSUB; ++i)
  871. g.sub[i] = 0;
  872. g.prog->flags = cflags;
  873. next(&g);
  874. node = parsealt(&g);
  875. if (g.lookahead == ')')
  876. die(&g, "unmatched ')'");
  877. if (g.lookahead != EOF)
  878. die(&g, "syntax error");
  879. #ifdef TEST
  880. dumpnode(&g, node);
  881. putchar('\n');
  882. #endif
  883. n = 6 + count(&g, node, 0);
  884. if (n > REG_MAXPROG)
  885. die(&g, "program too large");
  886. g.prog->nsub = g.nsub;
  887. g.prog->start = g.prog->end = alloc(ctx, NULL, n * sizeof (Reinst));
  888. if (!g.prog->start)
  889. die(&g, "cannot allocate regular expression instruction list");
  890. if (g.ncclass > 0) {
  891. g.prog->cclass = alloc(ctx, NULL, g.ncclass * sizeof (Reclass));
  892. if (!g.prog->cclass)
  893. die(&g, "cannot allocate regular expression character class list");
  894. memcpy(g.prog->cclass, g.cclass, g.ncclass * sizeof (Reclass));
  895. for (i = 0; i < g.ncclass; ++i)
  896. g.prog->cclass[i].end = g.prog->cclass[i].spans + (g.cclass[i].end - g.cclass[i].spans);
  897. }
  898. split = emit(g.prog, I_SPLIT);
  899. split->x = split + 3;
  900. split->y = split + 1;
  901. emit(g.prog, I_ANYNL);
  902. jump = emit(g.prog, I_JUMP);
  903. jump->x = split;
  904. emit(g.prog, I_LPAR);
  905. compile(g.prog, node);
  906. emit(g.prog, I_RPAR);
  907. emit(g.prog, I_END);
  908. #ifdef TEST
  909. dumpprog(g.prog);
  910. #endif
  911. alloc(ctx, g.pstart, 0);
  912. if (errorp) *errorp = NULL;
  913. return g.prog;
  914. }
  915. void regfreex(void *(*alloc)(void *ctx, void *p, int n), void *ctx, Reprog *prog)
  916. {
  917. if (prog) {
  918. if (prog->cclass)
  919. alloc(ctx, prog->cclass, 0);
  920. alloc(ctx, prog->start, 0);
  921. alloc(ctx, prog, 0);
  922. }
  923. }
  924. static void *default_alloc(void *ctx, void *p, int n)
  925. {
  926. if (n == 0) {
  927. free(p);
  928. return NULL;
  929. }
  930. return realloc(p, (size_t)n);
  931. }
  932. Reprog *regcomp(const char *pattern, int cflags, const char **errorp)
  933. {
  934. return regcompx(default_alloc, NULL, pattern, cflags, errorp);
  935. }
  936. void regfree(Reprog *prog)
  937. {
  938. regfreex(default_alloc, NULL, prog);
  939. }
  940. /* Match */
  941. static int isnewline(int c)
  942. {
  943. return c == 0xA || c == 0xD || c == 0x2028 || c == 0x2029;
  944. }
  945. static int iswordchar(int c)
  946. {
  947. return c == '_' ||
  948. (c >= 'a' && c <= 'z') ||
  949. (c >= 'A' && c <= 'Z') ||
  950. (c >= '0' && c <= '9');
  951. }
  952. static int incclass(Reclass *cc, Rune c)
  953. {
  954. Rune *p;
  955. for (p = cc->spans; p < cc->end; p += 2)
  956. if (p[0] <= c && c <= p[1])
  957. return 1;
  958. return 0;
  959. }
  960. static int incclasscanon(Reclass *cc, Rune c)
  961. {
  962. Rune *p, r;
  963. for (p = cc->spans; p < cc->end; p += 2)
  964. for (r = p[0]; r <= p[1]; ++r)
  965. if (c == canon(r))
  966. return 1;
  967. return 0;
  968. }
  969. static int strncmpcanon(const char *a, const char *b, int n)
  970. {
  971. Rune ra, rb;
  972. int c;
  973. while (n--) {
  974. if (!*a) return -1;
  975. if (!*b) return 1;
  976. a += chartorune(&ra, a);
  977. b += chartorune(&rb, b);
  978. c = canon(ra) - canon(rb);
  979. if (c)
  980. return c;
  981. }
  982. return 0;
  983. }
  984. static int match(Reinst *pc, const char *sp, const char *bol, int flags, Resub *out, int depth, int *runaway)
  985. {
  986. Resub scratch;
  987. int result;
  988. int i;
  989. Rune c;
  990. /* stack overflow */
  991. if (depth > REG_MAXREC)
  992. return -1;
  993. for (;;) {
  994. if (flags & REG_RUNAWAY)
  995. if (++(*runaway) >= REG_MAXRUN)
  996. return -1;
  997. switch (pc->opcode) {
  998. case I_END:
  999. return 0;
  1000. case I_JUMP:
  1001. pc = pc->x;
  1002. break;
  1003. case I_SPLIT:
  1004. scratch = *out;
  1005. result = match(pc->x, sp, bol, flags, &scratch, depth+1, runaway);
  1006. if (result == -1)
  1007. return -1;
  1008. if (result == 0) {
  1009. *out = scratch;
  1010. return 0;
  1011. }
  1012. pc = pc->y;
  1013. break;
  1014. case I_PLA:
  1015. result = match(pc->x, sp, bol, flags, out, depth+1, runaway);
  1016. if (result == -1)
  1017. return -1;
  1018. if (result == 1)
  1019. return 1;
  1020. pc = pc->y;
  1021. break;
  1022. case I_NLA:
  1023. scratch = *out;
  1024. result = match(pc->x, sp, bol, flags, &scratch, depth+1, runaway);
  1025. if (result == -1)
  1026. return -1;
  1027. if (result == 0)
  1028. return 1;
  1029. pc = pc->y;
  1030. break;
  1031. case I_ANYNL:
  1032. if (!*sp) return 1;
  1033. sp += chartorune(&c, sp);
  1034. pc = pc + 1;
  1035. break;
  1036. case I_ANY:
  1037. if (!*sp) return 1;
  1038. sp += chartorune(&c, sp);
  1039. if (isnewline(c))
  1040. return 1;
  1041. pc = pc + 1;
  1042. break;
  1043. case I_CHAR:
  1044. if (!*sp) return 1;
  1045. sp += chartorune(&c, sp);
  1046. if (flags & REG_ICASE)
  1047. c = canon(c);
  1048. if (c != pc->c)
  1049. return 1;
  1050. pc = pc + 1;
  1051. break;
  1052. case I_CCLASS:
  1053. if (!*sp) return 1;
  1054. sp += chartorune(&c, sp);
  1055. if (flags & REG_ICASE) {
  1056. if (!incclasscanon(pc->cc, canon(c)))
  1057. return 1;
  1058. } else {
  1059. if (!incclass(pc->cc, c))
  1060. return 1;
  1061. }
  1062. pc = pc + 1;
  1063. break;
  1064. case I_NCCLASS:
  1065. if (!*sp) return 1;
  1066. sp += chartorune(&c, sp);
  1067. if (flags & REG_ICASE) {
  1068. if (incclasscanon(pc->cc, canon(c)))
  1069. return 1;
  1070. } else {
  1071. if (incclass(pc->cc, c))
  1072. return 1;
  1073. }
  1074. pc = pc + 1;
  1075. break;
  1076. case I_REF:
  1077. i = out->sub[pc->n].ep - out->sub[pc->n].sp;
  1078. if (flags & REG_ICASE) {
  1079. if (strncmpcanon(sp, out->sub[pc->n].sp, i))
  1080. return 1;
  1081. } else {
  1082. if (strncmp(sp, out->sub[pc->n].sp, i))
  1083. return 1;
  1084. }
  1085. if (i > 0)
  1086. sp += i;
  1087. pc = pc + 1;
  1088. break;
  1089. case I_BOL:
  1090. if (sp == bol && !(flags & REG_NOTBOL)) {
  1091. pc = pc + 1;
  1092. break;
  1093. }
  1094. if (flags & REG_NEWLINE) {
  1095. if (sp > bol && isnewline(sp[-1])) {
  1096. pc = pc + 1;
  1097. break;
  1098. }
  1099. }
  1100. return 1;
  1101. case I_EOL:
  1102. if (*sp == 0) {
  1103. pc = pc + 1;
  1104. break;
  1105. }
  1106. if (flags & REG_NEWLINE) {
  1107. if (isnewline(*sp)) {
  1108. pc = pc + 1;
  1109. break;
  1110. }
  1111. }
  1112. return 1;
  1113. case I_WORD:
  1114. i = sp > bol && iswordchar(sp[-1]);
  1115. i ^= iswordchar(sp[0]);
  1116. if (!i)
  1117. return 1;
  1118. pc = pc + 1;
  1119. break;
  1120. case I_NWORD:
  1121. i = sp > bol && iswordchar(sp[-1]);
  1122. i ^= iswordchar(sp[0]);
  1123. if (i)
  1124. return 1;
  1125. pc = pc + 1;
  1126. break;
  1127. case I_LPAR:
  1128. out->sub[pc->n].sp = sp;
  1129. pc = pc + 1;
  1130. break;
  1131. case I_RPAR:
  1132. out->sub[pc->n].ep = sp;
  1133. pc = pc + 1;
  1134. break;
  1135. default:
  1136. return 1;
  1137. }
  1138. }
  1139. }
  1140. int regexec(Reprog *prog, const char *sp, Resub *sub, int eflags)
  1141. {
  1142. Resub scratch;
  1143. int runaway = 0;
  1144. int i;
  1145. if (!sub)
  1146. sub = &scratch;
  1147. sub->nsub = prog->nsub;
  1148. for (i = 0; i < REG_MAXSUB; ++i)
  1149. sub->sub[i].sp = sub->sub[i].ep = NULL;
  1150. return match(prog->start, sp, sp, prog->flags | eflags, sub, 0, &runaway);
  1151. }
  1152. #ifdef TEST
  1153. int main(int argc, char **argv)
  1154. {
  1155. const char *error;
  1156. const char *s;
  1157. Reprog *p;
  1158. Resub m;
  1159. int i;
  1160. if (argc > 1) {
  1161. p = regcomp(argv[1], 0, &error);
  1162. if (!p) {
  1163. fprintf(stderr, "regcomp: %s\n", error);
  1164. return 1;
  1165. }
  1166. if (argc > 2) {
  1167. s = argv[2];
  1168. printf("nsub = %d\n", p->nsub);
  1169. if (!regexec(p, s, &m, REG_RUNAWAY)) {
  1170. for (i = 0; i < m.nsub; ++i) {
  1171. int n = m.sub[i].ep - m.sub[i].sp;
  1172. if (n > 0)
  1173. printf("match %d: s=%d e=%d n=%d '%.*s'\n", i, (int)(m.sub[i].sp - s), (int)(m.sub[i].ep - s), n, n, m.sub[i].sp);
  1174. else
  1175. printf("match %d: n=0 ''\n", i);
  1176. }
  1177. } else {
  1178. printf("no match\n");
  1179. }
  1180. }
  1181. }
  1182. return 0;
  1183. }
  1184. #endif