bundles/org.simantics.databoard/cpp/DataBoardTest/DataBoard/slre.c

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