1
/* Copyright (C) 1995, 1996 Tom Lord
3
* This program is free software; you can redistribute it and/or modify
4
* it under the terms of the GNU Library General Public License as published by
5
* the Free Software Foundation; either version 2, or (at your option)
8
* This program is distributed in the hope that it will be useful,
9
* but WITHOUT ANY WARRANTY; without even the implied warranty of
10
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
* GNU Library General Public License for more details.
13
* You should have received a copy of the GNU Library General Public License
14
* along with this software; see the file COPYING. If not, write to
15
* the Free Software Foundation, 59 Temple Place - Suite 330,
16
* Boston, MA 02111-1307, USA.
31
rx_posix_analyze_rexp (struct rexp_node *** subexps,
33
struct rexp_node * node,
37
rx_posix_analyze_rexp (subexps, re_nsub, node, id)
38
struct rexp_node *** subexps;
40
struct rexp_node * node;
47
if (node->type == r_parens)
49
if (node->params.intval >= 0)
51
this_subexp = *re_nsub;
54
*subexps = (struct rexp_node **)malloc (sizeof (struct rexp_node *) * *re_nsub);
56
*subexps = (struct rexp_node **)realloc (*subexps,
57
sizeof (struct rexp_node *) * *re_nsub);
60
if (node->params.pair.left)
61
id = rx_posix_analyze_rexp (subexps, re_nsub, node->params.pair.left, id);
62
if (node->params.pair.right)
63
id = rx_posix_analyze_rexp (subexps, re_nsub, node->params.pair.right, id);
71
node->len = node->params.cstr.len;
83
lob = (!node->params.pair.left ? 0 : node->params.pair.left->observed);
84
rob = (!node->params.pair.right ? 0 : node->params.pair.right->observed);
85
llen = (!node->params.pair.left ? 0 : node->params.pair.left->len);
86
rlen = (!node->params.pair.right ? 0 : node->params.pair.right->len);
87
node->len = ((llen >= 0) && (rlen >= 0)
88
? ((node->type == r_concat)
90
: ((llen == rlen) ? llen : -1))
92
node->observed = lob || rob;
99
node->observed = (node->params.pair.left
100
? node->params.pair.left->observed
110
if (node->params.intval >= 0)
113
(*subexps)[this_subexp] = node;
116
node->observed = (node->params.pair.left
117
? node->params.pair.left->observed
119
node->len = (node->params.pair.left
120
? node->params.pair.left->len
124
switch (node->params.intval)
152
/* Returns 0 unless the pattern can match the empty string. */
155
rx_fill_in_fastmap (int cset_size, unsigned char * map, struct rexp_node * exp)
158
rx_fill_in_fastmap (cset_size, map, exp)
161
struct rexp_node * exp;
169
for (x = 0; x < cset_size; ++x)
182
most = exp->params.cset_size;
183
for (x = 0; x < most; ++x)
184
if (RX_bitset_member (exp->params.cset, x))
190
if (exp->params.cstr.len)
192
map[exp->params.cstr.contents[0]] = 1;
203
return rx_fill_in_fastmap (cset_size, map, exp->params.pair.left);
205
/* Why not the right branch? If the left branch
206
* can't be empty it doesn't matter. If it can, then
207
* the fastmap is already saturated, and again, the
208
* right branch doesn't matter.
213
return ( rx_fill_in_fastmap (cset_size, map, exp->params.pair.left)
214
| rx_fill_in_fastmap (cset_size, map, exp->params.pair.right));
218
return rx_fill_in_fastmap (cset_size, map, exp->params.pair.left);
222
goto can_match_empty;
223
/* Why not the subtree? These operators already saturate
228
if (exp->params.intval == 0)
229
goto can_match_empty;
231
return rx_fill_in_fastmap (cset_size, map, exp->params.pair.left);
234
goto can_match_empty;
237
/* this should never happen but gcc seems to like it */
245
rx_is_anchored_p (struct rexp_node * exp)
248
rx_is_anchored_p (exp)
249
struct rexp_node * exp;
267
return rx_is_anchored_p (exp->params.pair.left);
270
return ( rx_is_anchored_p (exp->params.pair.left)
271
&& rx_is_anchored_p (exp->params.pair.right));
275
if (exp->params.intval == 0)
278
return rx_is_anchored_p (exp->params.pair.left);
281
return (exp->params.intval == '^');
284
/* this should never happen but gcc seems to like it */
292
rx_start_superstate (struct rx_classical_system * frame)
295
rx_start_superstate (frame)
296
struct rx_classical_system * frame;
299
struct rx_superset * start_contents;
300
struct rx_nfa_state_set * start_nfa_set;
302
if (frame->rx->start_set)
303
start_contents = frame->rx->start_set;
307
struct rx_possible_future * futures;
308
futures = rx_state_possible_futures (frame->rx, frame->rx->start_nfa_states);
314
return rx_start_state_with_too_many_futures;
316
start_nfa_set = futures->destset;
320
rx_superstate_eclosure_union (frame->rx,
321
rx_superset_cons (frame->rx, 0, 0),
327
start_contents->starts_for = frame->rx;
328
frame->rx->start_set = start_contents;
331
if ( start_contents->superstate
332
&& (start_contents->superstate->rx_id == frame->rx->rx_id))
336
rx_unlock_superstate (frame->rx, frame->state);
338
frame->state = start_contents->superstate;
339
/* The cached superstate may be in a semifree state.
340
* We need to lock it and preserve the invariant
341
* that a locked superstate is never semifree.
344
rx_refresh_this_superstate (frame->rx->cache, frame->state);
345
rx_lock_superstate (frame->rx, frame->state);
350
struct rx_superstate * state;
352
rx_protect_superset (frame->rx, start_contents);
353
state = rx_superstate (frame->rx, start_contents);
354
rx_release_superset (frame->rx, start_contents);
359
rx_unlock_superstate (frame->rx, frame->state);
361
frame->state = state;
362
rx_lock_superstate (frame->rx, frame->state);
372
rx_fit_p (struct rx_classical_system * frame, unsigned const char * burst, int len)
375
rx_fit_p (frame, burst, len)
376
struct rx_classical_system * frame;
377
unsigned const char * burst;
381
struct rx_inx * inx_table;
389
frame->final_tag = frame->state->contents->is_final;
390
return (frame->state->contents->is_final
395
inx_table = frame->state->transitions;
396
rx_unlock_superstate (frame->rx, frame->state);
400
struct rx_inx * next_table;
402
inx = inx_table + *burst;
403
next_table = (struct rx_inx *)inx->data;
406
struct rx_superstate * state;
407
state = ((struct rx_superstate *)
410
((struct rx_superstate *)0)->transitions)));
412
switch ((int)inx->inx)
415
/* RX_BACKTRACK means that we've reached the empty
416
* superstate, indicating that match can't succeed
423
/* Because the superstate NFA is lazily constructed,
424
* and in fact may erode from underneath us, we sometimes
425
* have to construct the next instruction from the hard way.
426
* This invokes one step in the lazy-conversion.
430
(frame->rx, state, *burst, inx->data_2);
437
next_table = (struct rx_inx *)inx->data;
441
/* No other instructions are legal here.
442
* (In particular, this function does not handle backtracking
443
* or the related instructions.)
450
inx_table = next_table;
454
if (inx->data_2) /* indicates a final superstate */
456
frame->final_tag = (int)inx->data_2;
457
frame->state = ((struct rx_superstate *)
460
((struct rx_superstate *)0)->transitions)));
461
rx_lock_superstate (frame->rx, frame->state);
464
frame->state = ((struct rx_superstate *)
467
((struct rx_superstate *)0)->transitions)));
468
rx_lock_superstate (frame->rx, frame->state);
477
rx_advance (struct rx_classical_system * frame, unsigned const char * burst, int len)
480
rx_advance (frame, burst, len)
481
struct rx_classical_system * frame;
482
unsigned const char * burst;
486
struct rx_inx * inx_table;
494
inx_table = frame->state->transitions;
495
rx_unlock_superstate (frame->rx, frame->state);
500
struct rx_inx * next_table;
502
inx = inx_table + *burst;
503
next_table = (struct rx_inx *)inx->data;
506
struct rx_superstate * state;
507
state = ((struct rx_superstate *)
510
((struct rx_superstate *)0)->transitions)));
512
switch ((int)inx->inx)
515
/* RX_BACKTRACK means that we've reached the empty
516
* superstate, indicating that match can't succeed
523
/* Because the superstate NFA is lazily constructed,
524
* and in fact may erode from underneath us, we sometimes
525
* have to construct the next instruction from the hard way.
526
* This invokes one step in the lazy-conversion.
530
(frame->rx, state, *burst, inx->data_2);
537
next_table = (struct rx_inx *)inx->data;
541
/* No other instructions are legal here.
542
* (In particular, this function does not handle backtracking
543
* or the related instructions.)
550
inx_table = next_table;
554
frame->state = ((struct rx_superstate *)
557
((struct rx_superstate *)0)->transitions)));
558
rx_lock_superstate (frame->rx, frame->state);
566
rx_advance_to_final (struct rx_classical_system * frame, unsigned const char * burst, int len)
569
rx_advance_to_final (frame, burst, len)
570
struct rx_classical_system * frame;
571
unsigned const char * burst;
576
struct rx_inx * inx_table;
577
struct rx_superstate * this_state;
584
frame->final_tag = frame->state->contents->is_final;
588
inx_table = frame->state->transitions;
592
this_state = frame->state;
597
struct rx_inx * next_table;
599
/* this_state holds the state for the position we're
600
* leaving. this_state is locked.
602
inx = inx_table + *burst;
603
next_table = (struct rx_inx *)inx->data;
607
struct rx_superstate * state;
609
state = ((struct rx_superstate *)
612
((struct rx_superstate *)0)->transitions)));
614
switch ((int)inx->inx)
617
/* RX_BACKTRACK means that we've reached the empty
618
* superstate, indicating that match can't succeed
621
* Return to the state for the position prior to what
622
* we failed at, and return that position.
624
frame->state = this_state;
625
frame->final_tag = this_state->contents->is_final;
626
return (initial_len - len) - 1;
629
/* Because the superstate NFA is lazily constructed,
630
* and in fact may erode from underneath us, we sometimes
631
* have to construct the next instruction from the hard way.
632
* This invokes one step in the lazy-conversion.
634
inx = rx_handle_cache_miss
635
(frame->rx, state, *burst, inx->data_2);
639
rx_unlock_superstate (frame->rx, this_state);
643
next_table = (struct rx_inx *)inx->data;
647
/* No other instructions are legal here.
648
* (In particular, this function does not handle backtracking
649
* or the related instructions.)
652
rx_unlock_superstate (frame->rx, this_state);
658
/* Release the superstate for the preceeding position: */
659
rx_unlock_superstate (frame->rx, this_state);
661
/* Compute the superstate for the new position: */
662
inx_table = next_table;
663
this_state = ((struct rx_superstate *)
666
((struct rx_superstate *)0)->transitions)));
668
/* Lock it (see top-of-loop invariant): */
669
rx_lock_superstate (frame->rx, this_state);
671
/* Check to see if we should stop: */
672
if (this_state->contents->is_final)
674
frame->final_tag = this_state->contents->is_final;
675
frame->state = this_state;
676
return (initial_len - len);
682
/* Consumed all of the characters. */
683
frame->state = this_state;
684
frame->final_tag = this_state->contents->is_final;
686
/* state already locked (see top-of-loop invariant) */
695
rx_terminate_system (struct rx_classical_system * frame)
698
rx_terminate_system (frame)
699
struct rx_classical_system * frame;
704
rx_unlock_superstate (frame->rx, frame->state);
719
rx_init_system (struct rx_classical_system * frame, struct rx * rx)
722
rx_init_system (frame, rx)
723
struct rx_classical_system * frame;
added
removed
lib/common_test/priv/rx-1.5/rx/rxanal.c
