slre.c 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722
  1. /*
  2. * Copyright (c) 2004-2005 Sergey Lyubka <valenok@gmail.com>
  3. * All rights reserved
  4. *
  5. * "THE BEER-WARE LICENSE" (Revision 42):
  6. * Sergey Lyubka wrote this file. As long as you retain this notice you
  7. * can do whatever you want with this stuff. If we meet some day, and you think
  8. * this stuff is worth it, you can buy me a beer in return.
  9. */
  10. /*
  11. * Downloaded Sat Nov 5 17:43:06 CET 2011 at
  12. * http://slre.sourceforge.net/1.0/slre.c
  13. */
  14. #ifdef SLRE_TEST
  15. #include <stdio.h>
  16. #include <assert.h>
  17. #include <ctype.h>
  18. #include <stdlib.h>
  19. #include <string.h>
  20. #else
  21. #include <common.h>
  22. #include <linux/ctype.h>
  23. #endif /* SLRE_TEST */
  24. #include <errno.h>
  25. #include <slre.h>
  26. enum {END, BRANCH, ANY, EXACT, ANYOF, ANYBUT, OPEN, CLOSE, BOL, EOL,
  27. STAR, PLUS, STARQ, PLUSQ, QUEST, SPACE, NONSPACE, DIGIT};
  28. #ifdef SLRE_TEST
  29. static struct {
  30. const char *name;
  31. int narg;
  32. const char *flags;
  33. } opcodes[] = {
  34. {"END", 0, ""}, /* End of code block or program */
  35. {"BRANCH", 2, "oo"}, /* Alternative operator, "|" */
  36. {"ANY", 0, ""}, /* Match any character, "." */
  37. {"EXACT", 2, "d"}, /* Match exact string */
  38. {"ANYOF", 2, "D"}, /* Match any from set, "[]" */
  39. {"ANYBUT", 2, "D"}, /* Match any but from set, "[^]"*/
  40. {"OPEN ", 1, "i"}, /* Capture start, "(" */
  41. {"CLOSE", 1, "i"}, /* Capture end, ")" */
  42. {"BOL", 0, ""}, /* Beginning of string, "^" */
  43. {"EOL", 0, ""}, /* End of string, "$" */
  44. {"STAR", 1, "o"}, /* Match zero or more times "*" */
  45. {"PLUS", 1, "o"}, /* Match one or more times, "+" */
  46. {"STARQ", 1, "o"}, /* Non-greedy STAR, "*?" */
  47. {"PLUSQ", 1, "o"}, /* Non-greedy PLUS, "+?" */
  48. {"QUEST", 1, "o"}, /* Match zero or one time, "?" */
  49. {"SPACE", 0, ""}, /* Match whitespace, "\s" */
  50. {"NONSPACE", 0, ""}, /* Match non-space, "\S" */
  51. {"DIGIT", 0, ""} /* Match digit, "\d" */
  52. };
  53. #endif /* SLRE_TEST */
  54. /*
  55. * Commands and operands are all unsigned char (1 byte long). All code offsets
  56. * are relative to current address, and positive (always point forward). Data
  57. * offsets are absolute. Commands with operands:
  58. *
  59. * BRANCH offset1 offset2
  60. * Try to match the code block that follows the BRANCH instruction
  61. * (code block ends with END). If no match, try to match code block that
  62. * starts at offset1. If either of these match, jump to offset2.
  63. *
  64. * EXACT data_offset data_length
  65. * Try to match exact string. String is recorded in data section from
  66. * data_offset, and has length data_length.
  67. *
  68. * OPEN capture_number
  69. * CLOSE capture_number
  70. * If the user have passed 'struct cap' array for captures, OPEN
  71. * records the beginning of the matched substring (cap->ptr), CLOSE
  72. * sets the length (cap->len) for respective capture_number.
  73. *
  74. * STAR code_offset
  75. * PLUS code_offset
  76. * QUEST code_offset
  77. * *, +, ?, respectively. Try to gobble as much as possible from the
  78. * matched buffer, until code block that follows these instructions
  79. * matches. When the longest possible string is matched,
  80. * jump to code_offset
  81. *
  82. * STARQ, PLUSQ are non-greedy versions of STAR and PLUS.
  83. */
  84. static const char *meta_chars = "|.^$*+?()[\\";
  85. #ifdef SLRE_TEST
  86. static void
  87. print_character_set(FILE *fp, const unsigned char *p, int len)
  88. {
  89. int i;
  90. for (i = 0; i < len; i++) {
  91. if (i > 0)
  92. (void) fputc(',', fp);
  93. if (p[i] == 0) {
  94. i++;
  95. if (p[i] == 0)
  96. (void) fprintf(fp, "\\x%02x", p[i]);
  97. else
  98. (void) fprintf(fp, "%s", opcodes[p[i]].name);
  99. } else if (isprint(p[i])) {
  100. (void) fputc(p[i], fp);
  101. } else {
  102. (void) fprintf(fp, "\\x%02x", p[i]);
  103. }
  104. }
  105. }
  106. void
  107. slre_dump(const struct slre *r, FILE *fp)
  108. {
  109. int i, j, ch, op, pc;
  110. for (pc = 0; pc < r->code_size; pc++) {
  111. op = r->code[pc];
  112. (void) fprintf(fp, "%3d %s ", pc, opcodes[op].name);
  113. for (i = 0; opcodes[op].flags[i] != '\0'; i++)
  114. switch (opcodes[op].flags[i]) {
  115. case 'i':
  116. (void) fprintf(fp, "%d ", r->code[pc + 1]);
  117. pc++;
  118. break;
  119. case 'o':
  120. (void) fprintf(fp, "%d ",
  121. pc + r->code[pc + 1] - i);
  122. pc++;
  123. break;
  124. case 'D':
  125. print_character_set(fp, r->data +
  126. r->code[pc + 1], r->code[pc + 2]);
  127. pc += 2;
  128. break;
  129. case 'd':
  130. (void) fputc('"', fp);
  131. for (j = 0; j < r->code[pc + 2]; j++) {
  132. ch = r->data[r->code[pc + 1] + j];
  133. if (isprint(ch)) {
  134. (void) fputc(ch, fp);
  135. } else {
  136. (void) fprintf(fp,
  137. "\\x%02x", ch);
  138. }
  139. }
  140. (void) fputc('"', fp);
  141. pc += 2;
  142. break;
  143. }
  144. (void) fputc('\n', fp);
  145. }
  146. }
  147. #endif /* SLRE_TEST */
  148. static void
  149. set_jump_offset(struct slre *r, int pc, int offset)
  150. {
  151. assert(offset < r->code_size);
  152. if (r->code_size - offset > 0xff)
  153. r->err_str = "Jump offset is too big";
  154. else
  155. r->code[pc] = (unsigned char) (r->code_size - offset);
  156. }
  157. static void
  158. emit(struct slre *r, int code)
  159. {
  160. if (r->code_size >= (int) (sizeof(r->code) / sizeof(r->code[0])))
  161. r->err_str = "RE is too long (code overflow)";
  162. else
  163. r->code[r->code_size++] = (unsigned char) code;
  164. }
  165. static void
  166. store_char_in_data(struct slre *r, int ch)
  167. {
  168. if (r->data_size >= (int) sizeof(r->data))
  169. r->err_str = "RE is too long (data overflow)";
  170. else
  171. r->data[r->data_size++] = ch;
  172. }
  173. static void
  174. exact(struct slre *r, const char **re)
  175. {
  176. int old_data_size = r->data_size;
  177. while (**re != '\0' && (strchr(meta_chars, **re)) == NULL)
  178. store_char_in_data(r, *(*re)++);
  179. emit(r, EXACT);
  180. emit(r, old_data_size);
  181. emit(r, r->data_size - old_data_size);
  182. }
  183. static int
  184. get_escape_char(const char **re)
  185. {
  186. int res;
  187. switch (*(*re)++) {
  188. case 'n':
  189. res = '\n';
  190. break;
  191. case 'r':
  192. res = '\r';
  193. break;
  194. case 't':
  195. res = '\t';
  196. break;
  197. case '0':
  198. res = 0;
  199. break;
  200. case 'S':
  201. res = NONSPACE << 8;
  202. break;
  203. case 's':
  204. res = SPACE << 8;
  205. break;
  206. case 'd':
  207. res = DIGIT << 8;
  208. break;
  209. default:
  210. res = (*re)[-1];
  211. break;
  212. }
  213. return res;
  214. }
  215. static void
  216. anyof(struct slre *r, const char **re)
  217. {
  218. int esc, old_data_size = r->data_size, op = ANYOF;
  219. if (**re == '^') {
  220. op = ANYBUT;
  221. (*re)++;
  222. }
  223. while (**re != '\0')
  224. switch (*(*re)++) {
  225. case ']':
  226. emit(r, op);
  227. emit(r, old_data_size);
  228. emit(r, r->data_size - old_data_size);
  229. return;
  230. /* NOTREACHED */
  231. break;
  232. case '\\':
  233. esc = get_escape_char(re);
  234. if ((esc & 0xff) == 0) {
  235. store_char_in_data(r, 0);
  236. store_char_in_data(r, esc >> 8);
  237. } else {
  238. store_char_in_data(r, esc);
  239. }
  240. break;
  241. default:
  242. store_char_in_data(r, (*re)[-1]);
  243. break;
  244. }
  245. r->err_str = "No closing ']' bracket";
  246. }
  247. static void
  248. relocate(struct slre *r, int begin, int shift)
  249. {
  250. emit(r, END);
  251. memmove(r->code + begin + shift, r->code + begin, r->code_size - begin);
  252. r->code_size += shift;
  253. }
  254. static void
  255. quantifier(struct slre *r, int prev, int op)
  256. {
  257. if (r->code[prev] == EXACT && r->code[prev + 2] > 1) {
  258. r->code[prev + 2]--;
  259. emit(r, EXACT);
  260. emit(r, r->code[prev + 1] + r->code[prev + 2]);
  261. emit(r, 1);
  262. prev = r->code_size - 3;
  263. }
  264. relocate(r, prev, 2);
  265. r->code[prev] = op;
  266. set_jump_offset(r, prev + 1, prev);
  267. }
  268. static void
  269. exact_one_char(struct slre *r, int ch)
  270. {
  271. emit(r, EXACT);
  272. emit(r, r->data_size);
  273. emit(r, 1);
  274. store_char_in_data(r, ch);
  275. }
  276. static void
  277. fixup_branch(struct slre *r, int fixup)
  278. {
  279. if (fixup > 0) {
  280. emit(r, END);
  281. set_jump_offset(r, fixup, fixup - 2);
  282. }
  283. }
  284. static void
  285. compile(struct slre *r, const char **re)
  286. {
  287. int op, esc, branch_start, last_op, fixup, cap_no, level;
  288. fixup = 0;
  289. level = r->num_caps;
  290. branch_start = last_op = r->code_size;
  291. for (;;)
  292. switch (*(*re)++) {
  293. case '\0':
  294. (*re)--;
  295. return;
  296. /* NOTREACHED */
  297. break;
  298. case '^':
  299. emit(r, BOL);
  300. break;
  301. case '$':
  302. emit(r, EOL);
  303. break;
  304. case '.':
  305. last_op = r->code_size;
  306. emit(r, ANY);
  307. break;
  308. case '[':
  309. last_op = r->code_size;
  310. anyof(r, re);
  311. break;
  312. case '\\':
  313. last_op = r->code_size;
  314. esc = get_escape_char(re);
  315. if (esc & 0xff00)
  316. emit(r, esc >> 8);
  317. else
  318. exact_one_char(r, esc);
  319. break;
  320. case '(':
  321. last_op = r->code_size;
  322. cap_no = ++r->num_caps;
  323. emit(r, OPEN);
  324. emit(r, cap_no);
  325. compile(r, re);
  326. if (*(*re)++ != ')') {
  327. r->err_str = "No closing bracket";
  328. return;
  329. }
  330. emit(r, CLOSE);
  331. emit(r, cap_no);
  332. break;
  333. case ')':
  334. (*re)--;
  335. fixup_branch(r, fixup);
  336. if (level == 0) {
  337. r->err_str = "Unbalanced brackets";
  338. return;
  339. }
  340. return;
  341. /* NOTREACHED */
  342. break;
  343. case '+':
  344. case '*':
  345. op = (*re)[-1] == '*' ? STAR : PLUS;
  346. if (**re == '?') {
  347. (*re)++;
  348. op = op == STAR ? STARQ : PLUSQ;
  349. }
  350. quantifier(r, last_op, op);
  351. break;
  352. case '?':
  353. quantifier(r, last_op, QUEST);
  354. break;
  355. case '|':
  356. fixup_branch(r, fixup);
  357. relocate(r, branch_start, 3);
  358. r->code[branch_start] = BRANCH;
  359. set_jump_offset(r, branch_start + 1, branch_start);
  360. fixup = branch_start + 2;
  361. r->code[fixup] = 0xff;
  362. break;
  363. default:
  364. (*re)--;
  365. last_op = r->code_size;
  366. exact(r, re);
  367. break;
  368. }
  369. }
  370. int
  371. slre_compile(struct slre *r, const char *re)
  372. {
  373. r->err_str = NULL;
  374. r->code_size = r->data_size = r->num_caps = r->anchored = 0;
  375. if (*re == '^')
  376. r->anchored++;
  377. emit(r, OPEN); /* This will capture what matches full RE */
  378. emit(r, 0);
  379. while (*re != '\0')
  380. compile(r, &re);
  381. if (r->code[2] == BRANCH)
  382. fixup_branch(r, 4);
  383. emit(r, CLOSE);
  384. emit(r, 0);
  385. emit(r, END);
  386. return (r->err_str == NULL ? 1 : 0);
  387. }
  388. static int match(const struct slre *, int,
  389. const char *, int, int *, struct cap *);
  390. static void
  391. loop_greedy(const struct slre *r, int pc, const char *s, int len, int *ofs)
  392. {
  393. int saved_offset, matched_offset;
  394. matched_offset = *ofs;
  395. while (match(r, pc + 2, s, len, ofs, NULL)) {
  396. saved_offset = *ofs;
  397. if (match(r, pc + r->code[pc + 1], s, len, ofs, NULL))
  398. matched_offset = saved_offset;
  399. *ofs = saved_offset;
  400. }
  401. *ofs = matched_offset;
  402. }
  403. static void
  404. loop_non_greedy(const struct slre *r, int pc, const char *s, int len, int *ofs)
  405. {
  406. int saved_offset = *ofs;
  407. while (match(r, pc + 2, s, len, ofs, NULL)) {
  408. saved_offset = *ofs;
  409. if (match(r, pc + r->code[pc + 1], s, len, ofs, NULL))
  410. break;
  411. }
  412. *ofs = saved_offset;
  413. }
  414. static int
  415. is_any_of(const unsigned char *p, int len, const char *s, int *ofs)
  416. {
  417. int i, ch;
  418. ch = s[*ofs];
  419. for (i = 0; i < len; i++)
  420. if (p[i] == ch) {
  421. (*ofs)++;
  422. return 1;
  423. }
  424. return 0;
  425. }
  426. static int
  427. is_any_but(const unsigned char *p, int len, const char *s, int *ofs)
  428. {
  429. int i, ch;
  430. ch = s[*ofs];
  431. for (i = 0; i < len; i++) {
  432. if (p[i] == ch)
  433. return 0;
  434. }
  435. (*ofs)++;
  436. return 1;
  437. }
  438. static int
  439. match(const struct slre *r, int pc, const char *s, int len,
  440. int *ofs, struct cap *caps)
  441. {
  442. int n, saved_offset, res = 1;
  443. while (res && r->code[pc] != END) {
  444. assert(pc < r->code_size);
  445. assert(pc < (int) (sizeof(r->code) / sizeof(r->code[0])));
  446. switch (r->code[pc]) {
  447. case BRANCH:
  448. saved_offset = *ofs;
  449. res = match(r, pc + 3, s, len, ofs, caps);
  450. if (res == 0) {
  451. *ofs = saved_offset;
  452. res = match(r, pc + r->code[pc + 1],
  453. s, len, ofs, caps);
  454. }
  455. pc += r->code[pc + 2];
  456. break;
  457. case EXACT:
  458. res = 0;
  459. n = r->code[pc + 2]; /* String length */
  460. if (n <= len - *ofs && !memcmp(s + *ofs, r->data +
  461. r->code[pc + 1], n)) {
  462. (*ofs) += n;
  463. res = 1;
  464. }
  465. pc += 3;
  466. break;
  467. case QUEST:
  468. res = 1;
  469. saved_offset = *ofs;
  470. if (!match(r, pc + 2, s, len, ofs, caps))
  471. *ofs = saved_offset;
  472. pc += r->code[pc + 1];
  473. break;
  474. case STAR:
  475. res = 1;
  476. loop_greedy(r, pc, s, len, ofs);
  477. pc += r->code[pc + 1];
  478. break;
  479. case STARQ:
  480. res = 1;
  481. loop_non_greedy(r, pc, s, len, ofs);
  482. pc += r->code[pc + 1];
  483. break;
  484. case PLUS:
  485. res = match(r, pc + 2, s, len, ofs, caps);
  486. if (res == 0)
  487. break;
  488. loop_greedy(r, pc, s, len, ofs);
  489. pc += r->code[pc + 1];
  490. break;
  491. case PLUSQ:
  492. res = match(r, pc + 2, s, len, ofs, caps);
  493. if (res == 0)
  494. break;
  495. loop_non_greedy(r, pc, s, len, ofs);
  496. pc += r->code[pc + 1];
  497. break;
  498. case SPACE:
  499. res = 0;
  500. if (*ofs < len && isspace(((unsigned char *)s)[*ofs])) {
  501. (*ofs)++;
  502. res = 1;
  503. }
  504. pc++;
  505. break;
  506. case NONSPACE:
  507. res = 0;
  508. if (*ofs < len &&
  509. !isspace(((unsigned char *)s)[*ofs])) {
  510. (*ofs)++;
  511. res = 1;
  512. }
  513. pc++;
  514. break;
  515. case DIGIT:
  516. res = 0;
  517. if (*ofs < len && isdigit(((unsigned char *)s)[*ofs])) {
  518. (*ofs)++;
  519. res = 1;
  520. }
  521. pc++;
  522. break;
  523. case ANY:
  524. res = 0;
  525. if (*ofs < len) {
  526. (*ofs)++;
  527. res = 1;
  528. }
  529. pc++;
  530. break;
  531. case ANYOF:
  532. res = 0;
  533. if (*ofs < len)
  534. res = is_any_of(r->data + r->code[pc + 1],
  535. r->code[pc + 2], s, ofs);
  536. pc += 3;
  537. break;
  538. case ANYBUT:
  539. res = 0;
  540. if (*ofs < len)
  541. res = is_any_but(r->data + r->code[pc + 1],
  542. r->code[pc + 2], s, ofs);
  543. pc += 3;
  544. break;
  545. case BOL:
  546. res = *ofs == 0 ? 1 : 0;
  547. pc++;
  548. break;
  549. case EOL:
  550. res = *ofs == len ? 1 : 0;
  551. pc++;
  552. break;
  553. case OPEN:
  554. if (caps != NULL)
  555. caps[r->code[pc + 1]].ptr = s + *ofs;
  556. pc += 2;
  557. break;
  558. case CLOSE:
  559. if (caps != NULL)
  560. caps[r->code[pc + 1]].len = (s + *ofs) -
  561. caps[r->code[pc + 1]].ptr;
  562. pc += 2;
  563. break;
  564. case END:
  565. pc++;
  566. break;
  567. default:
  568. printf("unknown cmd (%d) at %d\n", r->code[pc], pc);
  569. assert(0);
  570. break;
  571. }
  572. }
  573. return res;
  574. }
  575. int
  576. slre_match(const struct slre *r, const char *buf, int len,
  577. struct cap *caps)
  578. {
  579. int i, ofs = 0, res = 0;
  580. if (r->anchored) {
  581. res = match(r, 0, buf, len, &ofs, caps);
  582. } else {
  583. for (i = 0; i < len && res == 0; i++) {
  584. ofs = i;
  585. res = match(r, 0, buf, len, &ofs, caps);
  586. }
  587. }
  588. return res;
  589. }
  590. #ifdef SLRE_TEST
  591. #define N_CAPS 5
  592. int main(int argc, char *argv[])
  593. {
  594. struct slre slre;
  595. struct cap caps[N_CAPS];
  596. unsigned char data[1 * 1024 * 1024];
  597. FILE *fp;
  598. int i, res, len;
  599. if (argc < 2) {
  600. fprintf(stderr, "Usage: %s 'slre' <file>\n", argv[0]);
  601. return 1;
  602. }
  603. fp = fopen(argv[2], "rb");
  604. if (fp == NULL) {
  605. fprintf(stderr, "Error: cannot open %s:%s\n",
  606. argv[2], strerror(errno));
  607. return 1;
  608. }
  609. if (!slre_compile(&slre, argv[1])) {
  610. fprintf(stderr, "Error compiling slre: %s\n", slre.err_str);
  611. return 1;
  612. }
  613. slre_dump(&slre, stderr);
  614. while (fgets(data, sizeof(data), fp) != NULL) {
  615. len = strlen(data);
  616. if ((len > 0) && (data[len-1] == '\n')) {
  617. data[len-1] = '\0';
  618. --len;
  619. }
  620. printf("Data = \"%s\"\n", data);
  621. (void) memset(caps, 0, sizeof(caps));
  622. res = slre_match(&slre, data, len, caps);
  623. printf("Result [%d]: %d\n", i, res);
  624. for (i = 0; i < N_CAPS; i++) {
  625. if (caps[i].len > 0) {
  626. printf("Substring %d: len=%d [%.*s]\n", i,
  627. caps[i].len,
  628. caps[i].len, caps[i].ptr);
  629. }
  630. }
  631. printf("----------------------------------------------------\n");
  632. }
  633. (void) fclose(fp);
  634. return 0;
  635. }
  636. #endif /* SLRE_TEST */