[irc/evilnet/x3.git] / rx / _rx.h

/* classes: h_files */

#ifndef _RXH
#define _RXH

/*	Copyright (C) 1995, 1996 Tom Lord
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Library General Public License as published by
 * the Free Software Foundation; either version 2, or (at your option)
 * any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Library General Public License for more details.
 * 
 * You should have received a copy of the GNU Library General Public License
 * along with this software; see the file COPYING.  If not, write to
 * the Free Software Foundation, 59 Temple Place - Suite 330, 
 * Boston, MA 02111-1307, USA. 
 */

\f

#include <sys/types.h>
#include "rxhash.h"
#include "rxcset.h"

\f

struct rx_cache;
struct rx_superset;
struct rx;
struct rx_se_list;

\f

/* Suppose that from some NFA state and next character, more than one
 * path through side-effect edges is possible.  In what order should
 * the paths be tried?  A function of type rx_se_list_order answers
 * that question.  It compares two lists of side effects, and says
 * which list comes first.
 */
 
#ifdef __STDC__
typedef int (*rx_se_list_order) (struct rx *,
				 struct rx_se_list *, 
				 struct rx_se_list *);
#else
typedef int (*rx_se_list_order) ();
#endif


/* Struct RX holds an NFA and cache state for the corresponding super NFA.
 */
struct rx
{
  /* The compiler assigns a unique id to every pattern.
   * Like sequence numbers in X, there is a subtle bug here
   * if you use Rx in a system that runs for a long time.
   * But, because of the way the caches work out, it is almost
   * impossible to trigger the Rx version of this bug.
   *
   * The id is used to validate superstates found in a cache
   * of superstates.  It isn't sufficient to let a superstate
   * point back to the rx for which it was compiled -- the caller
   * may be re-using a `struct rx' in which case the superstate
   * is not really valid.  So instead, superstates are validated
   * by checking the sequence number of the pattern for which
   * they were built.
   */
  int rx_id;

  /* This is memory mgt. state for superstates.  This may be 
   * shared by more than one struct rx.
   */
  struct rx_cache * cache;

  /* Every nfa defines the size of its own character set. 
   * Each superstate has an array of this size, with each element
   * a `struct rx_inx'.  So, don't make this number too large.
   * In particular, don't make it 2^16.
   */
  int local_cset_size;

  /* Lists of side effects as stored in the NFA are `hash consed'..meaning
   * that lists with the same elements are ==.  During compilation, 
   * this table facilitates hash-consing.
   */
  struct rx_hash se_list_memo;

  /* Lists of NFA states are also hashed. 
   */
  struct rx_hash set_list_memo;


  /* The compiler and matcher must build a number of instruction frames.
   * The format of these frames is fixed (c.f. struct rx_inx).  The values
   * of the instruction opcodes is not fixed.
   *
   * An enumerated type (enum rx_opcode) defines the set of instructions
   * that the compiler or matcher might generate.  When filling an instruction
   * frame, the INX field is found by indexing this instruction table
   * with an opcode:
   */
  void ** instruction_table;

  /* The list of all states in an NFA.
   * The NEXT field of NFA states links this list.
   */
  struct rx_nfa_state *nfa_states;
  struct rx_nfa_state *start_nfa_states;
  struct rx_superset * start_set;

  /* This orders the search through super-nfa paths.
   * See the comment near the typedef of rx_se_list_order.
   */
  rx_se_list_order se_list_cmp;

  int next_nfa_id;
};


/* If `regs_allocated' is REGS_UNALLOCATED in the pattern buffer,
 * `re_match_2' returns information about at least this many registers
 * the first time a `regs' structure is passed. 
 *
 * Also, this is the greatest number of backreferenced subexpressions
 * allowed in a pattern being matched without caller-supplied registers.
 */
#ifndef RE_NREGS
#define RE_NREGS 30
#endif


#ifndef emacs
#define CHARBITS 8
#define CHAR_SET_SIZE (1 << CHARBITS)
#define Sword 1
#define SYNTAX(c) re_syntax_table[c]
extern char re_syntax_table[CHAR_SET_SIZE];
#endif


