]> gerrit.simantics Code Review - simantics/platform.git/blob - bundles/org.simantics.databoard/cpp/DataBoardTest/DataBoard/slre.c
Document server should use variable value request with binding
[simantics/platform.git] / 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 */