RPA Toolkit
ad713a56e0098da6bbd2e7b07fa06d539ffac26e
[rpatk.git] / rexgrep / rexgrep.c
1 /*
2  *  Regular Pattern Analyzer Toolkit (RPA/Tk)
3  *  Copyright (c) 2009-2012 Martin Stoilov
4  *
5  *  This program is free software: you can redistribute it and/or modify
6  *  it under the terms of the GNU General Public License as published by
7  *  the Free Software Foundation, either version 3 of the License, or
8  *  (at your option) any later version.
9  *
10  *  This program is distributed in the hope that it will be useful,
11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  *  GNU General Public License for more details.
14  *
15  *  You should have received a copy of the GNU General Public License
16  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
17  *
18  *  Martin Stoilov <martin@rpasearch.com>
19  */
20
21
22 #include <stdio.h>
23 #include <stdlib.h>
24 #include <string.h>
25 #include <time.h>
26
27 #include "rlib/rutf.h"
28 #include "rlib/rmem.h"
29 #include "rex/rextransition.h"
30 #include "rex/rexdfasimulator.h"
31 #include "rexgrep.h"
32 #include "rexgrepdep.h"
33
34 #define MAX_STACK 256000
35
36
37 rexgrep_t *rex_grep_create()
38 {
39         rexgrep_t *pGrep;
40         
41         pGrep = (rexgrep_t *)r_malloc(sizeof(*pGrep));
42         if (!pGrep)
43                 return (void *)0;
44         r_memset(pGrep, 0, sizeof(*pGrep));
45         pGrep->nfa = rex_db_create(REXDB_TYPE_NFA);
46         pGrep->si = rex_nfasimulator_create();
47         pGrep->dfasi = rex_dfasimulator_create();
48         pGrep->ret = 1;
49         pGrep->startuid = 0UL;
50         rex_db_setblanks_s(pGrep->nfa, "");
51         return pGrep;
52 }
53
54
55 void rex_grep_destroy(rexgrep_t *pGrep)
56 {
57         if (!pGrep)
58                 return;
59         rex_db_destroy(pGrep->nfa);
60         rex_dfa_destroy(pGrep->dfa);
61         rex_nfasimulator_destroy(pGrep->si);
62         rex_dfasimulator_destroy(pGrep->dfasi);
63         r_free(pGrep);
64 }
65
66
67 int rex_grep_load_string_pattern(rexgrep_t *pGrep, rbuffer_t *buf)
68 {
69         return rex_grep_load_pattern(pGrep, buf);
70 }
71
72
73 int rex_grep_load_pattern(rexgrep_t *pGrep, rbuffer_t *buf)
74 {
75         pGrep->startuid = rex_db_addexpression(pGrep->nfa, pGrep->startuid, buf->s, buf->size, 0);
76         if (pGrep->startuid < 0) {
77                 return -1;
78         }
79         return 0;
80 }
81
82
83 int rex_grep_nfamatch(rexgrep_t *pGrep, const char* input, const char *end)
84 {
85         int inc;
86         ruint32 wc;
87         rexdb_t *db = pGrep->nfa;
88
89         if (pGrep->startuid < 0) {
90                 return -1;
91         }
92         rex_nfasimulator_start(pGrep->si, db, pGrep->startuid);
93         while ((inc = r_utf8_mbtowc(&wc, (const unsigned char*)input, (const unsigned char*)end)) > 0) {
94                 if (rex_nfasimulator_next(pGrep->si, db, wc, inc) == 0)
95                         break;
96                 input += inc;
97         }
98         if (r_array_length(pGrep->si->accepts) > 0) {
99                 rex_accept_t *acc = (rex_accept_t *)r_array_lastslot(pGrep->si->accepts);
100                 return acc->inputsize;
101         }
102         return 0;
103 }
104
105
106 static int rex_grep_dfamatch(rexgrep_t *pGrep, const char* input, const char *end)
107 {
108         int inc;
109         ruint32 wc = 0;
110         int ret = 0;
111         long nstate = REX_DFA_STARTSTATE;
112         const char *start = input;
113         rexdfa_t *dfa = pGrep->dfa;
114         rexdfs_t *s;
115
116         while ((inc = r_utf8_mbtowc(&wc, (const unsigned char*)input, (const unsigned char*)end)) > 0) {
117                 REX_DFA_NEXT(dfa, nstate, wc, &nstate);
118                 if (nstate == 0)
119                         break;
120                 input += inc;
121                 s = REX_DFA_STATE(dfa, nstate);
122                 if (s->type == REX_STATETYPE_ACCEPT)
123                         ret = (int)(input - start);
124         }
125         return ret;
126 }
127
128
129 #define REX_GREP_SHIFT(__shift__, __count__, __bytes__, __bitsperbyte__, __shiftstart__, __end__) \
130 do { \
131         int inc, i; \
132         unsigned int mask = (1 << __bitsperbyte__) - 1; \
133         ruint32 wc = 0; \
134         for (i = 0; i < __count__; i++) { \
135                 wc = 0; \
136                 if (__shiftstart__ < __end__) { \
137                         wc = *(__shiftstart__); \
138                         inc = 1; \
139                         if (wc >= 0x80) { \
140                                 inc = r_utf8_mbtowc(&wc, (const unsigned char*)(__shiftstart__), (const unsigned char*)__end__); \
141                         } \
142                         __shiftstart__ += inc; \
143                 } \
144                 __shift__ <<= __bitsperbyte__; \
145                 __shift__ |= (wc & mask); \
146         } \
147         __shift__ = (__shift__ & REX_DFA_HASHMASK(__bytes__, __bitsperbyte__)); \
148 } while (0)
149
150
151 static int rex_grep_dfascan(rexgrep_t *pGrep, const char* start, const char* end, int alloutput)
152 {
153         int ret = 0;
154         unsigned int shifter = 0;
155         const char *nextshift = start;
156         const char *input = start;
157         rexdfa_t *dfa = pGrep->dfa;
158
159         nextshift = start;
160         REX_GREP_SHIFT(shifter, REX_HASH_BYTES, REX_HASH_BYTES, REX_HASH_BITS, nextshift, end);
161
162         while (input < end) {
163                 while ((ret = REX_BITARRAY_GET(dfa->bits, shifter)) == 0 && nextshift < end && ((unsigned char)*nextshift) < 0x80 && ((unsigned char)*input) < 0x80) {
164                         shifter <<= REX_HASH_BITS;
165                         shifter |= (((unsigned char)*nextshift) & ((1 << REX_HASH_BITS) - 1));
166                         shifter = (shifter & REX_DFA_HASHMASK(REX_HASH_BYTES, REX_HASH_BITS));
167                         nextshift += 1;
168                         input += 1;
169                         pGrep->scfiltered++;
170                 }
171                 if (ret)
172                         ret = rex_grep_dfamatch(pGrep, input, end);
173
174                 if (ret == 0) {
175                         ruint32 wc = *input;
176                         if (wc >= 0x80) {
177                                 ret = r_utf8_mbtowc(&wc, (const unsigned char*)input, (const unsigned char*)end);
178                                 if (ret <= 0)
179                                         ret = 1;
180                                 input += ret;
181                         } else {
182                                 input += 1;
183                         }
184
185                         if (nextshift < end && ((unsigned char)*nextshift) < 0x80) {
186                                 shifter <<= REX_HASH_BITS;
187                                 shifter |= (((unsigned char)*nextshift) & ((1 << REX_HASH_BITS) - 1));
188                                 shifter = (shifter & REX_DFA_HASHMASK(REX_HASH_BYTES, REX_HASH_BITS));
189                                 nextshift += 1;
190                         } else {
191                                 REX_GREP_SHIFT(shifter, 1, REX_HASH_BYTES, REX_HASH_BITS, nextshift, end);
192                         }
193                 } else if (ret > 0) {
194                         if (pGrep->showfilename) {
195                                 fprintf(stdout, "%s:", (const char*)pGrep->filename);
196                         }
197                         if (alloutput) {
198                                 fwrite(start, 1, end - start, stdout);
199                                 break;
200                         } else {
201                                 fwrite(input, 1, ret, stdout);
202                                 fprintf(stdout, "\n");
203                         }
204                         input += ret;
205                         shifter = 0;
206                         nextshift = input;
207                         REX_GREP_SHIFT(shifter, REX_HASH_BYTES, REX_HASH_BYTES, REX_HASH_BITS, nextshift, end);
208                 } else {
209                         /*
210                          * Error
211                          */
212                         return -1;
213                 }
214         }
215         return 0;
216 }
217
218
219 static int rex_grep_nfascan(rexgrep_t *pGrep, const char* start, const char* end, int alloutput)
220 {
221         int ret = 0;
222         const char *input = start;
223
224         while (input < end) {
225                 ret = rex_grep_nfamatch(pGrep, input, end);
226                 if (ret < 0) {
227                         /*
228                          * Error
229                          */
230                         return -1;
231                 } else if (ret > 0) {
232                         if (pGrep->showfilename) {
233                                 fprintf(stdout, "%s:", (const char*)pGrep->filename);
234                         }
235                         if (alloutput) {
236                                 fwrite(start, 1, end - start, stdout);
237                                 break;
238                         } else {
239                                 fwrite(input, 1, ret, stdout);
240                                 fprintf(stdout, "\n");
241                         }
242                         input += ret;
243                 } else {
244                         ruint32 wc;
245                         if ((ret = r_utf8_mbtowc(&wc, (const unsigned char*)input, (const unsigned char*)end)) <= 0)
246                                 ret = 1;
247                         input += ret;
248                 }
249         }
250         return 0;
251 }
252
253
254 static int rex_grep_dfascanlines(rexgrep_t *pGrep, const char* start, const char* end)
255 {
256         int ret;
257         const char *eol;
258
259         for (eol = start; eol < end; eol++) {
260                 if (*eol == '\n' || (eol + 1) == end) {
261                         ret = rex_grep_dfascan(pGrep, start, eol + 1, 1);
262                         if (ret < 0) {
263                                 /*
264                                  * Error
265                                  */
266                         }
267                         start = eol + 1;
268                 }
269         }
270         return 0;
271 }
272
273
274 static int rex_grep_nfascanlines(rexgrep_t *pGrep, const char* start, const char* end)
275 {
276         int ret;
277         const char *eol;
278
279         for (eol = start; eol < end; eol++) {
280                 if (*eol == '\n' || (eol + 1) == end) {
281                         ret = rex_grep_nfascan(pGrep, start, eol + 1, 1);
282                         if (ret < 0) {
283                                 /*
284                                  * Error
285                                  */
286                         }
287                         start = eol + 1;
288                 }
289         }
290         return 0;
291 }
292
293
294 void rex_grep_scan_buffer(rexgrep_t *pGrep, rbuffer_t *buf)
295 {
296         clock_t btime, scanclocks;
297         btime = clock();
298
299         switch (pGrep->greptype) {
300         case REX_GREPTYPE_SCANLINES:
301                 if (pGrep->usedfa) {
302                         rex_grep_dfascanlines(pGrep, buf->s, buf->s + buf->size);
303                 } else {
304                         rex_grep_nfascanlines(pGrep, buf->s, buf->s + buf->size);
305                 }
306                 break;
307         case REX_GREPTYPE_MATCH:
308         case REX_GREPTYPE_SCAN:
309         default:
310                 if (pGrep->usedfa) {
311                         rex_grep_dfascan(pGrep, buf->s, buf->s + buf->size, 0);
312                 }else {
313                         rex_grep_nfascan(pGrep, buf->s, buf->s + buf->size, 0);
314                 }
315                 break;
316         };
317         scanclocks = clock() - btime;
318         pGrep->scsize += buf->size;
319         pGrep->scanmilisec += (unsigned long)(((unsigned long long)1000)*scanclocks/CLOCKS_PER_SEC);
320 }
321
322
323 void rex_grep_output(rexgrep_t *pGrep, const char *s, unsigned long size, unsigned int encoding)
324 {
325         fwrite(s, 1, size, stdout);
326 }
327
328
329 void rex_grep_output_utf8_string(rexgrep_t *pGrep, const char *s)
330 {
331         rex_grep_output(pGrep, s, r_strlen(s), 0);
332 }
333