Branch data Line data Source code
1 : : // $Id: RE.cc 6219 2008-10-01 05:39:07Z vern $
2 : : //
3 : : // See the file "COPYING" in the main distribution directory for copyright.
4 : :
5 : : #include "config.h"
6 : :
7 : : #include <stdlib.h>
8 : :
9 : : #include "RE.h"
10 : : #include "DFA.h"
11 : : #include "CCL.h"
12 : : #include "EquivClass.h"
13 : : #include "Serializer.h"
14 : :
15 : : CCL* curr_ccl = 0;
16 : :
17 : : Specific_RE_Matcher* rem;
18 : : NFA_Machine* nfa = 0;
19 : : int case_insensitive = 0;
20 : :
21 : : extern int RE_parse(void);
22 : : extern void RE_set_input(const char* str);
23 : :
24 : : // If true, the set-wise matching always returns false - for benchmarking.
25 : : extern int rule_bench;
26 : :
27 : 444 : Specific_RE_Matcher::Specific_RE_Matcher(match_type arg_mt, int arg_multiline)
28 : 444 : : equiv_class(NUM_SYM)
29 : : {
30 : 444 : mt = arg_mt;
31 : 444 : multiline = arg_multiline;
32 : 444 : any_ccl = 0;
33 : 444 : pattern_text = 0;
34 : 444 : dfa = 0;
35 : 444 : ecs = 0;
36 : 444 : accepted = new AcceptingSet();
37 : 444 : }
38 : :
39 : 4 : Specific_RE_Matcher::~Specific_RE_Matcher()
40 : : {
41 [ + + ][ # # ]: 48 : for ( int i = 0; i < ccl_list.length(); ++i )
42 [ + - ][ # # ]: 44 : delete ccl_list[i];
43 : :
44 : 4 : Unref(dfa);
45 [ + - # # ]: 4 : delete [] pattern_text;
46 [ + - ][ # # ]: 4 : delete accepted;
47 : 4 : }
48 : :
49 : 1385 : CCL* Specific_RE_Matcher::AnyCCL()
50 : : {
51 [ + + ]: 1385 : if ( ! any_ccl )
52 : : { // Create the '.' character class.
53 : 305 : any_ccl = new CCL();
54 [ + - ]: 305 : if ( ! multiline )
55 : 305 : any_ccl->Add('\n');
56 : 305 : any_ccl->Negate();
57 : 305 : EC()->CCL_Use(any_ccl);
58 : : }
59 : :
60 : 1385 : return any_ccl;
61 : : }
62 : :
63 : 444 : void Specific_RE_Matcher::ConvertCCLs()
64 : : {
65 [ + + ]: 1513 : for ( int i = 0; i < ccl_list.length(); ++i )
66 : 1069 : equiv_class.ConvertCCL(ccl_list[i]);
67 : 444 : }
68 : :
69 : 1266 : void Specific_RE_Matcher::AddPat(const char* new_pat)
70 : : {
71 [ + + ]: 1266 : if ( mt == MATCH_EXACTLY )
72 : 633 : AddExactPat(new_pat);
73 : : else
74 : 633 : AddAnywherePat(new_pat);
75 : 1266 : }
76 : :
77 : 633 : void Specific_RE_Matcher::AddAnywherePat(const char* new_pat)
78 : : {
79 : 633 : AddPat(new_pat, "^?(.|\\n)*(%s)", "(%s)|(^?(.|\\n)*(%s))");
80 : 633 : }
81 : :
82 : 633 : void Specific_RE_Matcher::AddExactPat(const char* new_pat)
83 : : {
84 : 633 : AddPat(new_pat, "^?(%s)$?", "(%s)|(^?(%s)$?)");
85 : 633 : }
86 : :
87 : : void Specific_RE_Matcher::AddPat(const char* new_pat,
88 : 1266 : const char* orig_fmt, const char* app_fmt)
89 : : {
90 : 1266 : int n = strlen(new_pat);
91 : :
92 [ + + ]: 1266 : if ( pattern_text )
93 : 822 : n += strlen(pattern_text) + strlen(app_fmt);
94 : : else
95 : 444 : n += strlen(orig_fmt);
96 : :
97 : 1266 : char* s = new char[n + 5 /* slop */];
98 : :
99 [ + + ]: 1266 : if ( pattern_text )
100 : 822 : sprintf(s, app_fmt, pattern_text, new_pat);
101 : : else
102 : 444 : sprintf(s, orig_fmt, new_pat);
103 : :
104 [ + + ]: 1266 : delete [] pattern_text;
105 : 1266 : pattern_text = s;
106 : 1266 : }
107 : :
108 : 444 : int Specific_RE_Matcher::Compile(int lazy)
109 : : {
110 [ - + ]: 444 : if ( ! pattern_text )
111 : 0 : return 0;
112 : :
113 : 444 : rem = this;
114 : 444 : RE_set_input(pattern_text);
115 [ - + ]: 444 : if ( RE_parse() )
116 : : {
117 : 0 : run_time("error compiling pattern /%s/", pattern_text);
118 : 0 : return 0;
119 : : }
120 : :
121 : 444 : EC()->BuildECs();
122 : 444 : ConvertCCLs();
123 : :
124 : 888 : dfa = new DFA_Machine(nfa, EC());
125 : :
126 : 444 : Unref(nfa);
127 : 444 : nfa = 0;
128 : :
129 : 444 : ecs = EC()->EquivClasses();
130 : :
131 : 444 : return 1;
132 : : }
133 : :
134 : 0 : int Specific_RE_Matcher::CompileSet(const string_list& set, const int_list& idx)
135 : : {
136 [ # # ]: 0 : if ( set.length() != idx.length() )
137 : 0 : internal_error("compileset: lengths of sets differ");
138 : :
139 : 0 : rem = this;
140 : :
141 : 0 : NFA_Machine* set_nfa = 0;
142 : :
143 [ # # ]: 0 : loop_over_list(set, i)
144 : : {
145 : 0 : RE_set_input(set[i]);
146 [ # # ]: 0 : if ( RE_parse() )
147 : : {
148 : 0 : run_time("error compiling pattern /%s/", set[i]);
149 : 0 : return 0;
150 : : }
151 : :
152 : 0 : nfa->FinalState()->SetAccept(idx[i]);
153 [ # # ]: 0 : set_nfa = set_nfa ? make_alternate(nfa, set_nfa) : nfa;
154 : : }
155 : :
156 : : // Prefix the expression with a "^?".
157 : 0 : nfa = new NFA_Machine(new NFA_State(SYM_BOL, rem->EC()));
158 : 0 : nfa->MakeOptional();
159 [ # # ]: 0 : if ( set_nfa )
160 : 0 : nfa->AppendMachine( set_nfa );
161 : :
162 : 0 : EC()->BuildECs();
163 : 0 : ConvertCCLs();
164 : :
165 : 0 : dfa = new DFA_Machine(nfa, EC());
166 : 0 : ecs = EC()->EquivClasses();
167 : :
168 : 0 : return 1;
169 : : }
170 : :
171 : 0 : const char* Specific_RE_Matcher::LookupDef(const char* def)
172 : : {
173 : 0 : return defs.Lookup(def);
174 : : }
175 : :
176 : 0 : int Specific_RE_Matcher::MatchAll(const char* s)
177 : : {
178 : 0 : return MatchAll((const u_char*)(s), strlen(s));
179 : : }
180 : :
181 : 8 : int Specific_RE_Matcher::MatchAll(const BroString* s)
182 : : {
183 : : // s->Len() does not include '\0'.
184 : 8 : return MatchAll(s->Bytes(), s->Len());
185 : : }
186 : :
187 : 0 : int Specific_RE_Matcher::Match(const char* s)
188 : : {
189 : 0 : return Match((const u_char*)(s), strlen(s));
190 : : }
191 : :
192 : 2204 : int Specific_RE_Matcher::Match(const BroString* s)
193 : : {
194 : 2204 : return Match(s->Bytes(), s->Len());
195 : : }
196 : :
197 : 3400 : int Specific_RE_Matcher::LongestMatch(const char* s)
198 : : {
199 : 3400 : return LongestMatch((const u_char*)(s), strlen(s));
200 : : }
201 : :
202 : 0 : int Specific_RE_Matcher::LongestMatch(const BroString* s)
203 : : {
204 : 0 : return LongestMatch(s->Bytes(), s->Len());
205 : : }
206 : :
207 : 8 : int Specific_RE_Matcher::MatchAll(const u_char* bv, int n)
208 : : {
209 [ - + ]: 8 : if ( ! dfa )
210 : : // An empty pattern matches "all" iff what's being
211 : : // matched is empty.
212 : 0 : return n == 0;
213 : :
214 : 8 : DFA_State_Handle* d = dfa->StartState();
215 : 8 : d = (*d)->Xtion(ecs[SYM_BOL], dfa);
216 : :
217 [ + + ]: 16 : while ( d )
218 : : {
219 [ - + ]: 8 : if ( --n < 0 )
220 : 0 : break;
221 : :
222 : 8 : int ec = ecs[*(bv++)];
223 : 8 : d = (*d)->Xtion(ec, dfa);
224 : : }
225 : :
226 [ - + ]: 8 : if ( d )
227 : 0 : d = (*d)->Xtion(ecs[SYM_EOL], dfa);
228 : :
229 [ - + ][ # # ]: 8 : return d && (*d)->Accept() != 0;
230 : : }
231 : :
232 : :
233 : 2204 : int Specific_RE_Matcher::Match(const u_char* bv, int n)
234 : : {
235 [ - + ]: 2204 : if ( ! dfa )
236 : : // An empty pattern matches anything.
237 : 0 : return 1;
238 : :
239 : 2204 : DFA_State_Handle* d = dfa->StartState();
240 : :
241 : 2204 : d = (*d)->Xtion(ecs[SYM_BOL], dfa);
242 [ - + ]: 2204 : if ( ! d ) return 0;
243 : :
244 [ + + ]: 242384 : for ( int i = 0; i < n; ++i )
245 : : {
246 : 240180 : int ec = ecs[bv[i]];
247 : 240180 : d = (*d)->Xtion(ec, dfa);
248 [ - + ]: 240180 : if ( ! d )
249 : 0 : break;
250 : :
251 [ - + ]: 240180 : if ( (*d)->Accept() )
252 : 0 : return i + 1;
253 : : }
254 : :
255 [ + - ]: 2204 : if ( d )
256 : : {
257 : 2204 : d = (*d)->Xtion(ecs[SYM_EOL], dfa);
258 [ - + # # ]: 2204 : if ( d && (*d)->Accept() )
[ - + ]
259 : 0 : return n > 0 ? n : 1; // we can't return 0 here for match...
260 : : }
261 : :
262 : 2204 : return 0;
263 : : }
264 : :
265 : :
266 : 0 : void Specific_RE_Matcher::Dump(FILE* f)
267 : : {
268 : 0 : dfa->Dump(f);
269 : 0 : }
270 : :
271 : 0 : RE_Match_State::~RE_Match_State()
272 : : {
273 [ # # ][ # # ]: 0 : if ( current_state )
274 : 0 : StateUnref(current_state);
275 : 0 : }
276 : :
277 : : bool RE_Match_State::Match(const u_char* bv, int n,
278 : 0 : bool bol, bool eol, bool clear)
279 : : {
280 [ # # ]: 0 : if ( rule_bench > 0 )
281 : 0 : return false;
282 : :
283 [ # # ]: 0 : if ( current_pos == -1 )
284 : : {
285 : : // First call to Match().
286 [ # # ]: 0 : if ( ! dfa )
287 : 0 : return false;
288 : :
289 : : // Initialize state and copy the accepting states of the start
290 : : // state into the acceptance set.
291 : 0 : current_state = dfa->StartState();
292 : 0 : StateRef(current_state);
293 : :
294 : 0 : const AcceptingSet* ac = (*current_state)->Accept();
295 [ # # ]: 0 : if ( ac )
296 : : {
297 [ # # ]: 0 : loop_over_list(*ac, i)
298 : : {
299 : 0 : accepted.append((*ac)[i]);
300 : 0 : match_pos.append(0);
301 : : }
302 : : }
303 : : }
304 : :
305 [ # # ]: 0 : else if ( clear )
306 : : {
307 [ # # ]: 0 : if ( current_state )
308 : 0 : StateUnref(current_state);
309 : :
310 : 0 : current_state = dfa->StartState();
311 : 0 : StateRef(current_state);
312 : : }
313 : :
314 [ # # ]: 0 : if ( ! current_state )
315 : 0 : return false;
316 : :
317 : : else
318 : 0 : (*current_state)->Unlock();
319 : :
320 : 0 : current_pos = 0;
321 : :
322 : 0 : int old_matches = accepted.length();
323 : :
324 : : int ec;
325 [ # # ]: 0 : int m = bol ? n + 1 : n;
326 [ # # ]: 0 : int e = eol ? -1 : 0;
327 : :
328 [ # # ]: 0 : while ( --m >= e )
329 : : {
330 [ # # ]: 0 : if ( m == n )
331 : 0 : ec = ecs[SYM_BOL];
332 [ # # ]: 0 : else if ( m == -1 )
333 : 0 : ec = ecs[SYM_EOL];
334 : : else
335 : 0 : ec = ecs[*(bv++)];
336 : :
337 : 0 : DFA_State_Handle* next_state = (*current_state)->Xtion(ec,dfa);
338 : :
339 [ # # ]: 0 : if ( ! next_state )
340 : : {
341 : 0 : current_state = 0;
342 : 0 : break;
343 : : }
344 : :
345 [ # # ]: 0 : if ( (*next_state)->Accept() )
346 : : {
347 : 0 : const AcceptingSet* ac = (*next_state)->Accept();
348 [ # # ]: 0 : loop_over_list(*ac, i)
349 : : {
350 [ # # ]: 0 : if ( ! accepted.is_member((*ac)[i]) )
351 : : {
352 : 0 : accepted.append((*ac)[i]);
353 : 0 : match_pos.append(current_pos);
354 : : }
355 : : }
356 : : }
357 : :
358 : 0 : ++current_pos;
359 : :
360 : 0 : StateRef(next_state);
361 : 0 : StateUnref(current_state);
362 : 0 : current_state = next_state;
363 : : }
364 : :
365 : : // Make sure our state doesn't expire until we return.
366 [ # # ]: 0 : if ( current_state )
367 : 0 : (*current_state)->Lock();
368 : :
369 : 0 : return accepted.length() != old_matches;
370 : : }
371 : :
372 : 4489 : int Specific_RE_Matcher::LongestMatch(const u_char* bv, int n)
373 : : {
374 [ - + ]: 4489 : if ( ! dfa )
375 : : // An empty pattern matches anything.
376 : 0 : return 0;
377 : :
378 : : // Use -1 to indicate no match.
379 : 4489 : int last_accept = -1;
380 : 4489 : DFA_State_Handle* d = dfa->StartState();
381 : :
382 : 4489 : d = (*d)->Xtion(ecs[SYM_BOL], dfa);
383 [ - + ]: 4489 : if ( ! d )
384 : 0 : return -1;
385 : :
386 [ - + ]: 4489 : if ( (*d)->Accept() )
387 : 0 : last_accept = 0;
388 : :
389 [ + + ]: 7466 : for ( int i = 0; i < n; ++i )
390 : : {
391 : 7151 : int ec = ecs[bv[i]];
392 : 7151 : d = (*d)->Xtion(ec, dfa);
393 : :
394 [ + + ]: 7151 : if ( ! d )
395 : 4174 : break;
396 : :
397 [ + + ]: 2977 : if ( (*d)->Accept() )
398 : 1577 : last_accept = i + 1;
399 : : }
400 : :
401 [ + + ]: 4489 : if ( d )
402 : : {
403 : 315 : d = (*d)->Xtion(ecs[SYM_EOL], dfa);
404 [ + + + - ]: 315 : if ( d && (*d)->Accept() )
[ + + ]
405 : 297 : return n;
406 : : }
407 : :
408 : 4489 : return last_accept;
409 : : }
410 : :
411 : 0 : unsigned int Specific_RE_Matcher::MemoryAllocation() const
412 : : {
413 : 0 : unsigned int size = 0;
414 : :
415 [ # # ]: 0 : for ( int i = 0; i < ccl_list.length(); ++i )
416 : 0 : size += ccl_list[i]->MemoryAllocation();
417 : :
418 : : return size + padded_sizeof(*this)
419 : : + (pattern_text ? pad_size(strlen(pattern_text) + 1) : 0)
420 : : + defs.MemoryAllocation() - padded_sizeof(defs) // FIXME: count content
421 : : + ccl_dict.MemoryAllocation() - padded_sizeof(ccl_dict) // FIXME: count content
422 : : + ccl_list.MemoryAllocation() - padded_sizeof(ccl_list)
423 : : + equiv_class.Size() - padded_sizeof(EquivClass)
424 : : + (dfa ? dfa->MemoryAllocation() : 0) // this is ref counted; consider the bytes here?
425 : : + padded_sizeof(*any_ccl)
426 [ # # ][ # # ]: 0 : + accepted->MemoryAllocation();
427 : : }
428 : :
429 : 0 : RE_Matcher::RE_Matcher()
430 : : {
431 : 0 : re_anywhere = new Specific_RE_Matcher(MATCH_ANYWHERE);
432 : 0 : re_exact = new Specific_RE_Matcher(MATCH_EXACTLY);
433 : 0 : }
434 : :
435 : 222 : RE_Matcher::RE_Matcher(const char* pat)
436 : : {
437 : 222 : re_anywhere = new Specific_RE_Matcher(MATCH_ANYWHERE);
438 : 222 : re_exact = new Specific_RE_Matcher(MATCH_EXACTLY);
439 : :
440 : 222 : AddPat(pat);
441 : 222 : }
442 : :
443 : 2 : RE_Matcher::~RE_Matcher()
444 : : {
445 [ + - ][ # # ]: 2 : delete re_anywhere;
[ # # ]
446 [ + - ][ # # ]: 2 : delete re_exact;
[ # # ]
447 [ + - ][ # # ]: 2 : }
[ # # ]
448 : :
449 : 633 : void RE_Matcher::AddPat(const char* new_pat)
450 : : {
451 : 633 : re_anywhere->AddPat(new_pat);
452 : 633 : re_exact->AddPat(new_pat);
453 : 633 : }
454 : :
455 : 222 : int RE_Matcher::Compile(int lazy)
456 : : {
457 [ + - ][ + - ]: 222 : return re_anywhere->Compile(lazy) && re_exact->Compile(lazy);
458 : : }
459 : :
460 : 0 : bool RE_Matcher::Serialize(SerialInfo* info) const
461 : : {
462 : 0 : return SerialObj::Serialize(info);
463 : : }
464 : :
465 : 0 : RE_Matcher* RE_Matcher::Unserialize(UnserialInfo* info)
466 : : {
467 : 0 : return (RE_Matcher*) SerialObj::Unserialize(info, SER_RE_MATCHER);
468 : : }
469 : :
470 : 3 : IMPLEMENT_SERIAL(RE_Matcher, SER_RE_MATCHER);
471 : :
472 : 0 : bool RE_Matcher::DoSerialize(SerialInfo* info) const
473 : : {
474 [ # # ][ # # ]: 0 : DO_SERIALIZE(SER_RE_MATCHER, SerialObj);
475 : : return SERIALIZE(re_anywhere->PatternText())
476 [ # # ][ # # ]: 0 : && SERIALIZE(re_exact->PatternText());
477 : : }
478 : :
479 : 0 : bool RE_Matcher::DoUnserialize(UnserialInfo* info)
480 : : {
481 [ # # ]: 0 : DO_UNSERIALIZE(SerialObj);
482 : :
483 : 0 : re_anywhere = new Specific_RE_Matcher(MATCH_ANYWHERE);
484 : 0 : re_exact = new Specific_RE_Matcher(MATCH_EXACTLY);
485 : :
486 : : const char* pat;
487 [ # # ]: 0 : if ( ! UNSERIALIZE_STR(&pat, 0) )
488 : 0 : return false;
489 : :
490 : 0 : re_anywhere->SetPat(pat);
491 [ # # ]: 0 : if ( ! re_anywhere->Compile() )
492 : : {
493 : 0 : info->s->Error(fmt("Can't compile regexp '%s'", pat));
494 : 0 : return false;
495 : : }
496 : :
497 [ # # ]: 0 : if ( ! UNSERIALIZE_STR(&pat, 0) )
498 : 0 : return false;
499 : :
500 : 0 : re_exact->SetPat(pat);
501 [ # # ]: 0 : if ( ! re_exact->Compile() )
502 : : {
503 : 0 : info->s->Error(fmt("Can't compile regexp '%s'", pat));
504 : 0 : return false;
505 : : }
506 : :
507 : 0 : return true;
508 : : }
509 : :
510 : :
511 : : static RE_Matcher* matcher_merge(const RE_Matcher* re1, const RE_Matcher* re2,
512 : 0 : const char* merge_op)
513 : : {
514 : 0 : const char* text1 = re1->PatternText();
515 : 0 : const char* text2 = re2->PatternText();
516 : :
517 : 0 : int n = strlen(text1) + strlen(text2) + strlen(merge_op) + 32 /* slop */ ;
518 : :
519 : 0 : char* merge_text = new char[n];
520 : 0 : safe_snprintf(merge_text, n, "(%s)%s(%s)", text1, merge_op, text2);
521 : :
522 : 0 : RE_Matcher* merge = new RE_Matcher(merge_text);
523 : 0 : delete merge_text;
524 : :
525 : 0 : merge->Compile();
526 : :
527 : 0 : return merge;
528 : : }
529 : :
530 : 0 : RE_Matcher* RE_Matcher_conjunction(const RE_Matcher* re1, const RE_Matcher* re2)
531 : : {
532 : 0 : return matcher_merge(re1, re2, "");
533 : : }
534 : :
535 : 0 : RE_Matcher* RE_Matcher_disjunction(const RE_Matcher* re1, const RE_Matcher* re2)
536 : : {
537 : 0 : return matcher_merge(re1, re2, "|");
538 [ + - ][ + - ]: 6 : }
|
