6 /* Copyright (C) 1995, 1996 Tom Lord
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU Library General Public License as published by
10 * the Free Software Foundation; either version 2, or (at your option)
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU Library General Public License for more details.
18 * You should have received a copy of the GNU Library General Public License
19 * along with this software; see the file COPYING. If not, write to
20 * the Free Software Foundation, 59 Temple Place - Suite 330,
21 * Boston, MA 02111-1307, USA.
26 #include <sys/types.h>
39 /* Suppose that from some NFA state and next character, more than one
40 * path through side-effect edges is possible. In what order should
41 * the paths be tried? A function of type rx_se_list_order answers
42 * that question. It compares two lists of side effects, and says
43 * which list comes first.
47 typedef int (*rx_se_list_order
) (struct rx
*,
51 typedef int (*rx_se_list_order
) ();
56 /* Struct RX holds an NFA and cache state for the corresponding super NFA.
60 /* The compiler assigns a unique id to every pattern.
61 * Like sequence numbers in X, there is a subtle bug here
62 * if you use Rx in a system that runs for a long time.
63 * But, because of the way the caches work out, it is almost
64 * impossible to trigger the Rx version of this bug.
66 * The id is used to validate superstates found in a cache
67 * of superstates. It isn't sufficient to let a superstate
68 * point back to the rx for which it was compiled -- the caller
69 * may be re-using a `struct rx' in which case the superstate
70 * is not really valid. So instead, superstates are validated
71 * by checking the sequence number of the pattern for which
76 /* This is memory mgt. state for superstates. This may be
77 * shared by more than one struct rx.
79 struct rx_cache
* cache
;
81 /* Every nfa defines the size of its own character set.
82 * Each superstate has an array of this size, with each element
83 * a `struct rx_inx'. So, don't make this number too large.
84 * In particular, don't make it 2^16.
88 /* Lists of side effects as stored in the NFA are `hash consed'..meaning
89 * that lists with the same elements are ==. During compilation,
90 * this table facilitates hash-consing.
92 struct rx_hash se_list_memo
;
94 /* Lists of NFA states are also hashed.
96 struct rx_hash set_list_memo
;
100 /* The compiler and matcher must build a number of instruction frames.
101 * The format of these frames is fixed (c.f. struct rx_inx). The values
102 * of the instruction opcodes is not fixed.
104 * An enumerated type (enum rx_opcode) defines the set of instructions
105 * that the compiler or matcher might generate. When filling an instruction
106 * frame, the INX field is found by indexing this instruction table
109 void ** instruction_table
;
111 /* The list of all states in an NFA.
112 * The NEXT field of NFA states links this list.
114 struct rx_nfa_state
*nfa_states
;
115 struct rx_nfa_state
*start_nfa_states
;
116 struct rx_superset
* start_set
;
118 /* This orders the search through super-nfa paths.
119 * See the comment near the typedef of rx_se_list_order.
121 rx_se_list_order se_list_cmp
;
128 /* If `regs_allocated' is REGS_UNALLOCATED in the pattern buffer,
129 * `re_match_2' returns information about at least this many registers
130 * the first time a `regs' structure is passed.
132 * Also, this is the greatest number of backreferenced subexpressions
133 * allowed in a pattern being matched without caller-supplied registers.
142 #define CHAR_SET_SIZE (1 << CHARBITS)
144 #define SYNTAX(c) re_syntax_table[c]
145 extern char re_syntax_table
[CHAR_SET_SIZE
];
149 /* Should we use malloc or alloca? If REGEX_MALLOC is not defined, we
150 * use `alloca' instead of `malloc' for the backtracking stack.
152 * Emacs will die miserably if we don't do this.
156 #define REGEX_ALLOCATE malloc
157 #else /* not REGEX_MALLOC */
158 #define REGEX_ALLOCATE alloca
159 #endif /* not REGEX_MALLOC */
163 #define MAX(a, b) ((a) > (b) ? (a) : (b))
164 #define MIN(a, b) ((a) < (b) ? (a) : (b))
165 extern void * rx_id_instruction_table
[];
166 extern struct rx_cache
* rx_default_cache
;