regexp.c 27 KB

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