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
;