/* Should we use malloc or alloca?  If REGEX_MALLOC is not defined, we
 * use `alloca' instead of `malloc' for the backtracking stack.
 *
 * Emacs will die miserably if we don't do this.
 */

#ifdef REGEX_MALLOC
#define REGEX_ALLOCATE malloc
#else /* not REGEX_MALLOC  */
#define REGEX_ALLOCATE alloca
#endif /* not REGEX_MALLOC */

#undef MAX
#undef MIN
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
extern void * rx_id_instruction_table[];
extern struct rx_cache * rx_default_cache;

\f
#ifdef __STDC__

#else /* STDC */

#endif /* STDC */


#endif  /* _RXH */
Commit	Line	Data
d76ed9a9	1	/* classes: h_files */
	2
	3	#ifndef _RXH
	4	#define _RXH
	5
	6	/* Copyright (C) 1995, 1996 Tom Lord
	7	*
	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)
	11	* any later version.
	12	*
	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.
	17	*
	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.
	22	*/
	23
	24	\f
	25
	26	#include <sys/types.h>
	27	#include "rxhash.h"
	28	#include "rxcset.h"
	29
	30	\f
	31
	32	struct rx_cache;
	33	struct rx_superset;
	34	struct rx;
	35	struct rx_se_list;
	36
	37	\f
	38
	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.
	44	*/
	45
	46	#ifdef __STDC__
	47	typedef int (rx_se_list_order) (struct rx ,
	48	struct rx_se_list *,
	49	struct rx_se_list *);
	50	#else
	51	typedef int (*rx_se_list_order) ();
	52	#endif
	53
	54
	55
	56	/* Struct RX holds an NFA and cache state for the corresponding super NFA.
	57	*/
	58	struct rx
	59	{
	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.
65	*
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
72	* they were built.
73	*/
74	int rx_id;
75
76	/* This is memory mgt. state for superstates. This may be
77	* shared by more than one struct rx.
78	*/
79	struct rx_cache * cache;
80
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.
85	*/
86	int local_cset_size;
87
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.
91	*/
92	struct rx_hash se_list_memo;
93
94	/* Lists of NFA states are also hashed.
95	*/
96	struct rx_hash set_list_memo;
97
98
99
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.
103	*
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
107	* with an opcode:
108	*/
109	void ** instruction_table;
110
111	/* The list of all states in an NFA.
112	* The NEXT field of NFA states links this list.
113	*/
114	struct rx_nfa_state *nfa_states;
115	struct rx_nfa_state *start_nfa_states;
116	struct rx_superset * start_set;
117
118	/* This orders the search through super-nfa paths.
119	* See the comment near the typedef of rx_se_list_order.
120	*/
121	rx_se_list_order se_list_cmp;
122
123	int next_nfa_id;
124	};
125
126
127
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.
131	*
132	* Also, this is the greatest number of backreferenced subexpressions
133	* allowed in a pattern being matched without caller-supplied registers.
134	*/
135	#ifndef RE_NREGS
136	#define RE_NREGS 30
137	#endif
138
139
140	#ifndef emacs
141	#define CHARBITS 8
142	#define CHAR_SET_SIZE (1 << CHARBITS)
143	#define Sword 1
144	#define SYNTAX(c) re_syntax_table[c]
145	extern char re_syntax_table[CHAR_SET_SIZE];
146	#endif
147
148
149	/* Should we use malloc or alloca? If REGEX_MALLOC is not defined, we
150	* use `alloca' instead of `malloc' for the backtracking stack.
151	*
152	* Emacs will die miserably if we don't do this.
153	*/
154
155	#ifdef REGEX_MALLOC
156	#define REGEX_ALLOCATE malloc
157	#else /* not REGEX_MALLOC */
158	#define REGEX_ALLOCATE alloca
159	#endif /* not REGEX_MALLOC */
160
161	#undef MAX
162	#undef MIN
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;
167
168	\f
169	#ifdef __STDC__
170
171	#else /* STDC */
172
173	#endif /* STDC */
174
175
176	#endif /* _RXH */