root/luci2/libubox/trex.c @ 6161

Revision 6161, 16.6 KB (checked in by Cyrus, 3 years ago)

libubox: Add trex
Line 
1/* see copyright notice in trex.h */
2#include <string.h>
3#include <stdlib.h>
4#include <ctype.h>
5#include <setjmp.h>
6#include "trex.h"
7
8#ifdef _UINCODE
9#define scisprint iswprint
10#define scstrlen wcslen
11#define scprintf wprintf
12#define _SC(x) L(x)
13#else
14#define scisprint isprint
15#define scstrlen strlen
16#define scprintf printf
17#define _SC(x) (x)
18#endif
19
20#ifdef _DEBUG
21#include <stdio.h>
22
23static const TRexChar *g_nnames[] =
24{
25    _SC("NONE"),_SC("OP_GREEDY"),   _SC("OP_OR"),
26    _SC("OP_EXPR"),_SC("OP_NOCAPEXPR"),_SC("OP_DOT"),   _SC("OP_CLASS"),
27    _SC("OP_CCLASS"),_SC("OP_NCLASS"),_SC("OP_RANGE"),_SC("OP_CHAR"),
28    _SC("OP_EOL"),_SC("OP_BOL"),_SC("OP_WB")
29};
30
31#endif
32#define OP_GREEDY       (MAX_CHAR+1) // * + ? {n}
33#define OP_OR           (MAX_CHAR+2)
34#define OP_EXPR         (MAX_CHAR+3) //parentesis ()
35#define OP_NOCAPEXPR    (MAX_CHAR+4) //parentesis (?:)
36#define OP_DOT          (MAX_CHAR+5)
37#define OP_CLASS        (MAX_CHAR+6)
38#define OP_CCLASS       (MAX_CHAR+7)
39#define OP_NCLASS       (MAX_CHAR+8) //negates class the [^
40#define OP_RANGE        (MAX_CHAR+9)
41#define OP_CHAR         (MAX_CHAR+10)
42#define OP_EOL          (MAX_CHAR+11)
43#define OP_BOL          (MAX_CHAR+12)
44#define OP_WB           (MAX_CHAR+13)
45
46#define TREX_SYMBOL_ANY_CHAR ('.')
47#define TREX_SYMBOL_GREEDY_ONE_OR_MORE ('+')
48#define TREX_SYMBOL_GREEDY_ZERO_OR_MORE ('*')
49#define TREX_SYMBOL_GREEDY_ZERO_OR_ONE ('?')
50#define TREX_SYMBOL_BRANCH ('|')
51#define TREX_SYMBOL_END_OF_STRING ('$')
52#define TREX_SYMBOL_BEGINNING_OF_STRING ('^')
53#define TREX_SYMBOL_ESCAPE_CHAR ('\\')
54
55
56typedef int TRexNodeType;
57
58typedef struct tagTRexNode{
59    TRexNodeType type;
60    int left;
61    int right;
62    int next;
63}TRexNode;
64
65struct TRex{
66    const TRexChar *_eol;
67    const TRexChar *_bol;
68    const TRexChar *_p;
69    int _first;
70    int _op;
71    TRexNode *_nodes;
72    int _nallocated;
73    int _nsize;
74    int _nsubexpr;
75    TRexMatch *_matches;
76    int _currsubexp;
77    void *_jmpbuf;
78    const TRexChar **_error;
79};
80
81static int trex_list(TRex *exp);
82
83static int trex_newnode(TRex *exp, TRexNodeType type)
84{
85    TRexNode n;
86    int newid;
87    n.type = type;
88    n.next = n.right = n.left = -1;
89    if(type == OP_EXPR)
90        n.right = exp->_nsubexpr++;
91    if(exp->_nallocated < (exp->_nsize + 1)) {
92        exp->_nallocated *= 2;
93        exp->_nodes = (TRexNode *)realloc(exp->_nodes, exp->_nallocated * sizeof(TRexNode));
94    }
95    exp->_nodes[exp->_nsize++] = n;
96    newid = exp->_nsize - 1;
97    return (int)newid;
98}
99
100static void trex_error(TRex *exp,const TRexChar *error)
101{
102    if(exp->_error) *exp->_error = error;
103    longjmp(*((jmp_buf*)exp->_jmpbuf),-1);
104}
105
106static void trex_expect(TRex *exp, int n){
107    if((*exp->_p) != n) 
108        trex_error(exp, _SC("expected paren"));
109    exp->_p++;
110}
111
112static TRexChar trex_escapechar(TRex *exp)
113{
114    if(*exp->_p == TREX_SYMBOL_ESCAPE_CHAR){
115        exp->_p++;
116        switch(*exp->_p) {
117        case 'v': exp->_p++; return '\v';
118        case 'n': exp->_p++; return '\n';
119        case 't': exp->_p++; return '\t';
120        case 'r': exp->_p++; return '\r';
121        case 'f': exp->_p++; return '\f';
122        default: return (*exp->_p++);
123        }
124    } else if(!scisprint(*exp->_p)) trex_error(exp,_SC("letter expected"));
125    return (*exp->_p++);
126}
127
128static int trex_charclass(TRex *exp,int classid)
129{
130    int n = trex_newnode(exp,OP_CCLASS);
131    exp->_nodes[n].left = classid;
132    return n;
133}
134
135static int trex_charnode(TRex *exp,TRexBool isclass)
136{
137    TRexChar t;
138    if(*exp->_p == TREX_SYMBOL_ESCAPE_CHAR) {
139        exp->_p++;
140        switch(*exp->_p) {
141            case 'n': exp->_p++; return trex_newnode(exp,'\n');
142            case 't': exp->_p++; return trex_newnode(exp,'\t');
143            case 'r': exp->_p++; return trex_newnode(exp,'\r');
144            case 'f': exp->_p++; return trex_newnode(exp,'\f');
145            case 'v': exp->_p++; return trex_newnode(exp,'\v');
146            case 'a': case 'A': case 'w': case 'W': case 's': case 'S':
147            case 'd': case 'D': case 'x': case 'X': case 'c': case 'C':
148            case 'p': case 'P': case 'l': case 'u':
149                {
150                t = *exp->_p; exp->_p++; 
151                return trex_charclass(exp,t);
152                }
153            case 'b':
154            case 'B':
155                if(!isclass) {
156                    int node = trex_newnode(exp,OP_WB);
157                    exp->_nodes[node].left = *exp->_p;
158                    exp->_p++; 
159                    return node;
160                } //else default
161            default: 
162                t = *exp->_p; exp->_p++; 
163                return trex_newnode(exp,t);
164        }
165    }
166    else if(!scisprint(*exp->_p)) {
167       
168        trex_error(exp,_SC("letter expected"));
169    }
170    t = *exp->_p; exp->_p++; 
171    return trex_newnode(exp,t);
172}
173static int trex_class(TRex *exp)
174{
175    int ret = -1;
176    int first = -1,chain;
177    if(*exp->_p == TREX_SYMBOL_BEGINNING_OF_STRING){
178        ret = trex_newnode(exp,OP_NCLASS);
179        exp->_p++;
180    }else ret = trex_newnode(exp,OP_CLASS);
181   
182    if(*exp->_p == ']') trex_error(exp,_SC("empty class"));
183    chain = ret;
184    while(*exp->_p != ']' && exp->_p != exp->_eol) {
185        if(*exp->_p == '-' && first != -1){ 
186            int r,t;
187            if(*exp->_p++ == ']') trex_error(exp,_SC("unfinished range"));
188            r = trex_newnode(exp,OP_RANGE);
189            if(first>*exp->_p) trex_error(exp,_SC("invalid range"));
190            if(exp->_nodes[first].type == OP_CCLASS) trex_error(exp,_SC("cannot use character classes in ranges"));
191            exp->_nodes[r].left = exp->_nodes[first].type;
192            t = trex_escapechar(exp);
193            exp->_nodes[r].right = t;
194            exp->_nodes[chain].next = r;
195            chain = r;
196            first = -1;
197        }
198        else{
199            if(first!=-1){
200                int c = first;
201                exp->_nodes[chain].next = c;
202                chain = c;
203                first = trex_charnode(exp,TRex_True);
204            }
205            else{
206                first = trex_charnode(exp,TRex_True);
207            }
208        }
209    }
210    if(first!=-1){
211        int c = first;
212        exp->_nodes[chain].next = c;
213        chain = c;
214        first = -1;
215    }
216    /* hack? */
217    exp->_nodes[ret].left = exp->_nodes[ret].next;
218    exp->_nodes[ret].next = -1;
219    return ret;
220}
221
222static int trex_parsenumber(TRex *exp)
223{
224    int ret = *exp->_p-'0';
225    int positions = 10;
226    exp->_p++;
227    while(isdigit(*exp->_p)) {
228        ret = ret*10+(*exp->_p++-'0');
229        if(positions==1000000000) trex_error(exp,_SC("overflow in numeric constant"));
230        positions *= 10;
231    };
232    return ret;
233}
234
235static int trex_element(TRex *exp)
236{
237    int ret = -1;
238    switch(*exp->_p)
239    {
240    case '(': {
241        int expr,newn;
242        exp->_p++;
243
244
245        if(*exp->_p =='?') {
246            exp->_p++;
247            trex_expect(exp,':');
248            expr = trex_newnode(exp,OP_NOCAPEXPR);
249        }
250        else
251            expr = trex_newnode(exp,OP_EXPR);
252        newn = trex_list(exp);
253        exp->_nodes[expr].left = newn;
254        ret = expr;
255        trex_expect(exp,')');
256              }
257              break;
258    case '[':
259        exp->_p++;
260        ret = trex_class(exp);
261        trex_expect(exp,']');
262        break;
263    case TREX_SYMBOL_END_OF_STRING: exp->_p++; ret = trex_newnode(exp,OP_EOL);break;
264    case TREX_SYMBOL_ANY_CHAR: exp->_p++; ret = trex_newnode(exp,OP_DOT);break;
265    default:
266        ret = trex_charnode(exp,TRex_False);
267        break;
268    }
269
270    {
271        int op;
272        TRexBool isgreedy = TRex_False;
273        unsigned short p0 = 0, p1 = 0;
274        switch(*exp->_p){
275            case TREX_SYMBOL_GREEDY_ZERO_OR_MORE: p0 = 0; p1 = 0xFFFF; exp->_p++; isgreedy = TRex_True; break;
276            case TREX_SYMBOL_GREEDY_ONE_OR_MORE: p0 = 1; p1 = 0xFFFF; exp->_p++; isgreedy = TRex_True; break;
277            case TREX_SYMBOL_GREEDY_ZERO_OR_ONE: p0 = 0; p1 = 1; exp->_p++; isgreedy = TRex_True; break;
278            case '{':
279                exp->_p++;
280                if(!isdigit(*exp->_p)) trex_error(exp,_SC("number expected"));
281                p0 = (unsigned short)trex_parsenumber(exp);
282                /*******************************/
283                switch(*exp->_p) {
284            case '}':
285                p1 = p0; exp->_p++;
286                break;
287            case ',':
288                exp->_p++;
289                p1 = 0xFFFF;
290                if(isdigit(*exp->_p)){
291                    p1 = (unsigned short)trex_parsenumber(exp);
292                }
293                trex_expect(exp,'}');
294                break;
295            default:
296                trex_error(exp,_SC(", or } expected"));
297        }
298        /*******************************/
299        isgreedy = TRex_True; 
300        break;
301
302        }
303        if(isgreedy) {
304            int nnode = trex_newnode(exp,OP_GREEDY);
305            op = OP_GREEDY;
306            exp->_nodes[nnode].left = ret;
307            exp->_nodes[nnode].right = ((p0)<<16)|p1;
308            ret = nnode;
309        }
310    }
311    if((*exp->_p != TREX_SYMBOL_BRANCH) && (*exp->_p != ')') && (*exp->_p != TREX_SYMBOL_GREEDY_ZERO_OR_MORE) && (*exp->_p != TREX_SYMBOL_GREEDY_ONE_OR_MORE) && (*exp->_p != '\0')) {
312        int nnode = trex_element(exp);
313        exp->_nodes[ret].next = nnode;
314    }
315
316    return ret;
317}
318
319static int trex_list(TRex *exp)
320{
321    int ret=-1,e;
322    if(*exp->_p == TREX_SYMBOL_BEGINNING_OF_STRING) {
323        exp->_p++;
324        ret = trex_newnode(exp,OP_BOL);
325    }
326    e = trex_element(exp);
327    if(ret != -1) {
328        exp->_nodes[ret].next = e;
329    }
330    else ret = e;
331
332    if(*exp->_p == TREX_SYMBOL_BRANCH) {
333        int temp,tright;
334        exp->_p++;
335        temp = trex_newnode(exp,OP_OR);
336        exp->_nodes[temp].left = ret;
337        tright = trex_list(exp);
338        exp->_nodes[temp].right = tright;
339        ret = temp;
340    }
341    return ret;
342}
343
344static TRexBool trex_matchcclass(int cclass,TRexChar c)
345{
346    switch(cclass) {
347    case 'a': return isalpha(c)?TRex_True:TRex_False;
348    case 'A': return !isalpha(c)?TRex_True:TRex_False;
349    case 'w': return (isalnum(c) || c == '_')?TRex_True:TRex_False;
350    case 'W': return (!isalnum(c) && c != '_')?TRex_True:TRex_False;
351    case 's': return isspace(c)?TRex_True:TRex_False;
352    case 'S': return !isspace(c)?TRex_True:TRex_False;
353    case 'd': return isdigit(c)?TRex_True:TRex_False;
354    case 'D': return !isdigit(c)?TRex_True:TRex_False;
355    case 'x': return isxdigit(c)?TRex_True:TRex_False;
356    case 'X': return !isxdigit(c)?TRex_True:TRex_False;
357    case 'c': return iscntrl(c)?TRex_True:TRex_False;
358    case 'C': return !iscntrl(c)?TRex_True:TRex_False;
359    case 'p': return ispunct(c)?TRex_True:TRex_False;
360    case 'P': return !ispunct(c)?TRex_True:TRex_False;
361    case 'l': return islower(c)?TRex_True:TRex_False;
362    case 'u': return isupper(c)?TRex_True:TRex_False;
363    }
364    return TRex_False; /*cannot happen*/
365}
366
367static TRexBool trex_matchclass(TRex* exp,TRexNode *node,TRexChar c)
368{
369    do {
370        switch(node->type) {
371            case OP_RANGE:
372                if(c >= node->left && c <= node->right) return TRex_True;
373                break;
374            case OP_CCLASS:
375                if(trex_matchcclass(node->left,c)) return TRex_True;
376                break;
377            default:
378                if(c == node->type)return TRex_True;
379        }
380    } while((node->next != -1) && (node = &exp->_nodes[node->next]));
381    return TRex_False;
382}
383
384static const TRexChar *trex_matchnode(TRex* exp,TRexNode *node,const TRexChar *str,TRexNode *next)
385{
386   
387    TRexNodeType type = node->type;
388    switch(type) {
389    case OP_GREEDY: {
390        //TRexNode *greedystop = (node->next != -1) ? &exp->_nodes[node->next] : NULL;
391        TRexNode *greedystop = NULL;
392        int p0 = (node->right >> 16)&0x0000FFFF, p1 = node->right&0x0000FFFF, nmaches = 0;
393        const TRexChar *s=str, *good = str;
394
395        if(node->next != -1) {
396            greedystop = &exp->_nodes[node->next];
397        }
398        else {
399            greedystop = next;
400        }
401
402        while((nmaches == 0xFFFF || nmaches < p1)) {
403
404            const TRexChar *stop;
405            if(!(s = trex_matchnode(exp,&exp->_nodes[node->left],s,greedystop)))
406                break;
407            nmaches++;
408            good=s;
409            if(greedystop) {
410                //checks that 0 matches satisfy the expression(if so skips)
411                //if not would always stop(for instance if is a '?')
412                if(greedystop->type != OP_GREEDY ||
413                (greedystop->type == OP_GREEDY && ((greedystop->right >> 16)&0x0000FFFF) != 0))
414                {
415                    TRexNode *gnext = NULL;
416                    if(greedystop->next != -1) {
417                        gnext = &exp->_nodes[greedystop->next];
418                    }else if(next && next->next != -1){
419                        gnext = &exp->_nodes[next->next];
420                    }
421                    stop = trex_matchnode(exp,greedystop,s,gnext);
422                    if(stop) {
423                        //if satisfied stop it
424                        if(p0 == p1 && p0 == nmaches) break;
425                        else if(nmaches >= p0 && p1 == 0xFFFF) break;
426                        else if(nmaches >= p0 && nmaches <= p1) break;
427                    }
428                }
429            }
430           
431            if(s >= exp->_eol)
432                break;
433        }
434        if(p0 == p1 && p0 == nmaches) return good;
435        else if(nmaches >= p0 && p1 == 0xFFFF) return good;
436        else if(nmaches >= p0 && nmaches <= p1) return good;
437        return NULL;
438    }
439    case OP_OR: {
440            const TRexChar *asd = str;
441            TRexNode *temp=&exp->_nodes[node->left];
442            while( (asd = trex_matchnode(exp,temp,asd,NULL)) ) {
443                if(temp->next != -1)
444                    temp = &exp->_nodes[temp->next];
445                else
446                    return asd;
447            }
448            asd = str;
449            temp = &exp->_nodes[node->right];
450            while( (asd = trex_matchnode(exp,temp,asd,NULL)) ) {
451                if(temp->next != -1)
452                    temp = &exp->_nodes[temp->next];
453                else
454                    return asd;
455            }
456            return NULL;
457            break;
458    }
459    case OP_EXPR:
460    case OP_NOCAPEXPR:{
461            TRexNode *n = &exp->_nodes[node->left];
462            const TRexChar *cur = str;
463            int capture = -1;
464            if(node->type != OP_NOCAPEXPR && node->right == exp->_currsubexp) {
465                capture = exp->_currsubexp;
466                exp->_matches[capture].begin = cur;
467                exp->_currsubexp++;
468            }
469           
470            do {
471                TRexNode *subnext = NULL;
472                if(n->next != -1) {
473                    subnext = &exp->_nodes[n->next];
474                }else {
475                    subnext = next;
476                }
477                if(!(cur = trex_matchnode(exp,n,cur,subnext))) {
478                    if(capture != -1){
479                        exp->_matches[capture].begin = 0;
480                        exp->_matches[capture].len = 0;
481                    }
482                    return NULL;
483                }
484            } while((n->next != -1) && (n = &exp->_nodes[n->next]));
485
486            if(capture != -1) 
487                exp->_matches[capture].len = cur - exp->_matches[capture].begin;
488            return cur;
489    }               
490    case OP_WB:
491        if((str == exp->_bol && !isspace(*str))
492         || (str == exp->_eol && !isspace(*(str-1)))
493         || (!isspace(*str) && isspace(*(str+1)))
494         || (isspace(*str) && !isspace(*(str+1))) ) {
495            return (node->left == 'b')?str:NULL;
496        }
497        return (node->left == 'b')?NULL:str;
498    case OP_BOL:
499        if(str == exp->_bol) return str;
500        return NULL;
501    case OP_EOL:
502        if(str == exp->_eol) return str;
503        return NULL;
504    case OP_DOT:{
505        str++;
506                }
507        return str;
508    case OP_NCLASS:
509    case OP_CLASS:
510        if(trex_matchclass(exp,&exp->_nodes[node->left],*str)?(type == OP_CLASS?TRex_True:TRex_False):(type == OP_NCLASS?TRex_True:TRex_False)) {
511            str++;
512            return str;
513        }
514        return NULL;
515    case OP_CCLASS:
516        if(trex_matchcclass(node->left,*str)) {
517            str++;
518            return str;
519        }
520        return NULL;
521    default: /* char */
522        if(*str != node->type) return NULL;
523        str++;
524        return str;
525    }
526    return NULL;
527}
528
529/* public api */
530TRex *trex_compile(const TRexChar *pattern,const TRexChar **error)
531{
532    TRex *exp = (TRex *)malloc(sizeof(TRex));
533    exp->_eol = exp->_bol = NULL;
534    exp->_p = pattern;
535    exp->_nallocated = (int)scstrlen(pattern) * sizeof(TRexChar);
536    exp->_nodes = (TRexNode *)malloc(exp->_nallocated * sizeof(TRexNode));
537    exp->_nsize = 0;
538    exp->_matches = 0;
539    exp->_nsubexpr = 0;
540    exp->_first = trex_newnode(exp,OP_EXPR);
541    exp->_error = error;
542    exp->_jmpbuf = malloc(sizeof(jmp_buf));
543    if(setjmp(*((jmp_buf*)exp->_jmpbuf)) == 0) {
544        int res = trex_list(exp);
545        exp->_nodes[exp->_first].left = res;
546        if(*exp->_p!='\0')
547            trex_error(exp,_SC("unexpected character"));
548#ifdef _DEBUG
549        {
550            int nsize,i;
551            TRexNode *t;
552            nsize = exp->_nsize;
553            t = &exp->_nodes[0];
554            scprintf(_SC("\n"));
555            for(i = 0;i < nsize; i++) {
556                if(exp->_nodes[i].type>MAX_CHAR)
557                    scprintf(_SC("[%02d] %10s "),i,g_nnames[exp->_nodes[i].type-MAX_CHAR]);
558                else
559                    scprintf(_SC("[%02d] %10c "),i,exp->_nodes[i].type);
560                scprintf(_SC("left %02d right %02d next %02d\n"),exp->_nodes[i].left,exp->_nodes[i].right,exp->_nodes[i].next);
561            }
562            scprintf(_SC("\n"));
563        }
564#endif
565        exp->_matches = (TRexMatch *) malloc(exp->_nsubexpr * sizeof(TRexMatch));
566        memset(exp->_matches,0,exp->_nsubexpr * sizeof(TRexMatch));
567    }
568    else{
569        trex_free(exp);
570        return NULL;
571    }
572    return exp;
573}
574
575void trex_free(TRex *exp)
576{
577    if(exp) {
578        if(exp->_nodes) free(exp->_nodes);
579        if(exp->_jmpbuf) free(exp->_jmpbuf);
580        if(exp->_matches) free(exp->_matches);
581        free(exp);
582    }
583}
584
585TRexBool trex_match(TRex* exp,const TRexChar* text)
586{
587    const TRexChar* res = NULL;
588    exp->_bol = text;
589    exp->_eol = text + scstrlen(text);
590    exp->_currsubexp = 0;
591    res = trex_matchnode(exp,exp->_nodes,text,NULL);
592    if(res == NULL || res != exp->_eol)
593        return TRex_False;
594    return TRex_True;
595}
596
597TRexBool trex_searchrange(TRex* exp,const TRexChar* text_begin,const TRexChar* text_end,const TRexChar** out_begin, const TRexChar** out_end)
598{
599    const TRexChar *cur = NULL;
600    int node = exp->_first;
601    if(text_begin >= text_end) return TRex_False;
602    exp->_bol = text_begin;
603    exp->_eol = text_end;
604    do {
605        cur = text_begin;
606        while(node != -1) {
607            exp->_currsubexp = 0;
608            cur = trex_matchnode(exp,&exp->_nodes[node],cur,NULL);
609            if(!cur)
610                break;
611            node = exp->_nodes[node].next;
612        }
613        text_begin++;
614    } while(cur == NULL && text_begin != text_end);
615
616    if(cur == NULL)
617        return TRex_False;
618
619    --text_begin;
620
621    if(out_begin) *out_begin = text_begin;
622    if(out_end) *out_end = cur;
623    return TRex_True;
624}
625
626TRexBool trex_search(TRex* exp,const TRexChar* text, const TRexChar** out_begin, const TRexChar** out_end)
627{
628    return trex_searchrange(exp,text,text + scstrlen(text),out_begin,out_end);
629}
630
631int trex_getsubexpcount(TRex* exp)
632{
633    return exp->_nsubexpr;
634}
635
636TRexBool trex_getsubexp(TRex* exp, int n, TRexMatch *subexp)
637{
638    if( n<0 || n >= exp->_nsubexpr) return TRex_False;
639    *subexp = exp->_matches[n];
640    return TRex_True;
641}
642
Note: See TracBrowser for help on using the browser.