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;