File Coverage

engine.c

Criterion	Covered	Total	%
statement	2107	2389	88.2
branch	633	910	69.5
condition			n/a
subroutine			n/a
pod			n/a
total	2740	3299	83.0

line	stmt	bran	code
1			#include "engine.h"
2			#include "regnodes.h"
3			#include "regcomp.h"
4			#include
5			#include
6			#include
7
8			#if PERL_API_REVISION != 5
9			#error This module is only for Perl 5
10			#else
11			#if PERL_API_VERSION == 26
12			/* nothing special */
13			#else
14			#if PERL_API_VERSION == 28
15			#define RC_ANYOFM
16			#else
17			#if PERL_API_VERSION == 30
18			#define RC_ANYOFM
19			#define RC_NANYOFM
20			#define RC_EXACT_ONLY8
21			#define RC_UNCOND_CHARCLASS
22			#define RC_ANYOF_OFFSET
23			#define RC_SHORT_BITMAP
24			#define RC_UNSIGNED_COUNT
25			#else
26			#error Unsupported PERL_API_VERSION
27			#endif
28			#endif
29			#endif
30			#endif
31
32			#define SIZEOF_ARRAY(a) (sizeof(a) / sizeof(a[0]))
33
34			#define TOLOWER(c) ((((c) >= 'A') && ((c) <= 'Z')) ? ((c) - 'A' + 'a') : (c))
35
36			#define LETTER_COUNT ('z' - 'a' + 1)
37
38			#ifndef RC_UNSIGNED_COUNT
39			#define INFINITE_COUNT 32767
40			#else
41			#define INFINITE_COUNT 0xffff
42			#endif
43
44			#define ALNUM_BLOCK 0x0001
45			#define SPACE_BLOCK 0x0002
46			#define ALPHA_BLOCK 0x0004
47			#define NUMBER_BLOCK 0x0008
48			#define UPPER_BLOCK 0x0010
49			#define LOWER_BLOCK 0x0020
50			#define HEX_DIGIT_BLOCK 0x0040
51			#define HORIZONTAL_SPACE_BLOCK 0x0080
52			#define VERTICAL_SPACE_BLOCK 0x0100
53
54			#define MIRROR_SHIFT 16
55			#define NOT_ALNUM_BLOCK (ALNUM_BLOCK << MIRROR_SHIFT)
56			#define NOT_SPACE_BLOCK (SPACE_BLOCK << MIRROR_SHIFT)
57			#define NOT_ALPHA_BLOCK (ALPHA_BLOCK << MIRROR_SHIFT)
58			#define NOT_NUMBER_BLOCK (NUMBER_BLOCK << MIRROR_SHIFT)
59			#define NOT_UPPER_BLOCK (UPPER_BLOCK << MIRROR_SHIFT)
60			#define NOT_LOWER_BLOCK (LOWER_BLOCK << MIRROR_SHIFT)
61			#define NOT_HEX_DIGIT_BLOCK (HEX_DIGIT_BLOCK << MIRROR_SHIFT)
62			#define NOT_HORIZONTAL_SPACE_BLOCK (HORIZONTAL_SPACE_BLOCK << MIRROR_SHIFT)
63			#define NOT_VERTICAL_SPACE_BLOCK (VERTICAL_SPACE_BLOCK << MIRROR_SHIFT)
64
65			#define EVERY_BLOCK 0x01ff01ff
66
67			#define FORCED_BYTE 0x01
68			#define FORCED_CHAR 0x02
69			#define FORCED_MISMATCH (FORCED_BYTE \| FORCED_CHAR)
70
71			#define MIRROR_BLOCK(b) ((((b) & 0xffff) << MIRROR_SHIFT) \| ((b) >> MIRROR_SHIFT))
72
73			/* Regexp terms are normally regnodes, except for EXACT (and EXACTF)
74			nodes, which can bundle many characters, which we have to compare
75			separately. Occasionally, we also need access to extra regexp
76			data. */
77			typedef struct
78			{
79			regexp *origin;
80			regnode *rn;
81			int spent;
82			} Arrow;
83
84			#define GET_LITERAL(a) (((char *)((a)->rn + 1)) + (a)->spent)
85
86			#define GET_OFFSET(rn) ((rn)->next_off ? (rn)->next_off : get_synth_offset(rn))
87
88			#ifndef RC_UNSIGNED_COUNT
89			typedef I16 CurlyCount;
90			#else
91			typedef U16 CurlyCount;
92			#endif
93
94			/* Most functions below have this signature. The first parameter is a
95			flag set after the comparison actually matched something, second
96			parameter points into the first ("left") regexp passed into
97			rc_compare, the third into the second ("right") regexp. Return
98			value is 1 for match, 0 no match, -1 error (with the lowest-level
99			failing function setting rc_error before returning it). */
100			typedef int (FCompare)(int, Arrow , Arrow *);
101
102			/* Place of a char in regexp bitmap. */
103			typedef struct
104			{
105			int offs;
106			unsigned char mask;
107			} BitFlag;
108
109			/* Set of chars and its complement formatted for convenient
110			matching. */
111			typedef struct
112			{
113			char *expl;
114			int expl_size;
115			char lookup[256];
116			char nlookup[256];
117			unsigned char bitmap[ANYOF_BITMAP_SIZE];
118			unsigned char nbitmap[ANYOF_BITMAP_SIZE];
119			} ByteClass;
120
121			char *rc_error = 0;
122
123			unsigned char forced_byte[ANYOF_BITMAP_SIZE];
124
125			/* since Perl 5.18, \s matches vertical tab - see
126			* https://www.effectiveperlprogramming.com/2013/06/the-vertical-tab-is-part-of-s-in-perl-5-18/
127			* , or "Pattern White Space" in perlre */
128			static char whitespace_expl[] = { ' ', '\f', '\n', '\r', '\t', '\v' };
129
130			static ByteClass whitespace;
131
132			static char horizontal_whitespace_expl[] = { '\t', ' ' };
133
134			static ByteClass horizontal_whitespace;
135
136			static char vertical_whitespace_expl[] = { '\r', '\v', '\f', '\n' };
137
138			static ByteClass vertical_whitespace;
139
140			static char digit_expl[10];
141
142			static ByteClass digit;
143
144			static char xdigit_expl[10 + 2 * 6];
145
146			static ByteClass xdigit;
147
148			static char ndot_expl[] = { '\n' };
149
150			static ByteClass ndot;
151
152			static char alphanumeric_expl[11 + 2 * LETTER_COUNT];
153
154			static ByteClass word_bc;
155
156			static ByteClass alnum_bc;
157
158			static char alpha_expl[2 * LETTER_COUNT];
159
160			static ByteClass alpha_bc;
161
162			static char lower_expl[LETTER_COUNT];
163
164			static ByteClass lower_bc;
165
166			static char upper_expl[LETTER_COUNT];
167
168			static ByteClass upper_bc;
169
170			/* true flags for ALNUM and its subsets, 0 otherwise */
171			static unsigned char alphanumeric_classes[REGNODE_MAX];
172
173			/* true flags for NALNUM and its subsets, 0 otherwise */
174			static unsigned char non_alphanumeric_classes[REGNODE_MAX];
175
176			static unsigned char word_posix_regclasses[_CC_VERTSPACE + 1];
177
178			static unsigned char non_word_posix_regclasses[_CC_VERTSPACE + 1];
179
180			static unsigned char newline_posix_regclasses[_CC_VERTSPACE + 1];
181
182			/* Simplified hierarchy of character classes; ignoring the difference
183			between classes (i.e. IsAlnum & IsWord), which we probably
184			shouldn't - it is a documented bug, though... */
185			static char *regclass_names[] = { "Digit", "IsAlnum", "IsSpacePerl",
186			"IsHorizSpace", "IsVertSpace",
187			"IsWord", "IsXPosixAlnum", "IsXPosixXDigit",
188			"IsAlpha", "IsXPosixAlpha",
189			"IsDigit", "IsLower", "IsUpper",
190			"IsXDigit", "SpacePerl", "VertSpace",
191			"Word", "XPosixDigit",
192			"XPosixWord", "XPosixAlpha", "XPosixAlnum",
193			"XPosixXDigit" };
194
195			static U32 regclass_blocks[] = { NUMBER_BLOCK, ALNUM_BLOCK, SPACE_BLOCK,
196			HORIZONTAL_SPACE_BLOCK,
197			VERTICAL_SPACE_BLOCK, ALNUM_BLOCK,
198			ALNUM_BLOCK, HEX_DIGIT_BLOCK, ALPHA_BLOCK,
199			ALPHA_BLOCK, NUMBER_BLOCK, LOWER_BLOCK,
200			UPPER_BLOCK, HEX_DIGIT_BLOCK, SPACE_BLOCK,
201			VERTICAL_SPACE_BLOCK, ALNUM_BLOCK,
202			NUMBER_BLOCK, ALNUM_BLOCK, ALPHA_BLOCK,
203			ALNUM_BLOCK, HEX_DIGIT_BLOCK};
204
205			static U32 regclass_superset[] = { NOT_SPACE_BLOCK,
206			NOT_ALPHA_BLOCK, NOT_NUMBER_BLOCK,
207			ALNUM_BLOCK, ALNUM_BLOCK,
208			ALPHA_BLOCK, ALPHA_BLOCK, HEX_DIGIT_BLOCK,
209			SPACE_BLOCK, NOT_NUMBER_BLOCK,
210			NOT_HEX_DIGIT_BLOCK };
211			static U32 regclass_subset[] = { ALNUM_BLOCK,
212			NOT_ALNUM_BLOCK, NOT_ALNUM_BLOCK,
213			ALPHA_BLOCK, NUMBER_BLOCK,
214			UPPER_BLOCK, LOWER_BLOCK, NUMBER_BLOCK,
215			HORIZONTAL_SPACE_BLOCK,
216			VERTICAL_SPACE_BLOCK, VERTICAL_SPACE_BLOCK };
217
218			static U32 posix_regclass_blocks[_CC_VERTSPACE + 1] = {
219			ALNUM_BLOCK /* _CC_WORDCHAR == 0 */,
220			NUMBER_BLOCK /* _CC_DIGIT == 1 */,
221			ALPHA_BLOCK /* _CC_ALPHA == 2 */,
222			LOWER_BLOCK /* _CC_LOWER == 3 */,
223			UPPER_BLOCK /* _CC_UPPER == 4 */,
224			0,
225			0,
226			ALNUM_BLOCK /* _CC_ALPHANUMERIC == 7 */,
227			0,
228			0,
229			SPACE_BLOCK /* _CC_SPACE == 10 */,
230			HORIZONTAL_SPACE_BLOCK /* _CC_BLANK == 11, and according to perlrecharclass "\p{Blank}" and "\p{HorizSpace}" are synonyms. */,
231			HEX_DIGIT_BLOCK /* _CC_XDIGIT == 12 */
232			}; /* _CC_VERTSPACE set in rc_init because it has different values between perl 5.20 and 5.22 */
233
234			static unsigned char *posix_regclass_bitmaps[_CC_VERTSPACE + 1] = {
235			word_bc.bitmap,
236			digit.bitmap,
237			alpha_bc.bitmap,
238			lower_bc.bitmap,
239			upper_bc.bitmap,
240			0,
241			0,
242			alnum_bc.bitmap,
243			0,
244			0,
245			whitespace.bitmap,
246			horizontal_whitespace.bitmap,
247			xdigit.bitmap
248			};
249
250			static unsigned char *posix_regclass_nbitmaps[_CC_VERTSPACE + 1] = {
251			word_bc.nbitmap,
252			digit.nbitmap,
253			0,
254			0,
255			0,
256			0,
257			0,
258			alnum_bc.nbitmap,
259			0,
260			0,
261			whitespace.nbitmap,
262			horizontal_whitespace.nbitmap,
263			xdigit.nbitmap
264			};
265
266			static unsigned char trivial_nodes[REGNODE_MAX];
267
268			static FCompare dispatch[REGNODE_MAX][REGNODE_MAX];
269
270			static int compare(int anchored, Arrow a1, Arrow a2);
271			static int compare_right_branch(int anchored, Arrow a1, Arrow a2);
272			static int compare_right_curly(int anchored, Arrow a1, Arrow a2);
273
274	12614		static void init_bit_flag(BitFlag *bf, int c)
275			{
276			assert(c >= 0);
277
278	12614		bf->offs = c / 8;
279	12614		bf->mask = 1 << (c % 8);
280	12614		}
281
282	1		static void init_forced_byte()
283			{
284	1		char forced_byte_expl[] = { 'a', 'b', 'c', 'e', 'f', 'x' };
285			BitFlag bf;
286			int i;
287
288	1		memset(forced_byte, 0, sizeof(forced_byte));
289
290	7	100	for (i = 0; i < sizeof(forced_byte_expl); ++i)
291			{
292	6		init_bit_flag(&bf, (unsigned char)forced_byte_expl[i]);
293	6		forced_byte[bf.offs] \|= bf.mask;
294			}
295
296	9	100	for (i = 0; i < 8; ++i)
297			{
298	8		init_bit_flag(&bf, (unsigned char)('0' + i));
299	8		forced_byte[bf.offs] \|= bf.mask;
300			}
301	1		}
302
303	11		static void init_byte_class(ByteClass bc, char expl, int expl_size)
304			{
305			BitFlag bf;
306			int i;
307
308	11		bc->expl = expl;
309	11		bc->expl_size = expl_size;
310
311	11		memset(bc->lookup, 0, sizeof(bc->lookup));
312	11		memset(bc->nlookup, 1, sizeof(bc->nlookup));
313	11		memset(bc->bitmap, 0, sizeof(bc->bitmap));
314	11		memset(bc->nbitmap, 0xff, sizeof(bc->nbitmap));
315
316	285	100	for (i = 0; i < expl_size; ++i)
317			{
318	274		bc->lookup[(unsigned char)expl[i]] = 1;
319	274		bc->nlookup[(unsigned char)expl[i]] = 0;
320
321	274		init_bit_flag(&bf, (unsigned char)expl[i]);
322	274		bc->bitmap[bf.offs] \|= bf.mask;
323	274		bc->nbitmap[bf.offs] &= ~bf.mask;
324			}
325	11		}
326
327	272		static void init_unfolded(char *unf, char c)
328			{
329	272	100	*unf = TOLOWER(c);
		100
330	272	100	unf[1] = ((unf >= 'a') && (unf <= 'z')) ? unf - 'a' + 'A' : unf;
		50
331	272		}
332
333	5200		static U32 extend_mask(U32 mask)
334			{
335			U32 prev_mask;
336			int i, j;
337
338			/* extra cycle is inefficient but makes superset & subset
339			definitions order-independent */
340	5200		prev_mask = 0;
341	13741	100	while (mask != prev_mask)
342			{
343	8541		prev_mask = mask;
344	25623	100	for (i = 0; i < 2; ++i)
345			{
346	204984	100	for (j = 0; j < SIZEOF_ARRAY(regclass_superset); ++j)
347			{
348	187902		U32 b = regclass_superset[j];
349	187902		U32 s = regclass_subset[j];
350	187902	100	if (i)
351			{
352			U32 t;
353
354	93951		t = MIRROR_BLOCK(b);
355	93951		b = MIRROR_BLOCK(s);
356	93951		s = t;
357			}
358
359	187902	100	if (mask & b)
360			{
361	21868		mask \|= s;
362			}
363			}
364			}
365			}
366
367	5200		return mask;
368			}
369
370	0		static int convert_desc_to_map(char desc, int invert, U32 map)
371			{
372			int i;
373	0		U32 mask = 0;
374			char *p;
375
376			/* fprintf(stderr, "enter convert_desc_to_map(%s, %d\n", desc, invert); */
377
378	0		p = strstr(desc, "utf8::");
379			/* make sure (p - 1) is valid /
380	0	0	if (p == desc)
381			{
382	0		rc_error = "no inversion flag before character class description";
383	0		return -1;
384			}
385
386	0	0	while (p)
387			{
388	0		char sign = *(p - 1);
389	0	0	for (i = 0; i < SIZEOF_ARRAY(regclass_names); ++i)
390			{
391	0	0	if (!strncmp(p + 6, regclass_names[i], strlen(regclass_names[i])))
392			{
393	0	0	if (sign == '+')
394			{
395	0	0	if (mask & (regclass_blocks[i] << MIRROR_SHIFT))
396			{
397	0	0	*map = invert ? 0 : EVERY_BLOCK;
398	0		return 1;
399			}
400
401	0		mask \|= regclass_blocks[i];
402			}
403	0	0	else if (sign == '!')
404			{
405	0	0	if (mask & regclass_blocks[i])
406			{
407	0	0	*map = invert ? 0 : EVERY_BLOCK;
408	0		return 1;
409			}
410
411	0		mask \|= (regclass_blocks[i] << MIRROR_SHIFT);
412			}
413			else
414			{
415	0		rc_error = "unknown inversion flag before character class description";
416	0		return -1;
417			}
418			}
419			}
420
421	0		p = strstr(p + 6, "utf8::");
422			}
423
424			/* fprintf(stderr, "parsed 0x%x\n", (unsigned)mask); */
425
426	0	0	if ((mask & ALPHA_BLOCK) && (mask & NUMBER_BLOCK))
		0
427			{
428	0		mask \|= ALNUM_BLOCK;
429			}
430
431	0	0	if (invert)
432			{
433	0		mask = MIRROR_BLOCK(mask);
434			}
435
436	0	0	if ((mask & ALPHA_BLOCK) && (mask & NUMBER_BLOCK))
		0
437			{
438	0		mask \|= ALNUM_BLOCK;
439			}
440
441	0		*map = extend_mask(mask);
442	0		return 1;
443			}
444
445			/* invlist methods are static inside regcomp.c, so we must copy them... */
446	412		static bool get_invlist_offset_addr(SV invlist)
447			{
448	412		return &(((XINVLIST*) SvANY(invlist))->is_offset);
449			}
450
451	206		static UV get_invlist_len(SV *invlist)
452			{
453	206		return (SvCUR(invlist) == 0)
454			? 0
455	206	50	: (SvCUR(invlist) / sizeof(UV)) - *get_invlist_offset_addr(invlist);
456			}
457
458	206		static UV invlist_array(SV invlist)
459			{
460	206		return ((UV ) SvPVX(invlist) + get_invlist_offset_addr(invlist));
461			}
462
463			/* #define DEBUG_dump_invlist */
464
465	30		static int convert_invlist_to_map(SV invlist, int invert, U32 map)
466			{
467			/*
468			Not quite what's in charclass_invlists.h - we skip the header
469			as well as all ASCII values.
470			Note that changes to the arrays may require changing the switch
471			below.
472			*/
473			static UV perl_space_invlist[] = { 128,
474			#if PERL_API_VERSION == 26
475			#include "XPerlSpace.26"
476			#else
477			#if PERL_API_VERSION == 28
478			#include "XPerlSpace.26"
479			#else
480			#if PERL_API_VERSION == 30
481			#include "XPerlSpace.30"
482			#else
483			#error unexpected PERL_API_VERSION
484			#endif
485			#endif
486			#endif
487			};
488
489			#ifdef RC_UNCOND_CHARCLASS
490			static UV perl_space_short_invlist[] = { 256,
491			#include "XPerlSpace.30a"
492			};
493			#endif
494
495			static UV horizontal_space_invlist[] = { 128, 160, 161, 5760, 5761,
496			6158, 6159, 8192, 8203, 8239, 8240, 8287, 8288, 12288, 12289 };
497
498			static UV vertical_space_invlist[] = { 128, 133, 134, 8232, 8234 };
499
500			static UV xposix_digit_invlist[] = { 128,
501			#include "XPosixDigit.22"
502			};
503
504			static UV xposix_alnum_invlist[] = { 128,
505			#if PERL_API_VERSION == 26
506			#include "XPosixAlnum.26"
507			#else
508			#if PERL_API_VERSION == 28
509			#include "XPosixAlnum.28"
510			#else
511			#if PERL_API_VERSION == 30
512			#include "XPosixAlnum.30"
513			#else
514			#error unexpected PERL_API_VERSION
515			#endif
516			#endif
517			#endif
518			};
519
520			static UV xposix_alpha_invlist[] = { 128,
521			#if PERL_API_VERSION == 26
522			#include "XPosixAlpha.26"
523			#else
524			#if PERL_API_VERSION == 28
525			#include "XPosixAlpha.28"
526			#else
527			#if PERL_API_VERSION == 30
528			#include "XPosixAlpha.28"
529			#else
530			#error unexpected PERL_API_VERSION
531			#endif
532			#endif
533			#endif
534			};
535
536			static UV xposix_word_invlist[] = { 128,
537			#include "XPosixWord.22"
538			};
539
540			static UV xposix_xdigit_invlist[] = { 128, 65296, 65306, 65313,
541			65319, 65345, 65351 };
542
543			#ifdef DEBUG_dump_invlist
544			U16 i;
545			char div[3];
546			#endif
547
548			UV *ila;
549			UV ill;
550	30		U32 mask = 0;
551
552			#ifdef DEBUG_dump_invlist
553			fprintf(stderr, "enter convert_invlist_to_map(..., %d, ...)\n", invert);
554			#endif
555
556	30		ill = get_invlist_len(invlist);
557			#ifdef DEBUG_dump_invlist
558			fprintf(stderr, "ill = %lu\n", ill);
559			#endif
560	30	50	ila = ill ? invlist_array(invlist) : 0;
561
562	30		switch (ill)
563			{
564			case SIZEOF_ARRAY(perl_space_invlist):
565	0	0	if (!memcmp(ila, perl_space_invlist, sizeof(perl_space_invlist)))
566			{
567			#ifdef DEBUG_dump_invlist
568			fprintf(stderr, "NOT_SPACE_BLOCK\n");
569			#endif
570	0		mask = NOT_SPACE_BLOCK;
571			}
572
573	0		break;
574
575			case SIZEOF_ARRAY(perl_space_invlist) - 1:
576	0	0	if (!memcmp(ila, perl_space_invlist + 1,
577			sizeof(perl_space_invlist) - sizeof(perl_space_invlist[0])))
578			{
579			#ifdef DEBUG_dump_invlist
580			fprintf(stderr, "SPACE_BLOCK\n");
581			#endif
582	0		mask = SPACE_BLOCK;
583			}
584
585	0		break;
586
587			#ifdef RC_UNCOND_CHARCLASS
588			case SIZEOF_ARRAY(perl_space_short_invlist):
589			if (!memcmp(ila, perl_space_short_invlist, sizeof(perl_space_short_invlist)))
590			{
591			#ifdef DEBUG_dump_invlist
592			fprintf(stderr, "NOT_SPACE_BLOCK\n");
593			#endif
594			mask = NOT_SPACE_BLOCK;
595			}
596
597			break;
598			#endif
599
600			case SIZEOF_ARRAY(horizontal_space_invlist):
601	0	0	if (!memcmp(ila, horizontal_space_invlist, sizeof(horizontal_space_invlist)))
602			{
603			#ifdef DEBUG_dump_invlist
604			fprintf(stderr, "NOT_HORIZONTAL_SPACE_BLOCK\n");
605			#endif
606	0		mask = NOT_HORIZONTAL_SPACE_BLOCK;
607			}
608
609	0		break;
610
611			case SIZEOF_ARRAY(horizontal_space_invlist) - 1:
612	0	0	if (!memcmp(ila, horizontal_space_invlist + 1,
613			sizeof(horizontal_space_invlist) - sizeof(horizontal_space_invlist[0])))
614			{
615			#ifdef DEBUG_dump_invlist
616			fprintf(stderr, "HORIZONTAL_SPACE_BLOCK\n");
617			#endif
618	0		mask = HORIZONTAL_SPACE_BLOCK;
619			}
620
621	0		break;
622
623			case SIZEOF_ARRAY(vertical_space_invlist):
624	0	0	if (!memcmp(ila, vertical_space_invlist, sizeof(vertical_space_invlist)))
625			{
626			#ifdef DEBUG_dump_invlist
627			fprintf(stderr, "NOT_VERTICAL_SPACE_BLOCK\n");
628			#endif
629	0		mask = NOT_VERTICAL_SPACE_BLOCK;
630			}
631
632	0		break;
633
634			case SIZEOF_ARRAY(vertical_space_invlist) - 1:
635	0	0	if (!memcmp(ila, vertical_space_invlist + 1,
636			sizeof(vertical_space_invlist) - sizeof(vertical_space_invlist[0])))
637			{
638			#ifdef DEBUG_dump_invlist
639			fprintf(stderr, "VERTICAL_SPACE_BLOCK\n");
640			#endif
641	0		mask = VERTICAL_SPACE_BLOCK;
642			}
643
644	0		break;
645
646			case SIZEOF_ARRAY(xposix_digit_invlist):
647	0	0	if (!memcmp(ila, xposix_digit_invlist, sizeof(xposix_digit_invlist)))
648			{
649			#ifdef DEBUG_dump_invlist
650			fprintf(stderr, "NOT_NUMBER_BLOCK\n");
651			#endif
652	0		mask = NOT_NUMBER_BLOCK;
653			}
654
655	0		break;
656
657			case SIZEOF_ARRAY(xposix_digit_invlist) - 1:
658	0	0	if (!memcmp(ila, xposix_digit_invlist + 1,
659			sizeof(xposix_digit_invlist) - sizeof(xposix_digit_invlist[0])))
660			{
661			#ifdef DEBUG_dump_invlist
662			fprintf(stderr, "NUMBER_BLOCK\n");
663			#endif
664	0		mask = NUMBER_BLOCK;
665			}
666
667	0		break;
668
669			case SIZEOF_ARRAY(xposix_alnum_invlist):
670	0	0	if (!memcmp(ila, xposix_alnum_invlist, sizeof(xposix_alnum_invlist)))
671			{
672			#ifdef DEBUG_dump_invlist
673			fprintf(stderr, "NOT_ALNUM_BLOCK\n");
674			#endif
675	0		mask = NOT_ALNUM_BLOCK;
676			}
677
678	0		break;
679
680			case SIZEOF_ARRAY(xposix_alnum_invlist) - 1:
681	10	50	if (!memcmp(ila, xposix_alnum_invlist + 1,
682			sizeof(xposix_alnum_invlist) - sizeof(xposix_alnum_invlist[0])))
683			{
684			#ifdef DEBUG_dump_invlist
685			fprintf(stderr, "ALNUM_BLOCK\n");
686			#endif
687	10		mask = ALNUM_BLOCK;
688			}
689
690	10		break;
691
692			case SIZEOF_ARRAY(xposix_alpha_invlist):
693	0	0	if (!memcmp(ila, xposix_alpha_invlist, sizeof(xposix_alpha_invlist)))
694			{
695			#ifdef DEBUG_dump_invlist
696			fprintf(stderr, "NOT_ALPHA_BLOCK\n");
697			#endif
698	0		mask = NOT_ALPHA_BLOCK;
699			}
700
701	0		break;
702
703			case SIZEOF_ARRAY(xposix_alpha_invlist) - 1:
704	20	50	if (!memcmp(ila, xposix_alpha_invlist + 1,
705			sizeof(xposix_alpha_invlist) - sizeof(xposix_alpha_invlist[0])))
706			{
707			#ifdef DEBUG_dump_invlist
708			fprintf(stderr, "ALPHA_BLOCK\n");
709			#endif
710	20		mask = ALPHA_BLOCK;
711			}
712
713	20		break;
714
715			case SIZEOF_ARRAY(xposix_word_invlist):
716	0	0	if (!memcmp(ila, xposix_word_invlist, sizeof(xposix_word_invlist)))
717			{
718			#ifdef DEBUG_dump_invlist
719			fprintf(stderr, "NOT_ALPHA_BLOCK\n");
720			#endif
721	0		mask = NOT_ALPHA_BLOCK;
722			}
723
724	0		break;
725
726			case SIZEOF_ARRAY(xposix_word_invlist) - 1:
727	0	0	if (!memcmp(ila, xposix_word_invlist + 1,
728			sizeof(xposix_word_invlist) - sizeof(xposix_word_invlist[0])))
729			{
730			#ifdef DEBUG_dump_invlist
731			fprintf(stderr, "ALPHA_BLOCK\n");
732			#endif
733	0		mask = ALPHA_BLOCK;
734			}
735
736	0		break;
737
738			case SIZEOF_ARRAY(xposix_xdigit_invlist):
739	0	0	if (!memcmp(ila, xposix_xdigit_invlist, sizeof(xposix_xdigit_invlist)))
740			{
741			#ifdef DEBUG_dump_invlist
742			fprintf(stderr, "NOT_NUMBER_BLOCK\n");
743			#endif
744	0		mask = NOT_NUMBER_BLOCK;
745			}
746
747	0		break;
748
749			case SIZEOF_ARRAY(xposix_xdigit_invlist) - 1:
750	0	0	if (!memcmp(ila, xposix_xdigit_invlist + 1,
751			sizeof(xposix_xdigit_invlist) - sizeof(xposix_xdigit_invlist[0])))
752			{
753			#ifdef DEBUG_dump_invlist
754			fprintf(stderr, "NUMBER_BLOCK\n");
755			#endif
756	0		mask = NUMBER_BLOCK;
757			}
758
759	0		break;
760			}
761
762	30	50	if (mask)
763			{
764	30	50	if (invert)
765			{
766	0		mask = MIRROR_BLOCK(mask);
767			}
768
769	30		*map = extend_mask(mask);
770	30		return 1;
771			}
772
773			#ifdef DEBUG_dump_invlist
774			div[0] = 0;
775			div[2] = 0;
776			for (i = 0; i < ill; ++i)
777			{
778			fprintf(stderr, "%s0x%x", div, (int)(ila[i]));
779			div[0] = ',';
780			div[1] = '\n';
781			}
782
783			fprintf(stderr, "\n");
784			#endif
785
786	0		return 0;
787			}
788
789	30		static int convert_regclass_map(Arrow a, U32 map)
790			{
791			regexp_internal *pr;
792			U32 n;
793			struct reg_data *rdata;
794
795			/* fprintf(stderr, "enter convert_regclass_map\n"); */
796
797			assert((a->rn->type == ANYOF) \|\| (a->rn->type == ANYOFD));
798
799			/* basically copied from regexec.c:regclass_swash */
800	30		n = ARG_LOC(a->rn);
801	30		pr = RXi_GET(a->origin);
802	30	50	if (!pr) /* this should have been tested by find_internal during
803			initialization, but just in case... */
804			{
805	0		rc_error = "regexp_internal not found";
806	0		return -1;
807			}
808
809	30		rdata = pr->data;
810
811	30	50	if ((n < rdata->count) &&
		50
812	30		(rdata->what[n] == 's')) {
813	30		SV rv = (SV )(rdata->data[n]);
814	30		AV av = (AV )SvRV(rv);
815	30		SV **ary = AvARRAY(av);
816	30		SV si = ary;
817
818			#ifdef RC_UNCOND_CHARCLASS
819			/* from get_regclass_nonbitmap_data of perl 5.30.0: invlist is
820			in ary[0] */
821			return convert_invlist_to_map(si,
822			!!(a->rn->flags & ANYOF_INVERT),
823			map);
824			#else
825	30	50	if (si && (si != &PL_sv_undef))
		50
826			{
827			/* From regcomp.c:regclass: the 0th element stores the
828			character class description in its textual form. It isn't
829			very clear what exactly the textual form is, but we hope
830			it's 0-terminated. */
831	0	0	return convert_desc_to_map(SvPV_nolen(*ary),
832	0		!!(a->rn->flags & ANYOF_INVERT),
833			map);
834			}
835			/* FIXME: in perl 5.18, crashes for inverted classes */
836			else
837			{
838			/* in perl 5.16, the textual form doesn't necessarily exist... */
839	30	50	if (av_len(av) >= 3)
840			{
841	30		SV *invlist = ary[3];
842
843	30	50	if (SvUV(ary[4])) /* invlist_has_user_defined_property */
		50
844			{
845			/* fprintf(stderr, "invlist has user defined property\n"); */
846	0		return 0;
847			}
848
849	30		return convert_invlist_to_map(invlist,
850	30		!!(a->rn->flags & ANYOF_INVERT),
851			map);
852			}
853
854			/* fprintf(stderr, "regclass invlist not found\n"); */
855	0		return 0;
856			}
857			#endif
858			}
859
860	0		rc_error = "regclass not found";
861	0		return -1;
862			}
863
864			/* lifted from Perl__get_regclass_nonbitmap_data */
865	176		static SV get_invlist_sv(Arrow a)
866			{
867	176		RXi_GET_DECL(a->origin, progi);
868	176		struct reg_data *data = progi->data;
869
870			assert((a->rn->type == ANYOF) \|\| (a->rn->type == ANYOFD));
871
872	176	50	if (data && data->count)
		50
873			{
874	176		const U32 n = ARG(a->rn);
875
876	176	50	if (data->what[n] == 's')
877			{
878	176		SV * const rv = MUTABLE_SV(data->data[n]);
879	176		AV * const av = MUTABLE_AV(SvRV(rv));
880	176		SV **const ary = AvARRAY(av);
881
882			#ifdef RC_UNCOND_CHARCLASS
883			return *ary;
884			#else
885	176	50	if (av_tindex(av) >= 3)
886			{
887	176		return ary[3];
888			}
889			#endif
890			}
891			}
892
893	0		return 0;
894			}
895
896			/* returns 1 OK (map set), 0 map not recognized/representable, -1
897			unexpected input (rc_error set) */
898	72		static int convert_map(Arrow a, U32 map)
899			{
900			/* fprintf(stderr, "enter convert_map\n"); */
901
902			assert((a->rn->type == ANYOF) \|\| (a->rn->type == ANYOFD));
903			assert(map);
904
905	72	100	if (ANYOF_FLAGS(a->rn) & (ANYOF_SHARED_d_UPPER_LATIN1_UTF8_STRING_MATCHES_non_d_RUNTIME_USER_PROP
906			#ifdef RC_UNCOND_CHARCLASS
907			\| ANYOF_INVERT
908			#endif
909			))
910			{
911	30		return convert_regclass_map(a, map);
912			}
913			else
914			{
915			/* fprintf(stderr, "zero map\n"); */
916	42		*map = 0;
917	42		return 1;
918			}
919			}
920
921			/* returns 1 OK (map set), 0 map not recognized/representable */
922	5368		static int convert_class_narrow(Arrow a, U32 map)
923			{
924			/* fprintf(stderr, "enter convert_class_narrow\n"); */
925
926			assert(map);
927
928	5368	50	if (a->rn->flags >= SIZEOF_ARRAY(posix_regclass_blocks))
929			{
930			/* fprintf(stderr, "unknown class %d\n", a->rn->flags); */
931	0		return 0;
932			}
933
934	5368		U32 mask = posix_regclass_blocks[a->rn->flags];
935	5368	50	if (!mask)
936			{
937			/* fprintf(stderr, "class %d ignored\n", a->rn->flags); */
938	0		return 0;
939			}
940
941	5368		*map = mask;
942	5368		return 1;
943			}
944
945			#ifdef RC_ANYOFM
946			/* Adapted from regcomp.c:get_ANYOFM_contents. b must point to
947			ANYOF_BITMAP_SIZE bytes. Returns 1 OK (b set), 0 matches something
948			above the bitmap. */
949			static int convert_anyofm_to_bitmap(Arrow a, unsigned char b)
950			{
951			regnode *n = a->rn;
952			U8 lowest = (U8)ARG(n);
953			unsigned count = 0;
954			unsigned needed = 1U << PL_bitcount[(U8)~FLAGS(n)];
955			unsigned i;
956			BitFlag bf;
957
958			memset(b, 0, ANYOF_BITMAP_SIZE);
959			for (i = lowest; i <= 0xFF; i++)
960			{
961			if ((i & FLAGS(n)) == ARG(n))
962			{
963			init_bit_flag(&bf, i);
964			b[bf.offs] \|= bf.mask;
965
966			if (++count >= needed)
967			{
968			return 1;
969			}
970			}
971			}
972
973			return 0;
974			}
975			#endif
976
977			/* returns 1 OK (map set), 0 map not recognized/representable */
978	4182		static int convert_class(Arrow a, U32 map)
979			{
980	4182	50	if (!convert_class_narrow(a, map))
981			{
982	0		return 0;
983			}
984
985	4182		map = extend_mask(map);
986	4182		return 1;
987			}
988
989	988		static int convert_negative_class(Arrow a, U32 map)
990			{
991			U32 mask;
992
993	988	50	if (!convert_class_narrow(a, &mask))
994			{
995	0		return 0;
996			}
997
998	988		*map = extend_mask(MIRROR_BLOCK(mask));
999	988		return 1;
1000			}
1001
1002	644		static int get_assertion_offset(regnode *p)
1003			{
1004			int offs;
1005
1006	644		offs = ARG_LOC(p);
1007	644	50	if (offs <= 2)
1008			{
1009	0		rc_error = "Assertion offset too small";
1010	0		return -1;
1011			}
1012
1013	644		return offs;
1014			}
1015
1016	3024		static int get_synth_offset(regnode *p)
1017			{
1018			assert(!p->next_off);
1019
1020	3024	100	if (((p->type == EXACT) \|\| (p->type == EXACTF) \|\| (p->type == EXACTFU)) &&
		50
		100
		50
1021	1508		(p->flags == 1))
1022			{
1023	1508		return 2;
1024			}
1025	1516	100	else if (trivial_nodes[p->type] \|\|
		100
1026	439	100	(p->type == REG_ANY) \|\| (p->type == SANY) \|\|
		100
1027	356	100	(p->type == POSIXD) \|\| (p->type == NPOSIXD) \|\|
		100
1028	250	100	(p->type == POSIXU) \|\| (p->type == NPOSIXU) \|\|
		100
1029	168	100	(p->type == POSIXA) \|\| (p->type == NPOSIXA) \|\|
		100
1030	159		(p->type == LNBREAK))
1031			{
1032	1361		return 1;
1033			}
1034	155	100	else if ((p->type == ANYOF) \|\| (p->type == ANYOFD))
		100
1035			{
1036			/* other flags obviously exist, but they haven't been seen yet
1037			and it isn't clear what they mean */
1038	149		unsigned int unknown = p->flags & ~(ANYOF_INVERT \|
1039			ANYOF_MATCHES_ALL_ABOVE_BITMAP \| ANYOF_SHARED_d_UPPER_LATIN1_UTF8_STRING_MATCHES_non_d_RUNTIME_USER_PROP \| ANYOF_SHARED_d_UPPER_LATIN1_UTF8_STRING_MATCHES_non_d_RUNTIME_USER_PROP);
1040	149	50	if (unknown)
1041			{
1042			/* p[10] seems always 0 on Linux, but 0xfbfaf9f8 seen on
1043			Windows; for '[\\w\\-_.]+\\.', both 0 and 0x20202020
1044			observed in p[11] - wonder what those are... */
1045	0		rc_error = "Unknown bitmap format";
1046	0		return -1;
1047			}
1048
1049			#ifndef RC_ANYOF_OFFSET
1050	149		return 11;
1051			#else
1052			return 10;
1053			#endif
1054			}
1055			#ifdef RC_ANYOFM
1056			else if (p->type == ANYOFM)
1057			{
1058			return 2;
1059			}
1060			#endif
1061			#ifdef RC_NANYOFM
1062			else if (p->type == NANYOFM)
1063			{
1064			return 2;
1065			}
1066			#endif
1067	6	100	else if ((p->type == IFMATCH) \|\| (p->type == UNLESSM) \|\|
		50
		0
1068	0		(p->type == SUSPEND))
1069			{
1070	6		return get_assertion_offset(p);
1071			}
1072
1073			/* fprintf(stderr, "type %d\n", p->type); */
1074	0		rc_error = "Offset not set";
1075	0		return -1;
1076			}
1077
1078	2893		static int get_size(regnode *rn)
1079			{
1080			int offs;
1081	2893		regnode *e = rn;
1082
1083	6999	100	while (e->type != END)
1084			{
1085	4106	100	offs = GET_OFFSET(e);
1086	4106	50	if (offs <= 0)
1087			{
1088	0		return -1;
1089			}
1090
1091	4106		e += offs;
1092			}
1093
1094	2893		return e - rn + 1;
1095			}
1096
1097			/* #define DEBUG_dump_data */
1098
1099	18112		static regnode find_internal(regexp pt)
1100			{
1101			regexp_internal *pr;
1102			regnode *p;
1103			#ifdef DEBUG_dump_data
1104			struct reg_data *rdata;
1105			int n;
1106			#endif
1107
1108			assert(pt);
1109
1110			/* ActivePerl Build 1001 doesn't export PL_core_reg_engine, so
1111			the test, however useful, wouldn't link... */
1112			#if !defined(ACTIVEPERL_PRODUCT)
1113	18112	50	if (pt->engine && (pt->engine != &PL_core_reg_engine))
		50
1114			{
1115	0		rc_error = "Alternative regexp engine not supported";
1116	0		return 0;
1117			}
1118			#endif
1119
1120	18112		pr = RXi_GET(pt);
1121	18112	50	if (!pr)
1122			{
1123	0		rc_error = "Internal regexp not set";
1124	0		return 0;
1125			}
1126
1127	18112		p = pr->program;
1128	18112	50	if (!p)
1129			{
1130	0		rc_error = "Compiled regexp not set";
1131	0		return 0;
1132			}
1133
1134	18112	50	if (!((p->flags == REG_MAGIC) &&
		50
1135	18112		(p->next_off == 0)))
1136			{
1137			/* fprintf(stderr, "%d %d %d\n", p->flags, p->type, p->next_off); */
1138	0		rc_error = "Invalid regexp signature";
1139	0		return 0;
1140			}
1141
1142			#ifdef DEBUG_dump_data
1143			rdata = pr->data;
1144			if (rdata)
1145			{
1146			fprintf(stderr, "regexp data count = %d\n", (int)(rdata->count));
1147			for (n = 0; n < rdata->count; ++n)
1148			{
1149			fprintf(stderr, "\twhat[%d] = %c\n", n, rdata->what[n]);
1150			}
1151			}
1152			else
1153			{
1154			fprintf(stderr, "no regexp data\n");
1155			}
1156			#endif
1157
1158	18112		return p + 1;
1159			}
1160
1161	216		static unsigned char parse_hex_digit(char d)
1162			{
1163			unsigned char rv;
1164
1165	216		d = tolower(d);
1166
1167	216	50	if (('0' <= d) && (d <= '9'))
		100
1168			{
1169	149		rv = d - '0';
1170			}
1171			else
1172			{
1173	67		rv = 10 + (d - 'a');
1174			}
1175
1176	216		return rv;
1177			}
1178
1179	108		static unsigned char parse_hex_byte(const char *first)
1180			{
1181	216		return 16 * parse_hex_digit(*first) +
1182	108		parse_hex_digit(first[1]);
1183			}
1184
1185	18126		static unsigned get_forced_semantics(REGEXP *pt)
1186			{
1187	18126		const char *precomp = RX_PRECOMP(pt);
1188	18126		U32 prelen = RX_PRELEN(pt);
1189	18126		int quoted = 0;
1190			int matched;
1191	18126		unsigned forced = 0;
1192			U32 i;
1193			BitFlag bf;
1194			char c;
1195
1196			/* fprintf(stderr, "precomp = %s\n", (int)prelen, precomp); /
1197
1198	134176	100	for (i = 0; i < prelen; ++i)
1199			{
1200	116050		c = precomp[i];
1201
1202	116050	100	if (c == '.')
1203			{
1204			/* a dot does match Unicode character - the problem is
1205			that character might take up multiple bytes, and we
1206			don't want to match just one of them... */
1207	1252		forced \|= FORCED_BYTE;
1208			}
1209
1210	116050	100	if (!quoted)
1211			{
1212			/* technically, the backslash might be in a comment, but
1213			parsing that is too much hassle */
1214	104056	100	if (c == '\\')
1215			{
1216	104056		quoted = 1;
1217			}
1218			}
1219			else
1220			{
1221	11994		matched = 0;
1222
1223	11994	100	if (c == 'N')
1224			{
1225			/* we have special cases only for \r & \n... */
1226	441	100	if ((i + 8 < prelen) &&
		100
1227	11	50	!memcmp(precomp + i + 1, "{U+00", 5) &&
1228	22	50	isxdigit(precomp[i + 6]) && isxdigit(precomp[i + 7]) &&
		50
1229	11		(precomp[i + 8] == '}'))
1230	11		{
1231	11		unsigned char x = parse_hex_byte(precomp + i + 6);
1232	11	100	if ((x != '\r') && (x != '\n'))
		50
1233			{
1234	0		forced \|= FORCED_CHAR;
1235			}
1236
1237	11		i += 8;
1238			}
1239	430	100	else if ((i + 1 < prelen) &&
		100
1240	220		(precomp[i + 1] == '{'))
1241			{
1242	13		forced \|= FORCED_CHAR;
1243			}
1244
1245			/* otherwise it's not an escape, but the inverse of \n
1246			- we aren't interested in that */
1247
1248	441		matched = 1;
1249			}
1250	11553	100	else if (c == 'x')
1251			{
1252	234		if ((i + 2 < prelen) &&
1253	214	50	isxdigit(precomp[i + 1]) && isxdigit(precomp[i + 2]))
1254			{
1255	97		unsigned char x = parse_hex_byte(precomp + i + 1);
1256	97	100	if ((x != '\r') && (x != '\n'))
		100
1257			{
1258	85		forced \|= FORCED_BYTE;
1259			}
1260
1261	97		matched = 1;
1262	97		i += 2;
1263			}
1264			}
1265
1266			/* ...and we aren't bothering to parse octal numbers
1267			and \x{n+} at all... */
1268
1269	11994	100	if (!matched)
1270			{
1271	11456		init_bit_flag(&bf, (unsigned char)c);
1272	11456	100	if (forced_byte[bf.offs] & bf.mask)
1273			{
1274	339		forced \|= FORCED_BYTE;
1275			}
1276			}
1277
1278	11994		quoted = 0;
1279			}
1280			}
1281
1282	18126		return forced;
1283			}
1284
1285	913		static regnode alloc_alt(regnode p, int sz)
1286			{
1287			regnode *alt;
1288
1289	913		alt = (regnode )malloc(sizeof(regnode) sz);
1290	913	50	if (!alt)
1291			{
1292	0		rc_error = "Could not allocate memory for regexp copy";
1293	0		return 0;
1294			}
1295
1296	913		memcpy(alt, p, sizeof(regnode) * sz);
1297
1298	913		return alt;
1299			}
1300
1301	376		static regnode alloc_terminated(regnode p, int sz)
1302			{
1303			regnode *alt;
1304			int last;
1305
1306			/* fprintf(stderr, "enter alloc_terminated(, %d\n", sz); */
1307
1308			assert(sz > 0);
1309	376		alt = alloc_alt(p, sz);
1310	376	50	if (!alt)
1311			{
1312	0		return 0;
1313			}
1314
1315	376		last = alt[sz - 1].type;
1316			/* fprintf(stderr, "type: %d\n", last); */
1317	376	50	if ((last >= REGNODE_MAX) \|\| !trivial_nodes[last])
		50
1318			{
1319	0		rc_error = "Alternative doesn't end like subexpression";
1320	0		return 0;
1321			}
1322
1323	376		alt[sz - 1].type = END;
1324	376		return alt;
1325			}
1326
1327	15971		static int bump_exact(Arrow *a)
1328			{
1329			int offs;
1330
1331			assert((a->rn->type == EXACT) \|\| (a->rn->type == EXACTF) \|\| (a->rn->type == EXACTFU)
1332			#ifdef RC_EXACT_ONLY8
1333			\|\| (a->rn->type == EXACT_ONLY8)
1334			#endif
1335			);
1336
1337	15971	100	offs = GET_OFFSET(a->rn);
1338	15971	50	if (offs <= 0)
1339			{
1340	0		return -1;
1341			}
1342
1343			#ifdef RC_EXACT_ONLY8
1344			if (a->rn->type == EXACT_ONLY8)
1345			{
1346			while ((((unsigned char )((a)->rn + 1)) + (a)->spent) & 0x80)
1347			{
1348			++(a->spent);
1349			}
1350			}
1351			#endif
1352
1353	15971	100	if (++(a->spent) >= a->rn->flags)
1354			{
1355	10645		a->spent = 0;
1356	10645		a->rn += offs;
1357			}
1358
1359	15971		return 1;
1360			}
1361
1362	18559		static int bump_regular(Arrow *a)
1363			{
1364			int offs;
1365
1366			assert(a->rn->type != END);
1367			assert(a->rn->type != EXACT);
1368			assert(a->rn->type != EXACTF);
1369			assert(!a->spent);
1370
1371	18559	100	offs = GET_OFFSET(a->rn);
1372	18559	50	if (offs <= 0)
1373			{
1374	0		return -1;
1375			}
1376
1377	18559		a->rn += offs;
1378	18559		return 1;
1379			}
1380
1381	32717		static int bump_with_check(Arrow *a)
1382			{
1383	32717	100	if (a->rn->type == END)
1384			{
1385	73		return 0;
1386			}
1387	32644	100	else if ((a->rn->type == EXACT) \|\| (a->rn->type == EXACTF) \|\| (a->rn->type == EXACTFU)
		100
		100
1388			#ifdef RC_EXACT_ONLY8
1389			\|\| (a->rn->type == EXACT_ONLY8)
1390			#endif
1391			)
1392			{
1393	15971		return bump_exact(a);
1394			}
1395			else
1396			{
1397	16673		return bump_regular(a);
1398			}
1399			}
1400
1401	92		static int get_jump_offset(regnode *p)
1402			{
1403			int offs;
1404			regnode *q;
1405
1406			assert(p->type != END);
1407
1408	92	50	offs = GET_OFFSET(p);
1409	92	50	if (offs <= 0)
1410			{
1411	0		return -1;
1412			}
1413
1414	92		q = p + offs;
1415	124	100	while (trivial_nodes[q->type])
1416			{
1417	32	100	offs = GET_OFFSET(q);
1418	32	50	if (offs <= 0)
1419			{
1420	0		return -1;
1421			}
1422
1423	32		q += offs;
1424			}
1425
1426	92		return q - p;
1427			}
1428
1429	18133		REGEXP rc_regcomp(SV rs)
1430			{
1431			REGEXP *rx;
1432
1433	18133	50	if (!rs)
1434			{
1435	0		croak("No regexp to compare");
1436			}
1437
1438	18133		rx = pregcomp(rs, 0);
1439	18128	50	if (!rx)
1440			{
1441	0		croak("Cannot compile regexp");
1442			}
1443
1444	18128		return rx;
1445			}
1446
1447	18128		void rc_regfree(REGEXP *rx)
1448			{
1449	18128	50	if (rx)
1450			{
1451	18128		pregfree(rx);
1452			}
1453	18128		}
1454
1455	6354		static int compare_mismatch(int anchored, Arrow a1, Arrow a2)
1456			{
1457			int rv;
1458
1459			/* fprintf(stderr, "enter compare_mismatch(%d...)\n", anchored); */
1460
1461	6354	100	if (anchored)
1462			{
1463	672		return 0;
1464			}
1465			else
1466			{
1467	5682		rv = bump_with_check(a1);
1468	5682	100	if (rv <= 0)
1469			{
1470	73		return rv;
1471			}
1472
1473	5609		return compare(0, a1, a2);
1474			}
1475			}
1476
1477	13018		static int compare_tails(int anchored, Arrow a1, Arrow a2)
1478			{
1479			Arrow tail1, tail2;
1480			int rv;
1481
1482			/* is it worth using StructCopy? */
1483	13018		tail1 = *a1;
1484	13018		rv = bump_with_check(&tail1);
1485	13018	50	if (rv <= 0)
1486			{
1487	0		return rv;
1488			}
1489
1490	13018		tail2 = *a2;
1491	13018		rv = bump_with_check(&tail2);
1492	13018	50	if (rv <= 0)
1493			{
1494	0		return rv;
1495			}
1496
1497	13018		rv = compare(1, &tail1, &tail2);
1498	13018	50	if (rv < 0)
1499			{
1500	0		return rv;
1501			}
1502
1503	13018	100	if (!rv)
1504			{
1505	257		rv = compare_mismatch(anchored, a1, a2);
1506			}
1507			else
1508			{
1509	12761		*a1 = tail1;
1510	12761		*a2 = tail2;
1511			}
1512
1513	13018		return rv;
1514			}
1515
1516	821		static int compare_left_tail(int anchored, Arrow a1, Arrow a2)
1517			{
1518			Arrow tail1;
1519			int rv;
1520
1521	821		tail1 = *a1;
1522	821		rv = bump_with_check(&tail1);
1523	821	50	if (rv <= 0)
1524			{
1525	0		return rv;
1526			}
1527
1528	821		return compare(anchored, &tail1, a2);
1529			}
1530
1531	262		static int compare_after_assertion(int anchored, Arrow a1, Arrow a2)
1532			{
1533			Arrow tail1;
1534			int offs;
1535
1536			assert((a1->rn->type == IFMATCH) \|\| (a1->rn->type == UNLESSM));
1537
1538	262		offs = get_assertion_offset(a1->rn);
1539	262	50	if (offs < 0)
1540			{
1541	0		return offs;
1542			}
1543
1544	262		tail1.origin = a1->origin;
1545	262		tail1.rn = a1->rn + offs;
1546	262		tail1.spent = 0;
1547	262		return compare(anchored, &tail1, a2);
1548			}
1549
1550	80		static int compare_positive_assertions(int anchored, Arrow a1, Arrow a2)
1551			{
1552			regnode p1, alt1, p2, alt2;
1553			int rv, sz1, sz2;
1554			Arrow left, right;
1555
1556	80		p1 = a1->rn;
1557	80		p2 = a2->rn;
1558			assert(p1->type == IFMATCH);
1559			assert(p2->type == IFMATCH);
1560
1561	80		sz1 = get_assertion_offset(p1);
1562	80	50	if (sz1 < 0)
1563			{
1564	0		return -1;
1565			}
1566
1567	80		sz2 = get_assertion_offset(p2);
1568	80	50	if (sz2 < 0)
1569			{
1570	0		return -1;
1571			}
1572
1573	80		alt1 = alloc_terminated(p1 + 2, sz1 - 2);
1574	80	50	if (!alt1)
1575			{
1576	0		return -1;
1577			}
1578
1579	80		alt2 = alloc_terminated(p2 + 2, sz2 - 2);
1580	80	50	if (!alt2)
1581			{
1582	0		free(alt1);
1583	0		return -1;
1584			}
1585
1586	80		left.origin = a1->origin;
1587	80		left.rn = alt1;
1588	80		left.spent = 0;
1589	80		right.origin = a2->origin;
1590	80		right.rn = alt2;
1591	80		right.spent = 0;
1592	80		rv = compare(0, &left, &right);
1593
1594	80		free(alt1);
1595	80		free(alt2);
1596
1597	80	100	if (rv <= 0)
1598			{
1599	1		return rv;
1600			}
1601
1602			/* left & right.origin stays a1 & a2->origin, respectively */
1603	79		left.rn = p1 + sz1;
1604	79		left.spent = 0;
1605	79		right.rn = p2 + sz2;
1606	79		right.spent = 0;
1607	80		return compare(anchored, &left, &right);
1608			}
1609
1610	77		static int compare_negative_assertions(int anchored, Arrow a1, Arrow a2)
1611			{
1612			regnode p1, alt1, p2, alt2;
1613			int rv, sz1, sz2;
1614			Arrow left, right;
1615
1616	77		p1 = a1->rn;
1617	77		p2 = a2->rn;
1618			assert(p1->type == UNLESSM);
1619			assert(p2->type == UNLESSM);
1620
1621	77		sz1 = get_assertion_offset(p1);
1622	77	50	if (sz1 < 0)
1623			{
1624	0		return -1;
1625			}
1626
1627	77		sz2 = get_assertion_offset(p2);
1628	77	50	if (sz2 < 0)
1629			{
1630	0		return -1;
1631			}
1632
1633	77		alt1 = alloc_terminated(p1 + 2, sz1 - 2);
1634	77	50	if (!alt1)
1635			{
1636	0		return -1;
1637			}
1638
1639	77		alt2 = alloc_terminated(p2 + 2, sz2 - 2);
1640	77	50	if (!alt2)
1641			{
1642	0		free(alt1);
1643	0		return -1;
1644			}
1645
1646	77		left.origin = a1->origin;
1647	77		left.rn = alt1;
1648	77		left.spent = 0;
1649	77		right.origin = a2->origin;
1650	77		right.rn = alt2;
1651	77		right.spent = 0;
1652	77		rv = compare(0, &right, &left);
1653
1654	77		free(alt1);
1655	77		free(alt2);
1656
1657	77	100	if (rv <= 0)
1658			{
1659	2		return rv;
1660			}
1661
1662			/* left & right.origin stays a1 & a2->origin, respectively */
1663	75		left.rn = p1 + sz1;
1664	75		left.spent = 0;
1665	75		right.rn = p2 + sz2;
1666	75		right.spent = 0;
1667	77		return compare(anchored, &left, &right);
1668			}
1669
1670	31		static int compare_subexpressions(int anchored, Arrow a1, Arrow a2)
1671			{
1672			regnode p1, alt1, p2, alt2;
1673			int rv, sz1, sz2;
1674			Arrow left, right;
1675
1676	31		p1 = a1->rn;
1677	31		p2 = a2->rn;
1678			assert(p1->type == SUSPEND);
1679			assert(p2->type == SUSPEND);
1680
1681	31		sz1 = get_assertion_offset(p1);
1682	31	50	if (sz1 < 0)
1683			{
1684	0		return -1;
1685			}
1686
1687	31		sz2 = get_assertion_offset(p2);
1688	31	50	if (sz2 < 0)
1689			{
1690	0		return -1;
1691			}
1692
1693	31		alt1 = alloc_terminated(p1 + 2, sz1 - 2);
1694	31	50	if (!alt1)
1695			{
1696	0		return -1;
1697			}
1698
1699	31		alt2 = alloc_terminated(p2 + 2, sz2 - 2);
1700	31	50	if (!alt2)
1701			{
1702	0		free(alt1);
1703	0		return -1;
1704			}
1705
1706	31		left.origin = a1->origin;
1707	31		left.rn = alt1;
1708	31		left.spent = 0;
1709	31		right.origin = a2->origin;
1710	31		right.rn = alt2;
1711	31		right.spent = 0;
1712	31		rv = compare(1, &left, &right);
1713
1714	31		free(alt1);
1715	31		free(alt2);
1716
1717	31	100	if (rv <= 0)
1718			{
1719	1		return rv;
1720			}
1721
1722			/* left & right.origin stays a1 & a2->origin, respectively */
1723	30		left.rn = p1 + sz1;
1724	30		left.spent = 0;
1725	30		right.rn = p2 + sz2;
1726	30		right.spent = 0;
1727	31		return compare(1, &left, &right);
1728			}
1729
1730	637		static int compare_bol(int anchored, Arrow a1, Arrow a2)
1731			{
1732			int rv;
1733
1734			assert((a1->rn->type == MBOL) \|\| (a1->rn->type == SBOL));
1735
1736	637	100	if (anchored)
1737			{
1738	8		return 0;
1739			}
1740
1741	629	50	if (bump_regular(a1) <= 0)
1742			{
1743	0		return -1;
1744			}
1745
1746	629		rv = compare(1, a1, a2);
1747	629	100	if (!rv)
1748			{
1749	62		rv = compare_mismatch(0, a1, a2);
1750			}
1751
1752	629		return rv;
1753			}
1754
1755	35580		static unsigned char get_bitmap_byte(regnode *p, int i)
1756			{
1757			unsigned char *bitmap;
1758			unsigned char loc;
1759
1760			assert((p->type == ANYOF) \|\| (p->type == ANYOFD));
1761
1762	35580		bitmap = (unsigned char *)(p + 2);
1763			#ifdef RC_SHORT_BITMAP
1764			if ((i >= 16) && (p->type == ANYOFD) &&
1765			(p->flags & ANYOF_SHARED_d_MATCHES_ALL_NON_UTF8_NON_ASCII_non_d_WARN_SUPER))
1766			{
1767			loc = 0xff;
1768			}
1769			else
1770			{
1771			loc = bitmap[i];
1772			}
1773			#else
1774	35580		loc = bitmap[i];
1775			#endif
1776	35580	100	if (p->flags & ANYOF_INVERT)
1777			{
1778	234		loc = ~loc;
1779			}
1780
1781	35580		return loc;
1782			}
1783
1784	827		static int compare_bitmaps(int anchored, Arrow a1, Arrow a2,
1785			unsigned char b1, unsigned char b2)
1786			{
1787			/* Note that aN->flags must be ignored when bN is set (necessary
1788			for ANYOFM, where they aren't really flags and can't be used as
1789			such). */
1790			unsigned char loc1, loc2;
1791			int i;
1792
1793			/* fprintf(stderr, "enter compare_bitmaps(%d, %d, %d)\n", anchored,
1794			a1->rn->type, a2->rn->type); */
1795
1796	22728	100	for (i = 0; i < ANYOF_BITMAP_SIZE; ++i)
1797			{
1798	22064	100	loc1 = b1 ? b1[i] : get_bitmap_byte(a1->rn, i);
1799	22064	100	loc2 = b2 ? b2[i] : get_bitmap_byte(a2->rn, i);
1800	22064	100	if (loc1 & ~loc2)
1801			{
1802			/* fprintf(stderr, "compare_bitmaps fails at %d: %d does not imply %d\n",
1803			i, loc1, loc2); */
1804	163		return compare_mismatch(anchored, a1, a2);
1805			}
1806			}
1807
1808	664		return compare_tails(anchored, a1, a2);
1809			}
1810
1811			#ifdef RC_NANYOFM
1812			static int compare_negative_bitmaps(int anchored, Arrow a1, Arrow a2,
1813			unsigned char b1, unsigned char b2)
1814			{
1815			unsigned char loc1, loc2;
1816			int i;
1817
1818			assert(b1 && b2);
1819			for (i = 0; i < ANYOF_BITMAP_SIZE; ++i)
1820			{
1821			loc1 = b1[i];
1822			loc2 = b2[i];
1823			if (~loc1 & loc2)
1824			{
1825			return compare_mismatch(anchored, a1, a2);
1826			}
1827			}
1828
1829			return compare_tails(anchored, a1, a2);
1830			}
1831			#endif
1832
1833	5		static int compare_anyof_multiline(int anchored, Arrow a1, Arrow a2)
1834			{
1835			BitFlag bf;
1836			Arrow tail1, tail2;
1837			unsigned char req;
1838			int i;
1839
1840			/* fprintf(stderr, "enter compare_anyof_multiline\n"); */
1841
1842			assert((a1->rn->type == ANYOF) \|\| (a1->rn->type == ANYOFD));
1843			assert((a2->rn->type == MBOL) \|\| (a2->rn->type == MEOL));
1844
1845	5	100	if (a1->rn->flags & ANYOF_MATCHES_ALL_ABOVE_BITMAP)
1846			{
1847	2		return compare_mismatch(anchored, a1, a2);
1848			}
1849
1850	3		init_bit_flag(&bf, '\n');
1851	6	50	for (i = 0; i < ANYOF_BITMAP_SIZE; ++i)
1852			{
1853	6	100	req = (i != bf.offs) ? 0 : bf.mask;
1854	6	100	if (get_bitmap_byte(a1->rn, i) != req)
1855			{
1856	3		return compare_mismatch(anchored, a1, a2);
1857			}
1858			}
1859
1860	0		tail1 = *a1;
1861	0	0	if (bump_regular(&tail1) <= 0)
1862			{
1863	0		return -1;
1864			}
1865
1866	0		tail2 = *a2;
1867	0	0	if (bump_regular(&tail2) <= 0)
1868			{
1869	0		return -1;
1870			}
1871
1872	5		return compare(1, &tail1, &tail2);
1873			}
1874
1875			#ifdef RC_ANYOFM
1876			static int compare_anyofm_multiline(int anchored, Arrow a1, Arrow a2)
1877			{
1878			unsigned char req;
1879			int i;
1880			BitFlag bf;
1881			Arrow tail1, tail2;
1882			unsigned char left[ANYOF_BITMAP_SIZE];
1883
1884			assert(a1->rn->type == ANYOFM);
1885			assert((a2->rn->type == MBOL) \|\| (a2->rn->type == MEOL));
1886
1887			if (!convert_anyofm_to_bitmap(a1, left))
1888			{
1889			return compare_mismatch(anchored, a1, a2);
1890			}
1891
1892			init_bit_flag(&bf, '\n');
1893			for (i = 0; i < ANYOF_BITMAP_SIZE; ++i)
1894			{
1895			req = (i != bf.offs) ? 0 : bf.mask;
1896			if (left[i] != req)
1897			{
1898			return compare_mismatch(anchored, a1, a2);
1899			}
1900			}
1901
1902			tail1 = *a1;
1903			if (bump_regular(&tail1) <= 0)
1904			{
1905			return -1;
1906			}
1907
1908			tail2 = *a2;
1909			if (bump_regular(&tail2) <= 0)
1910			{
1911			return -1;
1912			}
1913
1914			return compare(1, &tail1, &tail2);
1915			}
1916			#endif
1917
1918			#ifdef RC_NANYOFM
1919			static int compare_nanyofm_multiline(int anchored, Arrow a1, Arrow a2)
1920			{
1921			unsigned char req;
1922			int i;
1923			BitFlag bf;
1924			Arrow tail1, tail2;
1925			unsigned char left[ANYOF_BITMAP_SIZE];
1926
1927			assert(a1->rn->type == NANYOFM);
1928			assert((a2->rn->type == MBOL) \|\| (a2->rn->type == MEOL));
1929
1930			if (!convert_anyofm_to_bitmap(a1, left))
1931			{
1932			return compare_mismatch(anchored, a1, a2);
1933			}
1934
1935			for (i = 0; i < ANYOF_BITMAP_SIZE; ++i)
1936			{
1937			left[i] = ~left[i];
1938			}
1939
1940			init_bit_flag(&bf, '\n');
1941			for (i = 0; i < ANYOF_BITMAP_SIZE; ++i)
1942			{
1943			req = (i != bf.offs) ? 0 : bf.mask;
1944			if (left[i] != req)
1945			{
1946			return compare_mismatch(anchored, a1, a2);
1947			}
1948			}
1949
1950			tail1 = *a1;
1951			if (bump_regular(&tail1) <= 0)
1952			{
1953			return -1;
1954			}
1955
1956			tail2 = *a2;
1957			if (bump_regular(&tail2) <= 0)
1958			{
1959			return -1;
1960			}
1961
1962			return compare(1, &tail1, &tail2);
1963			}
1964			#endif
1965
1966	385		static int compare_anyof_anyof(int anchored, Arrow a1, Arrow a2)
1967			{
1968			int extra_left;
1969
1970			/* fprintf(stderr, "enter compare_anyof_anyof(%d\n", anchored); */
1971
1972			assert((a1->rn->type == ANYOF) \|\| (a1->rn->type == ANYOFD));
1973			assert((a2->rn->type == ANYOF) \|\| (a2->rn->type == ANYOFD));
1974
1975	385		extra_left = ANYOF_FLAGS(a1->rn) &
1976			ANYOF_SHARED_d_UPPER_LATIN1_UTF8_STRING_MATCHES_non_d_RUNTIME_USER_PROP;
1977	385	100	if ((extra_left \|\| (a1->rn->flags & ANYOF_MATCHES_ALL_ABOVE_BITMAP)) &&
		100
		100
1978	151		!(a2->rn->flags & ANYOF_MATCHES_ALL_ABOVE_BITMAP))
1979			{
1980			U32 m1, m2;
1981			int cr1, cr2;
1982
1983			/* fprintf(stderr, "comparing invlists: left flags = 0x%x, right flags = 0x%x\n", (int)(a1->rn->flags), (int)(a2->rn->flags)); */
1984			/* before recognizing standard invlists, check whether they
1985			aren't the same - this duplicates the code to get to the
1986			invlist, but works even for non-standard ones,
1987			e.g. [\da] */
1988	96	100	if ((a1->rn->flags & ANYOF_SHARED_d_UPPER_LATIN1_UTF8_STRING_MATCHES_non_d_RUNTIME_USER_PROP) &&
		100
1989	91		(a2->rn->flags & ANYOF_SHARED_d_UPPER_LATIN1_UTF8_STRING_MATCHES_non_d_RUNTIME_USER_PROP))
1990			{
1991	88		SV *invlist1 = get_invlist_sv(a1);
1992	88		SV *invlist2 = get_invlist_sv(a2);
1993	88	50	if (invlist1 && invlist2)
		50
1994			{
1995	88		UV ill1 = get_invlist_len(invlist1);
1996	88		UV ill2 = get_invlist_len(invlist2);
1997	88	50	if (ill1 && (ill1 == ill2))
		50
1998			{
1999	88		UV *ila1 = invlist_array(invlist1);
2000	88		UV *ila2 = invlist_array(invlist2);
2001	88	50	if (!memcmp(ila1, ila2, ill1 * sizeof(UV)))
2002			{
2003	91		return compare_bitmaps(anchored, a1, a2, 0, 0);
2004			}
2005			}
2006			}
2007			}
2008
2009	8		cr1 = convert_map(a1, &m1);
2010	8	50	if (cr1 == -1)
2011			{
2012	0		return -1;
2013			}
2014
2015	8		cr2 = convert_map(a2, &m2);
2016	8	50	if (cr2 == -1)
2017			{
2018	0		return -1;
2019			}
2020
2021			/* clearly this hould happen at a lower level, but there it
2022			breaks other paths... */
2023	8	50	if (m2 & NOT_ALNUM_BLOCK)
2024			{
2025	0		m2 \|= NOT_ALPHA_BLOCK \| NOT_NUMBER_BLOCK;
2026	0		m2 = extend_mask(m2);
2027			}
2028
2029	8	50	if (!cr1 \|\| !cr2 \|\| (m1 & ~m2))
		50
		100
2030			{
2031			/* fprintf(stderr, "cr1 = %d, cr2 = %d, m1 = 0x%x, m2 = 0x%x\n",
2032			cr1, cr2, (unsigned)m1, (unsigned)m2); */
2033	8		return compare_mismatch(anchored, a1, a2);
2034			}
2035			}
2036
2037	294		return compare_bitmaps(anchored, a1, a2, 0, 0);
2038			}
2039
2040			#ifdef RC_ANYOFM
2041			static int compare_anyof_anyofm(int anchored, Arrow a1, Arrow a2)
2042			{
2043			unsigned char right[ANYOF_BITMAP_SIZE];
2044
2045			/* fprintf(stderr, "enter compare_anyof_anyofm(%d\n", anchored); */
2046
2047			assert((a1->rn->type == ANYOF) \|\| (a1->rn->type == ANYOFD));
2048			assert(a2->rn->type == ANYOFM);
2049
2050			if (ANYOF_FLAGS(a1->rn) & ANYOF_SHARED_d_UPPER_LATIN1_UTF8_STRING_MATCHES_non_d_RUNTIME_USER_PROP)
2051			{
2052			return compare_mismatch(anchored, a1, a2);
2053			}
2054
2055			if (!convert_anyofm_to_bitmap(a2, right))
2056			{
2057			return compare_mismatch(anchored, a1, a2);
2058			}
2059
2060			return compare_bitmaps(anchored, a1, a2, 0, right);
2061			}
2062
2063			static int compare_anyofm_anyof(int anchored, Arrow a1, Arrow a2)
2064			{
2065			unsigned char left[ANYOF_BITMAP_SIZE];
2066
2067			/* fprintf(stderr, "enter compare_anyofm_anyof(%d\n", anchored); */
2068
2069			assert(a1->rn->type == ANYOFM);
2070			assert((a2->rn->type == ANYOF) \|\| (a2->rn->type == ANYOFD));
2071
2072			if (!convert_anyofm_to_bitmap(a1, left))
2073			{
2074			return compare_mismatch(anchored, a1, a2);
2075			}
2076
2077			return compare_bitmaps(anchored, a1, a2, left, 0);
2078			}
2079
2080			static int compare_anyofm_anyofm(int anchored, Arrow a1, Arrow a2)
2081			{
2082			unsigned char left[ANYOF_BITMAP_SIZE];
2083			unsigned char right[ANYOF_BITMAP_SIZE];
2084
2085			assert(a1->rn->type == ANYOFM);
2086			assert(a2->rn->type == ANYOFM);
2087
2088			if (!convert_anyofm_to_bitmap(a1, left))
2089			{
2090			return compare_mismatch(anchored, a1, a2);
2091			}
2092
2093			if (!convert_anyofm_to_bitmap(a2, right))
2094			{
2095			return compare_mismatch(anchored, a1, a2);
2096			}
2097
2098			return compare_bitmaps(anchored, a1, a2, left, right);
2099			}
2100			#endif
2101
2102			#ifdef RC_NANYOFM
2103			static int compare_anyof_nanyofm(int anchored, Arrow a1, Arrow a2)
2104			{
2105			int i;
2106			unsigned char right[ANYOF_BITMAP_SIZE];
2107
2108			/* fprintf(stderr, "enter compare_anyof_nanyofn(%d\n", anchored); */
2109
2110			assert((a1->rn->type == ANYOF) \|\| (a1->rn->type == ANYOFD));
2111			assert(a2->rn->type == NANYOFM);
2112
2113			/* fprintf(stderr, "left flags = 0x%x\n", a1->rn->flags); */
2114
2115			if ((a1->rn->flags & ANYOF_SHARED_d_UPPER_LATIN1_UTF8_STRING_MATCHES_non_d_RUNTIME_USER_PROP) \|\|
2116			((a1->rn->flags & ANYOF_SHARED_d_MATCHES_ALL_NON_UTF8_NON_ASCII_non_d_WARN_SUPER) &&
2117			!(a1->rn->flags & ANYOF_INVERT)))
2118			{
2119			return compare_mismatch(anchored, a1, a2);
2120			}
2121
2122			if (!convert_anyofm_to_bitmap(a2, right))
2123			{
2124			return compare_mismatch(anchored, a1, a2);
2125			}
2126
2127			for (i = 0; i < ANYOF_BITMAP_SIZE; ++i)
2128			{
2129			right[i] = ~right[i];
2130			}
2131
2132			return compare_bitmaps(anchored, a1, a2, 0, right);
2133			}
2134
2135			static int compare_anyofm_nanyofm(int anchored, Arrow a1, Arrow a2)
2136			{
2137			int i;
2138			unsigned char left[ANYOF_BITMAP_SIZE];
2139			unsigned char right[ANYOF_BITMAP_SIZE];
2140
2141			assert(a1->rn->type == ANYOFM);
2142			assert(a2->rn->type == NANYOFM);
2143
2144			if (!convert_anyofm_to_bitmap(a1, left))
2145			{
2146			return compare_mismatch(anchored, a1, a2);
2147			}
2148
2149			if (!convert_anyofm_to_bitmap(a2, right))
2150			{
2151			return compare_mismatch(anchored, a1, a2);
2152			}
2153
2154			for (i = 0; i < ANYOF_BITMAP_SIZE; ++i)
2155			{
2156			right[i] = ~right[i];
2157			}
2158
2159			return compare_bitmaps(anchored, a1, a2, left, right);
2160			}
2161
2162			static int compare_nanyofm_nanyofm(int anchored, Arrow a1, Arrow a2)
2163			{
2164			unsigned char left[ANYOF_BITMAP_SIZE];
2165			unsigned char right[ANYOF_BITMAP_SIZE];
2166
2167			assert(a1->rn->type == NANYOFM);
2168			assert(a2->rn->type == NANYOFM);
2169
2170			if (!convert_anyofm_to_bitmap(a1, left))
2171			{
2172			return compare_mismatch(anchored, a1, a2);
2173			}
2174
2175			if (!convert_anyofm_to_bitmap(a2, right))
2176			{
2177			return compare_mismatch(anchored, a1, a2);
2178			}
2179
2180			return compare_negative_bitmaps(anchored, a1, a2, left, right);
2181			}
2182			#endif
2183
2184			/* compare_bitmaps could replace this method, but when a class
2185			contains just a few characters, it seems more natural to compare
2186			them explicitly */
2187	0		static int compare_short_byte_class(int anchored, Arrow a1, Arrow a2,
2188			ByteClass *left)
2189			{
2190			BitFlag bf;
2191			int i;
2192
2193	0	0	for (i = 0; i < left->expl_size; ++i)
2194			{
2195	0		init_bit_flag(&bf, (unsigned char)left->expl[i]);
2196	0	0	if (!(get_bitmap_byte(a2->rn, bf.offs) & bf.mask))
2197			{
2198	0		return compare_mismatch(anchored, a1, a2);
2199			}
2200			}
2201
2202	0		return compare_tails(anchored, a1, a2);
2203			}
2204
2205	2		static int compare_right_full(int anchored, Arrow a1, Arrow a2)
2206			{
2207			int i;
2208
2209	34	100	for (i = 0; i < 16; ++i)
2210			{
2211	32	50	if (!(get_bitmap_byte(a2->rn, i) & 0xff))
2212			{
2213	0		return compare_mismatch(anchored, a1, a2);
2214			}
2215			}
2216
2217	2		return compare_tails(anchored, a1, a2);
2218			}
2219
2220	1398		static int compare_posix_posix(int anchored, Arrow a1, Arrow a2)
2221			{
2222			U32 m1, m2;
2223			int cr1, cr2;
2224
2225			/* fprintf(stderr, "enter compare_posix_posix\n"); */
2226
2227	1398		cr1 = convert_class(a1, &m1);
2228	1398		cr2 = convert_class(a2, &m2);
2229	1398	50	if (!cr1 \|\| !cr2 \|\| (m1 & ~m2))
		50
		100
2230			{
2231	259		return compare_mismatch(anchored, a1, a2);
2232			}
2233
2234	1398		return compare_tails(anchored, a1, a2);
2235			}
2236
2237	693		static int compare_posix_negative_posix(int anchored, Arrow a1, Arrow a2)
2238			{
2239			U32 m1, m2;
2240			int cr1, cr2;
2241
2242			/* fprintf(stderr, "enter compare_posix_negative_posix\n"); */
2243
2244	693		cr1 = convert_class(a1, &m1);
2245	693		cr2 = convert_class(a2, &m2);
2246	693	50	if (!cr1 \|\| !cr2)
		50
2247			{
2248	0		return compare_mismatch(anchored, a1, a2);
2249			}
2250
2251			/* vertical space is not a strict subset of space, but it does
2252			have space elements, so we have to require space on the right */
2253	693	100	if ((m1 & VERTICAL_SPACE_BLOCK) && !(m2 & VERTICAL_SPACE_BLOCK))
		100
2254			{
2255	72		m1 \|= SPACE_BLOCK;
2256			}
2257
2258	693	100	if (m1 & m2)
2259			{
2260	189		return compare_mismatch(anchored, a1, a2);
2261			}
2262
2263	693		return compare_tails(anchored, a1, a2);
2264			}
2265
2266	494		static int compare_negative_posix_negative_posix(int anchored, Arrow a1, Arrow a2)
2267			{
2268			U32 m1, m2;
2269			int cr1, cr2;
2270
2271			assert((a1->rn->type == NPOSIXD) \|\| (a1->rn->type == NPOSIXU) \|\|
2272			(a1->rn->type == NPOSIXA));
2273			assert((a2->rn->type == NPOSIXD) \|\| (a2->rn->type == NPOSIXU) \|\|
2274			(a2->rn->type == NPOSIXA));
2275
2276			/* fprintf(stderr, "enter compare_negative_posix_negative_posix\n"); */
2277
2278	494		cr1 = convert_negative_class(a1, &m1);
2279	494		cr2 = convert_negative_class(a2, &m2);
2280	494	50	if (!cr2 \|\| !cr2 \|\| (m1 & ~m2))
		50
		100
2281			{
2282	128		return compare_mismatch(anchored, a1, a2);
2283			}
2284
2285	494		return compare_tails(anchored, a1, a2);
2286			}
2287
2288	891		static int compare_exact_posix(int anchored, Arrow a1, Arrow a2)
2289			{
2290			char *seq;
2291
2292			assert((a1->rn->type == EXACT) \|\| (a1->rn->type == EXACTF) \|\|
2293			(a1->rn->type == EXACTFU));
2294			assert((a2->rn->type == POSIXD) \|\| (a2->rn->type == POSIXU) \|\|
2295			(a2->rn->type == POSIXA));
2296
2297	891		seq = GET_LITERAL(a1);
2298
2299	891	100	if (!_generic_isCC_A(*seq, a2->rn->flags))
2300			{
2301	59		return compare_mismatch(anchored, a1, a2);
2302			}
2303
2304	832		return compare_tails(anchored, a1, a2);
2305			}
2306
2307	39		static int compare_exactf_posix(int anchored, Arrow a1, Arrow a2)
2308			{
2309			char *seq;
2310			char unf[2];
2311			int i;
2312
2313			assert((a1->rn->type == EXACTF) \|\| (a1->rn->type == EXACTFU));
2314			assert(a2->rn->type == POSIXD);
2315
2316	39		seq = GET_LITERAL(a1);
2317	39		init_unfolded(unf, *seq);
2318
2319	111	100	for (i = 0; i < 2; ++i)
2320			{
2321	75	100	if (!_generic_isCC_A(unf[i], a2->rn->flags))
2322			{
2323	3		return compare_mismatch(anchored, a1, a2);
2324			}
2325			}
2326
2327	39		return compare_tails(anchored, a1, a2);
2328			}
2329
2330	783		static int compare_exact_negative_posix(int anchored, Arrow a1, Arrow a2)
2331			{
2332			char *seq;
2333
2334			assert(a1->rn->type == EXACT);
2335			assert((a2->rn->type == NPOSIXD) \|\| (a2->rn->type == NPOSIXU) \|\|
2336			(a2->rn->type == NPOSIXA));
2337
2338	783		seq = GET_LITERAL(a1);
2339
2340	783	100	if (_generic_isCC_A(*seq, a2->rn->flags))
2341			{
2342	22		return compare_mismatch(anchored, a1, a2);
2343			}
2344
2345	761		return compare_tails(anchored, a1, a2);
2346			}
2347
2348	61		static int compare_exactf_negative_posix(int anchored, Arrow a1, Arrow a2)
2349			{
2350			char *seq;
2351			char unf[2];
2352			int i;
2353
2354			assert((a1->rn->type == EXACTF) \|\| (a1->rn->type == EXACTFU));
2355			assert((a2->rn->type == NPOSIXD) \|\| (a2->rn->type == NPOSIXU) \|\|
2356			(a2->rn->type == NPOSIXA));
2357
2358	61		seq = GET_LITERAL(a1);
2359	61		init_unfolded(unf, *seq);
2360
2361	181	100	for (i = 0; i < 2; ++i)
2362			{
2363	121	100	if (_generic_isCC_A(unf[i], a2->rn->flags))
2364			{
2365	1		return compare_mismatch(anchored, a1, a2);
2366			}
2367			}
2368
2369	61		return compare_tails(anchored, a1, a2);
2370			}
2371
2372	13		static int compare_reg_any_anyof(int anchored, Arrow a1, Arrow a2)
2373			{
2374			assert(a1->rn->type == REG_ANY);
2375			assert((a2->rn->type == ANYOF) \|\| (a2->rn->type == ANYOFD));
2376
2377	13		return compare_bitmaps(anchored, a1, a2, ndot.nbitmap, 0);
2378			}
2379
2380	130		static int compare_posix_anyof(int anchored, Arrow a1, Arrow a2)
2381			{
2382			U32 left_block;
2383			unsigned char *b;
2384
2385			/* fprintf(stderr, "enter compare_posix_anyof\n"); */
2386
2387			assert((a1->rn->type == POSIXD) \|\| (a1->rn->type == POSIXU) \|\|
2388			(a1->rn->type == POSIXA));
2389			assert((a2->rn->type == ANYOF) \|\| (a2->rn->type == ANYOFD));
2390
2391	130	50	if (!convert_class_narrow(a1, &left_block))
2392			{
2393	0		return compare_mismatch(anchored, a1, a2);
2394			}
2395
2396			/* fprintf(stderr, "right flags = %d\n", a2->rn->flags); */
2397
2398	130	100	if (!(a2->rn->flags & ANYOF_MATCHES_ALL_ABOVE_BITMAP))
2399			{
2400			U32 right_map;
2401
2402			#ifndef RC_UNCOND_CHARCLASS
2403			/* apparently a special case... */
2404	39	100	if (a2->rn->flags & ANYOF_INVERT)
2405			{
2406	33		return compare_mismatch(anchored, a1, a2);
2407			}
2408			#endif
2409
2410	38		int cr = convert_map(a2, &right_map);
2411	38	50	if (cr == -1)
2412			{
2413	0		return -1;
2414			}
2415
2416	38	50	if (!cr \|\| !(right_map & left_block))
		100
2417			{
2418	38		return compare_mismatch(anchored, a1, a2);
2419			}
2420			}
2421
2422			/* fprintf(stderr, "left flags = %d\n", a1->rn->flags); */
2423
2424	97	50	if (a1->rn->flags >= SIZEOF_ARRAY(posix_regclass_bitmaps))
2425			{
2426	0		return compare_mismatch(anchored, a1, a2);
2427			}
2428
2429	97		b = posix_regclass_bitmaps[a1->rn->flags];
2430	97	50	if (!b)
2431			{
2432	0		return compare_mismatch(anchored, a1, a2);
2433			}
2434
2435	130		return compare_bitmaps(anchored, a1, a2, b, 0);
2436			}
2437
2438	68		static int compare_negative_posix_anyof(int anchored, Arrow a1, Arrow a2)
2439			{
2440			U32 left_block;
2441			unsigned char *b;
2442
2443			/* fprintf(stderr, "enter compare_negative_posix_anyof\n"); */
2444
2445			assert((a1->rn->type == NPOSIXD) \|\| (a1->rn->type == NPOSIXU) \|\|
2446			(a1->rn->type == NPOSIXA));
2447			assert((a2->rn->type == ANYOF) \|\| (a2->rn->type == ANYOFD));
2448
2449	68	50	if (!convert_class_narrow(a1, &left_block))
2450			{
2451	0		return compare_mismatch(anchored, a1, a2);
2452			}
2453
2454			/* fprintf(stderr, "right flags = 0x%x\n", a2->rn->flags); */
2455
2456	68		left_block = EVERY_BLOCK & ~left_block;
2457
2458			/* fprintf(stderr, "left %d -> 0x%x\n", a1->rn->flags, (unsigned)left_block); */
2459
2460	68	100	if (!(a2->rn->flags & ANYOF_MATCHES_ALL_ABOVE_BITMAP))
2461			{
2462			U32 right_map;
2463
2464			#ifndef RC_UNCOND_CHARCLASS
2465			/* analogically with compare_posix_anyof but untested */
2466	19	100	if (a2->rn->flags & ANYOF_INVERT)
2467			{
2468	8		return compare_mismatch(anchored, a1, a2);
2469			}
2470			#endif
2471
2472	18		int cr = convert_map(a2, &right_map);
2473	18	50	if (cr == -1)
2474			{
2475	0		return -1;
2476			}
2477
2478			#ifdef RC_UNCOND_CHARCLASS
2479			if (a2->rn->flags & ANYOF_INVERT)
2480			{
2481			right_map = EVERY_BLOCK & ~right_map;
2482			}
2483			#endif
2484
2485			/* fprintf(stderr, "right map = 0x%x\n", (unsigned)right_map); */
2486
2487	18	50	if (!cr \|\| !(right_map & left_block))
		100
2488			{
2489	18		return compare_mismatch(anchored, a1, a2);
2490			}
2491			}
2492
2493	60	50	if (a1->rn->flags >= SIZEOF_ARRAY(posix_regclass_bitmaps))
2494			{
2495	0		return compare_mismatch(anchored, a1, a2);
2496			}
2497
2498	60		b = posix_regclass_nbitmaps[a1->rn->flags];
2499	60	50	if (!b)
2500			{
2501	0		return compare_mismatch(anchored, a1, a2);
2502			}
2503
2504	68		return compare_bitmaps(anchored, a1, a2, b, 0);
2505			}
2506
2507	750		static int compare_exact_anyof(int anchored, Arrow a1, Arrow a2)
2508			{
2509			BitFlag bf;
2510			char *seq;
2511
2512			/* fprintf(stderr, "enter compare_exact_anyof(%d, \n", anchored); */
2513
2514			assert(a1->rn->type == EXACT);
2515			assert((a2->rn->type == ANYOF) \|\| (a2->rn->type == ANYOFD));
2516
2517	750		seq = GET_LITERAL(a1);
2518	750		init_bit_flag(&bf, (unsigned char)(*seq));
2519
2520	750	100	if (!(get_bitmap_byte(a2->rn, bf.offs) & bf.mask))
2521			{
2522	160		return compare_mismatch(anchored, a1, a2);
2523			}
2524
2525	750		return compare_tails(anchored, a1, a2);
2526			}
2527
2528	38		static int compare_exactf_anyof(int anchored, Arrow a1, Arrow a2)
2529			{
2530			BitFlag bf;
2531			char *seq;
2532			char unf[2];
2533			int i;
2534
2535			/* fprintf(stderr, "enter compare_exactf_anyof(%d, \n", anchored); */
2536
2537			assert((a1->rn->type == EXACTF) \|\| (a1->rn->type == EXACTFU));
2538			assert((a2->rn->type == ANYOF) \|\| (a2->rn->type == ANYOFD));
2539
2540	38		seq = GET_LITERAL(a1);
2541	38		init_unfolded(unf, *seq);
2542
2543	113	100	for (i = 0; i < 2; ++i)
2544			{
2545	76		init_bit_flag(&bf, (unsigned char)unf[i]);
2546	76	100	if (!(get_bitmap_byte(a2->rn, bf.offs) & bf.mask))
2547			{
2548	1		return compare_mismatch(anchored, a1, a2);
2549			}
2550			}
2551
2552	38		return compare_tails(anchored, a1, a2);
2553			}
2554
2555			#ifdef RC_ANYOFM
2556			static int compare_exact_anyofm(int anchored, Arrow a1, Arrow a2)
2557			{
2558			char *seq;
2559			unsigned char right[ANYOF_BITMAP_SIZE];
2560			BitFlag bf;
2561
2562			/* fprintf(stderr, "enter compare_exact_anyofm(%d, \n", anchored); */
2563
2564			assert(a1->rn->type == EXACT);
2565			assert(a2->rn->type == ANYOFM);
2566
2567			seq = GET_LITERAL(a1);
2568			init_bit_flag(&bf, *seq);
2569
2570			if (!convert_anyofm_to_bitmap(a2, right))
2571			{
2572			return compare_mismatch(anchored, a1, a2);
2573			}
2574
2575			if (right[bf.offs] & bf.mask)
2576			{
2577			return compare_tails(anchored, a1, a2);
2578			}
2579
2580			return compare_mismatch(anchored, a1, a2);
2581			}
2582
2583			static int compare_exactf_anyofm(int anchored, Arrow a1, Arrow a2)
2584			{
2585			char *seq;
2586			int i;
2587			char left[2];
2588			unsigned char right[ANYOF_BITMAP_SIZE];
2589			BitFlag bf;
2590
2591			/* fprintf(stderr, "enter compare_exactf_anyofm(%d, \n", anchored); */
2592
2593			assert((a1->rn->type == EXACTF) \|\| (a1->rn->type == EXACTFU));
2594			assert(a2->rn->type == ANYOFM);
2595
2596			seq = GET_LITERAL(a1);
2597			init_unfolded(left, *seq);
2598
2599			if (!convert_anyofm_to_bitmap(a2, right))
2600			{
2601			return compare_mismatch(anchored, a1, a2);
2602			}
2603
2604			for (i = 0; i < 2; ++i)
2605			{
2606			init_bit_flag(&bf, left[i]);
2607			if (!(right[bf.offs] & bf.mask))
2608			{
2609			return compare_mismatch(anchored, a1, a2);
2610			}
2611			}
2612
2613			return compare_tails(anchored, a1, a2);
2614			}
2615			#endif
2616
2617			#ifdef RC_NANYOFM
2618			static int compare_exact_nanyofm(int anchored, Arrow a1, Arrow a2)
2619			{
2620			char *seq;
2621			unsigned char right[ANYOF_BITMAP_SIZE];
2622			BitFlag bf;
2623
2624			assert(a1->rn->type == EXACT);
2625			assert(a2->rn->type == NANYOFM);
2626
2627			seq = GET_LITERAL(a1);
2628			init_bit_flag(&bf, *seq);
2629
2630			if (!convert_anyofm_to_bitmap(a2, right))
2631			{
2632			return compare_mismatch(anchored, a1, a2);
2633			}
2634
2635			if (right[bf.offs] & bf.mask)
2636			{
2637			return compare_mismatch(anchored, a1, a2);
2638			}
2639
2640			return compare_tails(anchored, a1, a2);
2641			}
2642
2643			static int compare_exactf_nanyofm(int anchored, Arrow a1, Arrow a2)
2644			{
2645			char *seq;
2646			int i;
2647			char left[2];
2648			unsigned char right[ANYOF_BITMAP_SIZE];
2649			BitFlag bf;
2650
2651			assert((a1->rn->type == EXACTF) \|\| (a1->rn->type == EXACTFU));
2652			assert(a2->rn->type == NANYOFM);
2653
2654			seq = GET_LITERAL(a1);
2655			init_unfolded(left, *seq);
2656
2657			if (!convert_anyofm_to_bitmap(a2, right))
2658			{
2659			return compare_mismatch(anchored, a1, a2);
2660			}
2661
2662			for (i = 0; i < ANYOF_BITMAP_SIZE; ++i)
2663			{
2664			right[i] = ~right[i];
2665			}
2666
2667			for (i = 0; i < 2; ++i)
2668			{
2669			init_bit_flag(&bf, left[i]);
2670			if (!(right[bf.offs] & bf.mask))
2671			{
2672			return compare_mismatch(anchored, a1, a2);
2673			}
2674			}
2675
2676			return compare_tails(anchored, a1, a2);
2677			}
2678
2679			static int compare_posix_nanyofm(int anchored, Arrow a1, Arrow a2)
2680			{
2681			int i;
2682			unsigned char *b;
2683			unsigned char right[ANYOF_BITMAP_SIZE];
2684
2685			assert((a1->rn->type == POSIXD) \|\| (a1->rn->type == POSIXU) \|\|
2686			(a1->rn->type == POSIXA));
2687			assert(a2->rn->type == NANYOFM);
2688
2689			if (a1->rn->flags >= SIZEOF_ARRAY(posix_regclass_bitmaps))
2690			{
2691			return compare_mismatch(anchored, a1, a2);
2692			}
2693
2694			b = posix_regclass_bitmaps[a1->rn->flags];
2695			if (!b)
2696			{
2697			return compare_mismatch(anchored, a1, a2);
2698			}
2699
2700			if (!convert_anyofm_to_bitmap(a2, right))
2701			{
2702			return compare_mismatch(anchored, a1, a2);
2703			}
2704
2705			for (i = 0; i < ANYOF_BITMAP_SIZE; ++i)
2706			{
2707			right[i] = ~right[i];
2708			}
2709
2710			return compare_bitmaps(anchored, a1, a2, b, right);
2711			}
2712
2713			static int compare_negative_posix_nanyofm(int anchored, Arrow a1, Arrow a2)
2714			{
2715			int i;
2716			unsigned char *b;
2717			unsigned char right[ANYOF_BITMAP_SIZE];
2718
2719			assert((a1->rn->type == NPOSIXD) \|\| (a1->rn->type == NPOSIXU) \|\|
2720			(a1->rn->type == NPOSIXA));
2721			assert(a2->rn->type == NANYOFM);
2722
2723			if (a1->rn->flags >= SIZEOF_ARRAY(posix_regclass_bitmaps))
2724			{
2725			return compare_mismatch(anchored, a1, a2);
2726			}
2727
2728			/* positive, because negative bitmaps are compared below */
2729			b = posix_regclass_bitmaps[a1->rn->flags];
2730			if (!b)
2731			{
2732			return compare_mismatch(anchored, a1, a2);
2733			}
2734
2735			if (!convert_anyofm_to_bitmap(a2, right))
2736			{
2737			return compare_mismatch(anchored, a1, a2);
2738			}
2739
2740			return compare_negative_bitmaps(anchored, a1, a2, b, right);
2741			}
2742			#endif
2743
2744	10		static int compare_exact_lnbreak(int anchored, Arrow a1, Arrow a2)
2745			{
2746			char *cur;
2747			char *next;
2748
2749			assert((a1->rn->type == EXACT) \|\| (a1->rn->type == EXACTF) \|\|
2750			(a1->rn->type == EXACTFU));
2751			assert(a2->rn->type == LNBREAK);
2752
2753	10		cur = GET_LITERAL(a1);
2754
2755			/* first, check 2-character newline */
2756	10	100	if ((*cur == '\r') && ((a1->spent + 1) < a1->rn->flags))
		100
2757			{
2758			/* we're ignoring the possibility the \n is in a different
2759			node, but that probably doesn't happen */
2760	2		next = (((char *)(a1->rn + 1)) + a1->spent + 1);
2761	2	50	if (*next == '\n')
2762			{
2763	2		++(a1->spent);
2764	2		return compare_tails(anchored, a1, a2);
2765			}
2766			}
2767
2768			/* otherwise, check vertical space */
2769	8	100	if (!_generic_isCC_A(*cur, _CC_VERTSPACE))
2770			{
2771	4		return compare_mismatch(anchored, a1, a2);
2772			}
2773
2774	4		return compare_tails(anchored, a1, a2);
2775			}
2776
2777	627		static int compare_exact_byte_class(int anchored, Arrow a1, Arrow a2,
2778			char *lookup)
2779			{
2780			char *seq;
2781
2782			assert((a1->rn->type == EXACT) \|\| (a1->rn->type == EXACTF) \|\| (a1->rn->type == EXACTFU));
2783
2784	627		seq = GET_LITERAL(a1);
2785
2786	627	100	if (!lookup[(unsigned char)(*seq)])
2787			{
2788	31		return compare_mismatch(anchored, a1, a2);
2789			}
2790
2791	596		return compare_tails(anchored, a1, a2);
2792			}
2793
2794	33		static int compare_exact_multiline(int anchored, Arrow a1, Arrow a2)
2795			{
2796			assert((a1->rn->type == EXACT) \|\| (a1->rn->type == EXACTF) \|\|
2797			(a1->rn->type == EXACTFU));
2798			assert((a2->rn->type == MBOL) \|\| (a2->rn->type == MEOL));
2799
2800	33		return compare_exact_byte_class(anchored, a1, a2,
2801			ndot.lookup);
2802			}
2803
2804	8		static int compare_sany_anyof(int anchored, Arrow a1, Arrow a2)
2805			{
2806			/* fprintf(stderr, "enter compare_sany_anyof\n"); */
2807
2808			assert(a1->rn->type == SANY);
2809			assert((a2->rn->type == ANYOF) \|\| (a2->rn->type == ANYOFD));
2810
2811			/* fprintf(stderr, "left flags = 0x%x, right flags = 0x%x\n",
2812			a1->rn->flags, a2->rn->flags); */
2813
2814	8	100	if (a2->rn->flags & ANYOF_MATCHES_ALL_ABOVE_BITMAP)
2815			{
2816	2		return compare_right_full(anchored, a1, a2);
2817			}
2818
2819	6		return compare_mismatch(anchored, a1, a2);
2820			}
2821
2822	68		static int compare_anyof_reg_any(int anchored, Arrow a1, Arrow a2)
2823			{
2824			assert((a1->rn->type == ANYOF) \|\| (a1->rn->type == ANYOFD));
2825			assert(a2->rn->type == REG_ANY);
2826
2827	68		return compare_bitmaps(anchored, a1, a2, 0, ndot.nbitmap);
2828			}
2829
2830			#ifdef RC_ANYOFM
2831			static int compare_anyofm_reg_any(int anchored, Arrow a1, Arrow a2)
2832			{
2833			unsigned char left[ANYOF_BITMAP_SIZE];
2834
2835			assert(a1->rn->type == ANYOFM);
2836			assert(a2->rn->type == REG_ANY);
2837
2838			if (!convert_anyofm_to_bitmap(a1, left))
2839			{
2840			return compare_mismatch(anchored, a1, a2);
2841			}
2842
2843			return compare_bitmaps(anchored, a1, a2, left, ndot.nbitmap);
2844			}
2845			#endif
2846
2847			#ifdef RC_NANYOFM
2848			static int compare_nanyofm_reg_any(int anchored, Arrow a1, Arrow a2)
2849			{
2850			unsigned char left[ANYOF_BITMAP_SIZE];
2851
2852			assert(a1->rn->type == NANYOFM);
2853			assert(a2->rn->type == REG_ANY);
2854
2855			if (!convert_anyofm_to_bitmap(a1, left))
2856			{
2857			return compare_mismatch(anchored, a1, a2);
2858			}
2859
2860			return compare_negative_bitmaps(anchored, a1, a2, left, ndot.bitmap);
2861			}
2862			#endif
2863
2864	5		static int compare_anyof_lnbreak(int anchored, Arrow a1, Arrow a2)
2865			{
2866			assert((a1->rn->type == ANYOF) \|\| (a1->rn->type == ANYOFD));
2867			assert(a2->rn->type == LNBREAK);
2868
2869	5		return compare_bitmaps(anchored, a1, a2, 0, vertical_whitespace.bitmap);
2870			}
2871
2872	594		static int compare_exact_reg_any(int anchored, Arrow a1, Arrow a2)
2873			{
2874			assert((a1->rn->type == EXACT) \|\| (a1->rn->type == EXACTF) \|\| (a1->rn->type == EXACTFU));
2875			assert(a2->rn->type == REG_ANY);
2876
2877	594		return compare_exact_byte_class(anchored, a1, a2, ndot.nlookup);
2878			}
2879
2880	97		static int compare_anyof_posix(int anchored, Arrow a1, Arrow a2)
2881			{
2882			unsigned char *b;
2883
2884			/* fprintf(stderr, "enter compare_anyof_posix\n"); */
2885
2886			assert((a1->rn->type == ANYOF) \|\| (a1->rn->type == ANYOFD));
2887			assert((a2->rn->type == POSIXD) \|\| (a2->rn->type == POSIXU) \|\| (a2->rn->type == POSIXA));
2888
2889	97	50	if (a2->rn->flags >= SIZEOF_ARRAY(posix_regclass_bitmaps))
2890			{
2891			/* fprintf(stderr, "flags = %d\n", a2->rn->flags); */
2892	0		return compare_mismatch(anchored, a1, a2);
2893			}
2894
2895	97		b = posix_regclass_bitmaps[a2->rn->flags];
2896	97	50	if (!b)
2897			{
2898			/* fprintf(stderr, "no bitmap for flags = %d\n", a2->rn->flags); */
2899	0		return compare_mismatch(anchored, a1, a2);
2900			}
2901
2902	97		return compare_bitmaps(anchored, a1, a2, 0, b);
2903			}
2904
2905			#ifdef RC_ANYOFM
2906			static int compare_anyofm_posix(int anchored, Arrow a1, Arrow a2)
2907			{
2908			unsigned char *b;
2909			unsigned char left[ANYOF_BITMAP_SIZE];
2910
2911			/* fprintf(stderr, "enter compare_anyofm_posix\n"); */
2912
2913			assert(a1->rn->type == ANYOFM);
2914			assert((a2->rn->type == POSIXD) \|\| (a2->rn->type == POSIXU) \|\| (a2->rn->type == POSIXA));
2915
2916			if (!convert_anyofm_to_bitmap(a1, left))
2917			{
2918			return compare_mismatch(anchored, a1, a2);
2919			}
2920
2921			b = posix_regclass_bitmaps[a2->rn->flags];
2922			if (!b)
2923			{
2924			return compare_mismatch(anchored, a1, a2);
2925			}
2926
2927			return compare_bitmaps(anchored, a1, a2, left, b);
2928			}
2929			#endif
2930
2931			#ifdef RC_NANYOFM
2932			static int compare_nanyofm_posix(int anchored, Arrow a1, Arrow a2)
2933			{
2934			unsigned char *b;
2935			unsigned char left[ANYOF_BITMAP_SIZE];
2936
2937			assert(a1->rn->type == NANYOFM);
2938			assert((a2->rn->type == POSIXD) \|\| (a2->rn->type == POSIXU) \|\| (a2->rn->type == POSIXA));
2939
2940			if (!convert_anyofm_to_bitmap(a1, left))
2941			{
2942			return compare_mismatch(anchored, a1, a2);
2943			}
2944
2945			b = posix_regclass_nbitmaps[a2->rn->flags];
2946			if (!b)
2947			{
2948			return compare_mismatch(anchored, a1, a2);
2949			}
2950
2951			return compare_negative_bitmaps(anchored, a1, a2, left, b);
2952			}
2953			#endif
2954
2955	13		static int compare_anyof_posixa(int anchored, Arrow a1, Arrow a2)
2956			{
2957			unsigned char *b;
2958
2959			/* fprintf(stderr, "enter compare_anyof_posixa\n"); */
2960
2961			assert((a1->rn->type == ANYOF) \|\| (a1->rn->type == ANYOFD));
2962			assert(a2->rn->type == POSIXA);
2963
2964	13	100	if (ANYOF_FLAGS(a1->rn) & ANYOF_SHARED_d_UPPER_LATIN1_UTF8_STRING_MATCHES_non_d_RUNTIME_USER_PROP)
2965			{
2966	1		return compare_mismatch(anchored, a1, a2);
2967			}
2968
2969	12	50	if (a2->rn->flags >= SIZEOF_ARRAY(posix_regclass_bitmaps))
2970			{
2971			/* fprintf(stderr, "flags = %d\n", a2->rn->flags); */
2972	0		return compare_mismatch(anchored, a1, a2);
2973			}
2974
2975	12		b = posix_regclass_bitmaps[a2->rn->flags];
2976	12	50	if (!b)
2977			{
2978			/* fprintf(stderr, "no bitmap for flags = %d\n", a2->rn->flags); */
2979	0		return compare_mismatch(anchored, a1, a2);
2980			}
2981
2982	12		return compare_bitmaps(anchored, a1, a2, 0, b);
2983			}
2984
2985	75		static int compare_anyof_negative_posix(int anchored, Arrow a1, Arrow a2)
2986			{
2987			unsigned char *b;
2988
2989			/* fprintf(stderr, "enter compare_anyof_negative_posix\n"); */
2990
2991			assert((a1->rn->type == ANYOF) \|\| (a1->rn->type == ANYOFD));
2992			assert((a2->rn->type == NPOSIXD) \|\| (a2->rn->type == NPOSIXU) \|\|
2993			(a2->rn->type == NPOSIXA));
2994
2995	75	50	if (a2->rn->flags >= SIZEOF_ARRAY(posix_regclass_nbitmaps))
2996			{
2997			/* fprintf(stderr, "flags = %d\n", a2->rn->flags); */
2998	0		return compare_mismatch(anchored, a1, a2);
2999			}
3000
3001	75		b = posix_regclass_nbitmaps[a2->rn->flags];
3002	75	50	if (!b)
3003			{
3004			/* fprintf(stderr, "no negative bitmap for flags = %d\n", a2->rn->flags); */
3005	0		return compare_mismatch(anchored, a1, a2);
3006			}
3007
3008	75		return compare_bitmaps(anchored, a1, a2, 0, b);
3009			}
3010
3011			#ifdef RC_ANYOFM
3012			static int compare_anyofm_negative_posix(int anchored, Arrow a1, Arrow a2)
3013			{
3014			unsigned char *posix_bitmap;
3015			unsigned char anyof_bitmap[ANYOF_BITMAP_SIZE];
3016
3017			/* fprintf(stderr, "enter compare_anyofm_negative_posix\n"); */
3018
3019			assert(a1->rn->type == ANYOFM);
3020			assert((a2->rn->type == NPOSIXD) \|\| (a2->rn->type == NPOSIXU) \|\|
3021			(a2->rn->type == NPOSIXA));
3022
3023			if (!convert_anyofm_to_bitmap(a1, anyof_bitmap))
3024			{
3025			return compare_mismatch(anchored, a1, a2);
3026			}
3027
3028			if (a2->rn->flags >= SIZEOF_ARRAY(posix_regclass_nbitmaps))
3029			{
3030			/* fprintf(stderr, "flags = %d\n", a2->rn->flags); */
3031			return compare_mismatch(anchored, a1, a2);
3032			}
3033
3034			posix_bitmap = posix_regclass_nbitmaps[a2->rn->flags];
3035			if (!posix_bitmap)
3036			{
3037			/* fprintf(stderr, "no negative bitmap for flags = %d\n", a2->rn->flags); */
3038			return compare_mismatch(anchored, a1, a2);
3039			}
3040
3041			return compare_bitmaps(anchored, a1, a2, anyof_bitmap, posix_bitmap);
3042			}
3043			#endif
3044
3045			#ifdef RC_NANYOFM
3046			static int compare_nanyofm_negative_posix(int anchored, Arrow a1, Arrow a2)
3047			{
3048			unsigned char *posix_bitmap;
3049			unsigned char anyof_bitmap[ANYOF_BITMAP_SIZE];
3050
3051			assert(a1->rn->type == NANYOFM);
3052			assert((a2->rn->type == NPOSIXD) \|\| (a2->rn->type == NPOSIXU) \|\|
3053			(a2->rn->type == NPOSIXA));
3054
3055			if (!convert_anyofm_to_bitmap(a1, anyof_bitmap))
3056			{
3057			return compare_mismatch(anchored, a1, a2);
3058			}
3059
3060			if (a2->rn->flags >= SIZEOF_ARRAY(posix_regclass_bitmaps))
3061			{
3062			return compare_mismatch(anchored, a1, a2);
3063			}
3064
3065			posix_bitmap = posix_regclass_bitmaps[a2->rn->flags];
3066			if (!posix_bitmap)
3067			{
3068			return compare_mismatch(anchored, a1, a2);
3069			}
3070
3071			return compare_negative_bitmaps(anchored, a1, a2, anyof_bitmap, posix_bitmap);
3072			}
3073			#endif
3074
3075	256		static int compare_posix_reg_any(int anchored, Arrow a1, Arrow a2)
3076			{
3077			assert((a1->rn->type == POSIXD) \|\| (a1->rn->type == POSIXU) \|\|
3078			(a1->rn->type == POSIXA));
3079			assert(a2->rn->type == REG_ANY);
3080
3081	256		U8 flags = a1->rn->flags;
3082	256	50	if (flags >= SIZEOF_ARRAY(newline_posix_regclasses))
3083			{
3084			/* fprintf(stderr, "unknown POSIX character class %d\n", flags); */
3085	0		rc_error = "unknown POSIX character class";
3086	0		return -1;
3087			}
3088
3089	256	100	if (newline_posix_regclasses[flags])
3090			{
3091	54		return compare_mismatch(anchored, a1, a2);
3092			}
3093
3094	202		return compare_tails(anchored, a1, a2);
3095			}
3096
3097	125		static int compare_negative_posix_reg_any(int anchored, Arrow a1, Arrow a2)
3098			{
3099			assert((a1->rn->type == NPOSIXD) \|\| (a1->rn->type == NPOSIXU) \|\|
3100			(a1->rn->type == NPOSIXA));
3101			assert(a2->rn->type == REG_ANY);
3102
3103	125		U8 flags = a1->rn->flags;
3104	125	50	if (flags >= SIZEOF_ARRAY(newline_posix_regclasses))
3105			{
3106	0		rc_error = "unknown negative POSIX character class";
3107	0		return -1;
3108			}
3109
3110	125	100	if (!newline_posix_regclasses[flags])
3111			{
3112	82		return compare_mismatch(anchored, a1, a2);
3113			}
3114
3115	43		return compare_tails(anchored, a1, a2);
3116			}
3117
3118	25		static int compare_posix_lnbreak(int anchored, Arrow a1, Arrow a2)
3119			{
3120			assert((a1->rn->type == POSIXD) \|\| (a1->rn->type == POSIXU) \|\|
3121			(a1->rn->type == POSIXA));
3122			assert(a2->rn->type == LNBREAK);
3123
3124	25	100	if (a1->rn->flags != _CC_VERTSPACE)
3125			{
3126	7		return compare_mismatch(anchored, a1, a2);
3127			}
3128
3129	18		return compare_tails(anchored, a1, a2);
3130			}
3131
3132	6		static int compare_anyof_exact(int anchored, Arrow a1, Arrow a2)
3133			{
3134			BitFlag bf;
3135			char *seq;
3136			int i;
3137			unsigned char req;
3138
3139			assert((a1->rn->type == ANYOF) \|\| (a1->rn->type == ANYOFD));
3140			assert(a2->rn->type == EXACT);
3141
3142	6	100	if (a1->rn->flags & ANYOF_MATCHES_ALL_ABOVE_BITMAP)
3143			{
3144	1		return compare_mismatch(anchored, a1, a2);
3145			}
3146
3147	5		seq = GET_LITERAL(a2);
3148	5		init_bit_flag(&bf, ((unsigned char )seq));
3149
3150	41	50	for (i = 0; i < ANYOF_BITMAP_SIZE; ++i)
3151			{
3152	41	100	req = (i != bf.offs) ? 0 : bf.mask;
3153	41	100	if (get_bitmap_byte(a1->rn, i) != req)
3154			{
3155	5		return compare_mismatch(anchored, a1, a2);
3156			}
3157			}
3158
3159	6		return compare_tails(anchored, a1, a2);
3160			}
3161
3162			#ifdef RC_ANYOFM
3163			static int compare_anyofm_exact(int anchored, Arrow a1, Arrow a2)
3164			{
3165			unsigned char left[ANYOF_BITMAP_SIZE];
3166			BitFlag bf;
3167			char *seq;
3168			int i;
3169			unsigned char req;
3170
3171			assert(a1->rn->type == ANYOFM);
3172			assert(a2->rn->type == EXACT);
3173
3174			if (!convert_anyofm_to_bitmap(a1, left))
3175			{
3176			return compare_mismatch(anchored, a1, a2);
3177			}
3178
3179			seq = GET_LITERAL(a2);
3180			init_bit_flag(&bf, ((unsigned char )seq));
3181
3182			for (i = 0; i < ANYOF_BITMAP_SIZE; ++i)
3183			{
3184			req = (i != bf.offs) ? 0 : bf.mask;
3185			if (left[i] != req)
3186			{
3187			return compare_mismatch(anchored, a1, a2);
3188			}
3189			}
3190
3191			return compare_tails(anchored, a1, a2);
3192			}
3193			#endif
3194
3195	21		static int compare_anyof_exactf(int anchored, Arrow a1, Arrow a2)
3196			{
3197			char *seq;
3198			char unf[2];
3199			BitFlag bf[2];
3200			unsigned char right[ANYOF_BITMAP_SIZE];
3201			int i;
3202
3203			assert((a1->rn->type == ANYOF) \|\| (a1->rn->type == ANYOFD));
3204			assert((a2->rn->type == EXACTF) \|\| (a2->rn->type == EXACTFU));
3205
3206	21	100	if (a1->rn->flags & ANYOF_MATCHES_ALL_ABOVE_BITMAP)
3207			{
3208	3		return compare_mismatch(anchored, a1, a2);
3209			}
3210
3211	18		seq = GET_LITERAL(a2);
3212	18		init_unfolded(unf, *seq);
3213
3214	54	100	for (i = 0; i < 2; ++i)
3215			{
3216	36		init_bit_flag(bf + i, (unsigned char)(unf[i]));
3217			}
3218
3219	18	50	if (bf[0].offs == bf[1].offs)
3220			{
3221	0		bf[0].mask = bf[1].mask = bf[0].mask \| bf[1].mask;
3222			}
3223
3224	18		memset(right, 0, ANYOF_BITMAP_SIZE);
3225	54	100	for (i = 0; i < 2; ++i)
3226			{
3227	36		right[bf[i].offs] = bf[i].mask;
3228			}
3229
3230	21		return compare_bitmaps(anchored, a1, a2, 0, right);
3231			}
3232
3233			#ifdef RC_ANYOFM
3234			static int compare_anyofm_exactf(int anchored, Arrow a1, Arrow a2)
3235			{
3236			char *seq;
3237			int i;
3238			BitFlag bf;
3239			unsigned char left[ANYOF_BITMAP_SIZE];
3240			unsigned char right[ANYOF_BITMAP_SIZE];
3241			char unf[2];
3242
3243			/* fprintf(stderr, "enter compare_anyofm_exactf(%d, \n", anchored); */
3244
3245			assert(a1->rn->type == ANYOFM);
3246			assert((a2->rn->type == EXACTF) \|\| (a2->rn->type == EXACTFU));
3247
3248			if (!convert_anyofm_to_bitmap(a1, left))
3249			{
3250			return compare_mismatch(anchored, a1, a2);
3251			}
3252
3253			seq = GET_LITERAL(a2);
3254			init_unfolded(unf, *seq);
3255
3256			memset(right, 0, ANYOF_BITMAP_SIZE);
3257			for (i = 0; i < 2; ++i)
3258			{
3259			init_bit_flag(&bf, unf[i]);
3260			right[bf.offs] = bf.mask;
3261			}
3262
3263			return compare_bitmaps(anchored, a1, a2, left, right);
3264			}
3265			#endif
3266
3267	6779		static int compare_exact_exact(int anchored, Arrow a1, Arrow a2)
3268			{
3269			char q1, q2;
3270
3271			#ifndef RC_EXACT_ONLY8
3272			assert(a1->rn->type == EXACT);
3273			assert(a2->rn->type == EXACT);
3274			#endif
3275
3276	6779		q1 = GET_LITERAL(a1);
3277	6779		q2 = GET_LITERAL(a2);
3278
3279			/* fprintf(stderr, "enter compare_exact_exact(%d, '%c', '%c')\n", anchored,
3280			q1, q2); */
3281
3282	6779	100	if (q1 != q2)
3283			{
3284	2546		return compare_mismatch(anchored, a1, a2);
3285			}
3286
3287	4233		return compare_tails(anchored, a1, a2);
3288			}
3289
3290	88		static int compare_exact_exactf(int anchored, Arrow a1, Arrow a2)
3291			{
3292			char q1, q2;
3293			char unf[2];
3294
3295			assert(a1->rn->type == EXACT);
3296			assert((a2->rn->type == EXACTF) \|\| (a2->rn->type == EXACTFU));
3297
3298	88		q1 = GET_LITERAL(a1);
3299	88		q2 = GET_LITERAL(a2);
3300	88		init_unfolded(unf, *q2);
3301
3302	88	100	if ((q1 != unf[0]) && (q1 != unf[1]))
		100
3303			{
3304	6		return compare_mismatch(anchored, a1, a2);
3305			}
3306
3307	88		return compare_tails(anchored, a1, a2);
3308			}
3309
3310	28		static int compare_exactf_exact(int anchored, Arrow a1, Arrow a2)
3311			{
3312			char q1, q2;
3313			char unf[2];
3314
3315			assert((a1->rn->type == EXACTF) \|\| (a1->rn->type == EXACTFU));
3316			assert(a2->rn->type == EXACT);
3317
3318	28		q1 = GET_LITERAL(a1);
3319	28		init_unfolded(unf, *q1);
3320	28		q2 = GET_LITERAL(a2);
3321
3322	28	100	if ((unf[0] != q2) \|\| (unf[1] != q2))
		100
3323			{
3324	27		return compare_mismatch(anchored, a1, a2);
3325			}
3326
3327	28		return compare_tails(anchored, a1, a2);
3328			}
3329
3330	517		static int compare_exactf_exactf(int anchored, Arrow a1, Arrow a2)
3331			{
3332			char q1, q2;
3333			char l1, l2;
3334
3335			assert((a1->rn->type == EXACTF) \|\| (a1->rn->type == EXACTFU));
3336			assert((a2->rn->type == EXACTF) \|\| (a2->rn->type == EXACTFU));
3337
3338	517		q1 = GET_LITERAL(a1);
3339	517		q2 = GET_LITERAL(a2);
3340
3341	517	100	l1 = TOLOWER(*q1);
		100
3342	517	100	l2 = TOLOWER(*q2);
		100
3343
3344	517	100	if (l1 != l2)
3345			{
3346	58		return compare_mismatch(anchored, a1, a2);
3347			}
3348
3349	459		return compare_tails(anchored, a1, a2);
3350			}
3351
3352	617		static int compare_left_branch(int anchored, Arrow a1, Arrow a2)
3353			{
3354			int rv, tsz;
3355			regnode *p1;
3356			Arrow left, right;
3357
3358			/* fprintf(stderr, "enter compare_left_branch\n"); */
3359
3360			assert(a1->rn->type == BRANCH);
3361
3362			/* origins stay the same throughout the cycle */
3363	617		left.origin = a1->origin;
3364	617		right.origin = a2->origin;
3365	617		p1 = a1->rn;
3366	1837	100	while (p1->type == BRANCH)
3367			{
3368	1257	50	if (p1->next_off == 0)
3369			{
3370	0		rc_error = "Branch with zero offset";
3371	0		return -1;
3372			}
3373
3374	1257		left.rn = p1 + 1;
3375	1257		left.spent = 0;
3376
3377	1257		right.rn = a2->rn;
3378	1257		right.spent = a2->spent;
3379
3380	1257		rv = compare(anchored, &left, &right);
3381			/* fprintf(stderr, "rv = %d\n", rv); */
3382
3383	1257	50	if (rv < 0)
3384			{
3385	0		return rv;
3386			}
3387
3388	1257	100	if (!rv)
3389			{
3390			/* fprintf(stderr, "compare_left_branch doesn't match\n"); */
3391	37		return compare_mismatch(anchored, a1, a2);
3392			}
3393
3394	1220		p1 += p1->next_off;
3395			}
3396
3397	580		a1->rn = p1;
3398	580		a1->spent = 0;
3399
3400	580		tsz = get_size(a2->rn);
3401	580	50	if (tsz <= 0)
3402			{
3403	0		return -1;
3404			}
3405
3406	580		a2->rn += tsz - 1;
3407	580		a2->spent = 0;
3408
3409	617		return 1;
3410			}
3411
3412	19		static int compare_set(int anchored, Arrow a1, Arrow a2, unsigned char *b1)
3413			{
3414			regnode alt, t1;
3415			Arrow left, right;
3416			int i, j, power, rv, sz, offs;
3417			unsigned char loc;
3418
3419	19	50	offs = GET_OFFSET(a1->rn);
3420	19	50	if (offs <= 0)
3421			{
3422	0		return -1;
3423			}
3424
3425	19		t1 = a1->rn + offs;
3426	19		sz = get_size(t1);
3427	19	50	if (sz < 0)
3428			{
3429	0		return sz;
3430			}
3431
3432	19		alt = (regnode )malloc(sizeof(regnode) (2 + sz));
3433	19	50	if (!alt)
3434			{
3435	0		rc_error = "Couldn't allocate memory for alternative copy";
3436	0		return -1;
3437			}
3438
3439	19		alt[0].flags = 1;
3440	19		alt[0].type = EXACT;
3441	19		alt[0].next_off = 2;
3442	19		memcpy(alt + 2, t1, sizeof(regnode) * sz);
3443
3444	19		left.origin = a1->origin;
3445	19		right.origin = a2->origin;
3446	19		right.rn = 0;
3447
3448	591	100	for (i = 0; i < ANYOF_BITMAP_SIZE; ++i)
3449			{
3450	574	50	loc = b1 ? b1[i] : get_bitmap_byte(a1->rn, i);
3451	574	100	if ((i >= 16) && loc)
		100
3452			{
3453	1		free(alt);
3454	1		return compare_mismatch(anchored, a1, a2);
3455			}
3456
3457	573		power = 1;
3458	5152	100	for (j = 0; j < 8; ++j)
3459			{
3460	4580	100	if (loc & power)
3461			{
3462	339		alt[1].flags = 8 * i + j;
3463	339		left.rn = alt;
3464	339		left.spent = 0;
3465
3466	339		right.rn = a2->rn;
3467	339		right.spent = a2->spent;
3468
3469	339		rv = compare_right_branch(anchored, &left, &right);
3470	339	50	if (rv < 0)
3471			{
3472	0		free(alt);
3473	0		return rv;
3474			}
3475
3476	339	100	if (!rv)
3477			{
3478	1		free(alt);
3479	1		return compare_mismatch(anchored, a1, a2);
3480			}
3481			}
3482
3483	4579		power *= 2;
3484			}
3485			}
3486
3487	17		free(alt);
3488
3489	17	50	if (!right.rn)
3490			{
3491	0		rc_error = "Empty mask not supported";
3492	0		return -1;
3493			}
3494
3495	17		a1->rn = t1 + sz - 1;
3496			assert(a1->rn->type == END);
3497	17		a1->spent = 0;
3498
3499	17		a2->rn = right.rn;
3500	17		a2->spent = right.spent;
3501
3502	19		return 1;
3503			}
3504
3505	19		static int compare_anyof_branch(int anchored, Arrow a1, Arrow a2)
3506			{
3507			assert((a1->rn->type == ANYOF) \|\| (a1->rn->type == ANYOFD));
3508			assert(a2->rn->type == BRANCH);
3509
3510	19		return compare_set(anchored, a1, a2, 0);
3511			}
3512
3513			#ifdef RC_ANYOFM
3514			static int compare_anyofm_branch(int anchored, Arrow a1, Arrow a2)
3515			{
3516			unsigned char left[ANYOF_BITMAP_SIZE];
3517
3518			assert(a1->rn->type == ANYOFM);
3519			assert(a2->rn->type == BRANCH);
3520
3521			if (!convert_anyofm_to_bitmap(a1, left))
3522			{
3523			return compare_mismatch(anchored, a1, a2);
3524			}
3525
3526			return compare_set(anchored, a1, a2, left);
3527			}
3528			#endif
3529
3530	1565		static int compare_right_branch(int anchored, Arrow a1, Arrow a2)
3531			{
3532			int rv;
3533			regnode *p2;
3534			Arrow left, right;
3535
3536			/* fprintf(stderr, "enter compare_right_branch\n"); */
3537
3538			assert(a2->rn->type == BRANCH);
3539
3540			/* origins stay the same throughout the cycle */
3541	1565		left.origin = a1->origin;
3542	1565		right.origin = a2->origin;
3543	1565		p2 = a2->rn;
3544	1565		rv = 0;
3545	4012	100	while ((p2->type == BRANCH) && !rv)
		100
3546			{
3547			/* fprintf(stderr, "p2->type = %d\n", p2->type); */
3548
3549	2447		left.rn = a1->rn;
3550	2447		left.spent = a1->spent;
3551
3552	2447	50	if (p2->next_off == 0)
3553			{
3554	0		rc_error = "Branch with offset zero";
3555	0		return -1;
3556			}
3557
3558	2447		right.rn = p2 + 1;
3559	2447		right.spent = 0;
3560
3561	2447		rv = compare(anchored, &left, &right);
3562			/* fprintf(stderr, "got %d\n", rv); */
3563
3564	2447		p2 += p2->next_off;
3565			}
3566
3567	1565	50	if (rv < 0)
3568			{
3569	0		return rv;
3570			}
3571
3572	1565	100	if (!rv)
3573			{
3574	132		return compare_mismatch(anchored, a1, a2);
3575			}
3576
3577	1433		a1->rn = left.rn;
3578	1433		a1->spent = left.spent;
3579
3580	1433		a2->rn = right.rn;
3581	1433		a2->spent = right.spent;
3582
3583	1565		return 1;
3584			}
3585
3586	413		static int compare_right_star(int anchored, Arrow a1, Arrow a2)
3587			{
3588			regnode *p2;
3589			Arrow left, right;
3590			int sz, rv, offs;
3591
3592			/* fprintf(stderr, "enter compare_right_star\n"); */
3593
3594	413		p2 = a2->rn;
3595			assert(p2->type == STAR);
3596
3597	413		sz = get_size(p2);
3598	413	50	if (sz < 0)
3599			{
3600	0		return sz;
3601			}
3602
3603	413		left.origin = a1->origin;
3604	413		left.rn = a1->rn;
3605	413		left.spent = a1->spent;
3606
3607	413	50	offs = GET_OFFSET(p2);
3608	413	50	if (offs <= 0)
3609			{
3610	0		return -1;
3611			}
3612
3613	413		right.origin = a2->origin;
3614	413		right.rn = p2 + offs;
3615	413		right.spent = 0;
3616
3617	413		rv = compare(anchored, &left, &right);
3618	413	50	if (rv < 0)
3619			{
3620	0		return rv;
3621			}
3622
3623	413	100	if (rv == 0)
3624			{
3625	9		right.rn = p2 + 1;
3626	9		right.spent = 0;
3627
3628	9		rv = compare(anchored, a1, &right);
3629	9	50	if (rv < 0)
3630			{
3631	0		return rv;
3632			}
3633
3634	9	100	if (!rv)
3635			{
3636	4		return compare_mismatch(anchored, a1, a2);
3637			}
3638
3639	5		right.rn = p2;
3640	5		right.spent = 0;
3641
3642	5	50	if (!anchored)
3643			{
3644	0		rv = compare_right_star(1, a1, &right);
3645			}
3646			}
3647
3648	409	50	if (rv <= 0)
3649			{
3650	0		return rv;
3651			}
3652
3653	409		a2->rn += sz - 1;
3654			assert(a2->rn->type == END);
3655	409		a2->spent = 0;
3656
3657	413		return rv;
3658			}
3659
3660	136		static int compare_plus_plus(int anchored, Arrow a1, Arrow a2)
3661			{
3662			regnode p1, p2;
3663			Arrow left, right;
3664			int rv, offs;
3665
3666	136		p1 = a1->rn;
3667			assert(p1->type == PLUS);
3668	136		p2 = a2->rn;
3669			assert(p2->type == PLUS);
3670
3671	136		left.origin = a1->origin;
3672	136		left.rn = p1 + 1;
3673	136		left.spent = 0;
3674
3675	136		right.origin = a2->origin;
3676	136		right.rn = p2 + 1;
3677	136		right.spent = 0;
3678
3679	136		rv = compare(1, &left, &right);
3680	136	100	if (rv)
3681			{
3682	123		return rv;
3683			}
3684
3685	13	50	offs = GET_OFFSET(p1);
3686			/* fprintf(stderr, "offs = %d\n", offs); */
3687	13	50	if (offs <= 0)
3688			{
3689	0		return -1;
3690			}
3691
3692	13		left.origin = a1->origin;
3693	13		left.rn = p1 + offs;
3694	13		left.spent = 0;
3695	136		return compare(1, &left, a2);
3696			}
3697
3698	156		static int compare_repeat_star(int anchored, Arrow a1, Arrow a2)
3699			{
3700			regnode p1, p2;
3701			Arrow left, right;
3702			int rv, offs;
3703
3704	156		p1 = a1->rn;
3705			assert((p1->type == PLUS) \|\| (p1->type == STAR));
3706	156		p2 = a2->rn;
3707			assert(p2->type == STAR);
3708			/* fprintf(stderr, "enter compare_repeat_star(%d, %d, %d)\n",
3709			anchored, p1->type, p2->type); */
3710
3711	156		left.origin = a1->origin;
3712	156		left.rn = p1 + 1;
3713	156		left.spent = 0;
3714
3715	156		right.origin = a2->origin;
3716	156		right.rn = p2 + 1;
3717	156		right.spent = 0;
3718
3719	156		rv = compare(1, &left, &right);
3720			/* fprintf(stderr, "inclusive compare returned %d\n", rv); */
3721	156	100	if (rv)
3722			{
3723	140		return rv;
3724			}
3725
3726	16	50	offs = GET_OFFSET(p2);
3727			/* fprintf(stderr, "offs = %d\n", offs); */
3728	16	50	if (offs <= 0)
3729			{
3730	0		return -1;
3731			}
3732
3733	16		right.origin = a2->origin;
3734	16		right.rn = p2 + offs;
3735	16		right.spent = 0;
3736	156		return compare(1, &left, &right);
3737			}
3738
3739	310		static int compare_right_curly_from_zero(int anchored, Arrow a1, Arrow a2)
3740			{
3741			regnode p2, alt;
3742			CurlyCount *cnt;
3743			#ifndef RC_UNSIGNED_COUNT
3744			CurlyCount n;
3745			#endif
3746			Arrow left, right;
3747			int sz, rv, offs;
3748
3749	310		p2 = a2->rn;
3750
3751			#ifndef RC_UNSIGNED_COUNT
3752	310		n = ((CurlyCount *)(p2 + 1))[1];
3753	310	50	if (n <= 0)
3754			{
3755	0		rc_error = "Curly must have positive maximum";
3756	0		return -1;
3757			}
3758			#endif
3759
3760	310		sz = get_size(p2);
3761	310	50	if (sz < 0)
3762			{
3763	0		return sz;
3764			}
3765
3766	310		left.origin = a1->origin;
3767	310		left.rn = a1->rn;
3768	310		left.spent = a1->spent;
3769
3770	310	50	offs = GET_OFFSET(p2);
3771	310	50	if (offs <= 0)
3772			{
3773	0		return -1;
3774			}
3775
3776	310		right.origin = a2->origin;
3777	310		right.rn = p2 + offs;
3778	310		right.spent = 0;
3779
3780	310		rv = compare(anchored, &left, &right);
3781	310	50	if (rv < 0)
3782			{
3783	0		return rv;
3784			}
3785
3786	310	100	if (rv == 0)
3787			{
3788	4		alt = alloc_alt(p2, sz);
3789	4	50	if (!alt)
3790			{
3791	0		return -1;
3792			}
3793
3794	4		right.rn = alt + 2;
3795	4		right.spent = 0;
3796
3797	4		rv = compare(anchored, a1, &right);
3798	4	50	if (rv < 0)
3799			{
3800	0		free(alt);
3801	0		return rv;
3802			}
3803
3804	4	100	if (!rv)
3805			{
3806	2		free(alt);
3807	2		return compare_mismatch(anchored, a1, a2);
3808			}
3809
3810	2		cnt = (CurlyCount *)(alt + 1);
3811	2	50	if (cnt[1] < INFINITE_COUNT)
3812			{
3813	2		--cnt[1];
3814			}
3815
3816	2	100	if ((cnt[1] > 0) && !anchored)
		50
3817			{
3818	0		right.rn = alt;
3819	0		right.spent = 0;
3820
3821	0		rv = compare_right_curly_from_zero(1, a1, &right);
3822			}
3823			else
3824			{
3825	2		rv = 1;
3826			}
3827
3828	2		free(alt);
3829			}
3830
3831	308	50	if (rv <= 0)
3832			{
3833	0		return rv;
3834			}
3835
3836	308		a2->rn += sz - 1;
3837			assert(a2->rn->type == END);
3838	308		a2->spent = 0;
3839
3840	310		return rv;
3841			}
3842
3843	505		static int compare_left_plus(int anchored, Arrow a1, Arrow a2)
3844			{
3845			regnode p1, alt, *q;
3846			Arrow left, right;
3847			int sz, rv, offs, end_offs;
3848			unsigned char orig_type;
3849
3850	505		p1 = a1->rn;
3851			assert(p1->type == PLUS);
3852
3853	505		sz = get_size(p1);
3854	505	50	if (sz < 0)
3855			{
3856	0		return -1;
3857			}
3858
3859	505	50	if (sz < 2)
3860			{
3861	0		rc_error = "Left plus offset too small";
3862	0		return -1;
3863			}
3864
3865	505		alt = alloc_alt(p1 + 1, sz - 1);
3866	505	50	if (!alt)
3867			{
3868	0		return -1;
3869			}
3870
3871	505	100	if (anchored)
3872			{
3873	14		offs = get_jump_offset(p1);
3874	14	50	if (offs <= 0)
3875			{
3876	0		return -1;
3877			}
3878
3879	14		q = p1 + offs;
3880	14	100	if (q->type != END)
3881			{
3882			/* repeat with a tail after it can be more strict than a
3883			fixed-length match only if the tail is at least as
3884			strict as the repeated regexp */
3885	6		left.origin = a1->origin;
3886	6		left.rn = q;
3887	6		left.spent = 0;
3888
3889	6		end_offs = offs - 1;
3890	6		orig_type = alt[end_offs].type;
3891	6		alt[end_offs].type = END;
3892
3893	6		right.origin = a2->origin;
3894	6		right.rn = alt;
3895	6		right.spent = 0;
3896
3897			/* fprintf(stderr, "comparing %d to %d\n", left.rn->type,
3898			right.rn->type); */
3899	6		rv = compare(1, &left, &right);
3900			/* fprintf(stderr, "compare returned %d\n", rv); */
3901	6	100	if (rv <= 0)
3902			{
3903	4		free(alt);
3904	4		return rv;
3905			}
3906
3907	2		alt[end_offs].type = orig_type;
3908			}
3909			}
3910
3911	501		left.origin = a1->origin;
3912	501		left.rn = alt;
3913	501		left.spent = 0;
3914	501		rv = compare(anchored, &left, a2);
3915	501		free(alt);
3916	505		return rv;
3917			}
3918
3919	275		static int compare_right_plus(int anchored, Arrow a1, Arrow a2)
3920			{
3921			regnode *p2;
3922			Arrow right;
3923			int sz, rv;
3924
3925	275		p2 = a2->rn;
3926			assert(p2->type == PLUS);
3927
3928			/* fprintf(stderr, "enter compare_right_plus\n"); */
3929
3930	275		sz = get_size(p2);
3931	275	50	if (sz < 0)
3932			{
3933	0		return -1;
3934			}
3935
3936	275	50	if (sz < 2)
3937			{
3938	0		rc_error = "Plus offset too small";
3939	0		return -1;
3940			}
3941
3942			/* fprintf(stderr, "sz = %d\n", sz); */
3943
3944	275		right.origin = a2->origin;
3945	275		right.rn = p2 + 1;
3946	275		right.spent = 0;
3947
3948	275		rv = compare(anchored, a1, &right);
3949
3950	275	50	if (rv < 0)
3951			{
3952	0		return rv;
3953			}
3954
3955	275	100	if (!rv)
3956			{
3957	24		return compare_mismatch(anchored, a1, a2);
3958			}
3959
3960	251		a2->rn += sz - 1;
3961			assert(a2->rn->type == END);
3962	251		a2->spent = 0;
3963
3964	275		return rv;
3965			}
3966
3967	1257		static int compare_next(int anchored, Arrow a1, Arrow a2)
3968			{
3969	1257	50	if (bump_regular(a2) <= 0)
3970			{
3971	0		return -1;
3972			}
3973
3974	1257		return compare(anchored, a1, a2);
3975			}
3976
3977	21		static int compare_curly_plus(int anchored, Arrow a1, Arrow a2)
3978			{
3979			regnode p1, p2;
3980			Arrow left, right;
3981			CurlyCount *cnt;
3982
3983	21		p1 = a1->rn;
3984			assert((p1->type == CURLY) \|\| (p1->type == CURLYM) \|\|
3985			(p1->type == CURLYX));
3986	21		p2 = a2->rn;
3987			assert(p2->type == PLUS);
3988
3989	21		cnt = (CurlyCount *)(p1 + 1);
3990			#ifndef RC_UNSIGNED_COUNT
3991	21	50	if (cnt[0] < 0)
3992			{
3993	0		rc_error = "Left curly has negative minimum";
3994	0		return -1;
3995			}
3996			#endif
3997
3998	21	50	if (!cnt[0])
3999			{
4000	0		return compare_mismatch(anchored, a1, a2);
4001			}
4002
4003	21		left.origin = a1->origin;
4004	21		left.rn = p1 + 2;
4005	21		left.spent = 0;
4006
4007	21		right.origin = a2->origin;
4008	21		right.rn = p2 + 1;
4009	21		right.spent = 0;
4010
4011	21	100	if (cnt[0] > 1)
4012			{
4013	9		anchored = 1;
4014			}
4015
4016	21		return compare(anchored, &left, &right);
4017			}
4018
4019	30		static int compare_curly_star(int anchored, Arrow a1, Arrow a2)
4020			{
4021			regnode p1, p2;
4022			Arrow left, right;
4023			int rv;
4024
4025	30		p1 = a1->rn;
4026			assert((p1->type == CURLY) \|\| (p1->type == CURLYM) \|\|
4027			(p1->type == CURLYX));
4028	30		p2 = a2->rn;
4029			assert(p2->type == STAR);
4030
4031	30		left.origin = a1->origin;
4032	30		left.rn = p1 + 2;
4033	30		left.spent = 0;
4034
4035	30		right.origin = a2->origin;
4036	30		right.rn = p2 + 1;
4037	30		right.spent = 0;
4038
4039	30		rv = compare(1, &left, &right);
4040	30	100	if (!rv)
4041			{
4042	11		rv = compare_next(anchored, a1, a2);
4043			}
4044
4045	30		return rv;
4046			}
4047
4048	41		static int compare_plus_curly(int anchored, Arrow a1, Arrow a2)
4049			{
4050			regnode p1, p2, *e2;
4051			Arrow left, right;
4052			CurlyCount *cnt;
4053			int rv, offs;
4054
4055	41		p1 = a1->rn;
4056			assert(p1->type == PLUS);
4057	41		p2 = a2->rn;
4058			assert((p2->type == CURLY) \|\| (p2->type == CURLYM) \|\|
4059			(p2->type == CURLYX));
4060
4061	41		cnt = (CurlyCount *)(p2 + 1);
4062			#ifndef RC_UNSIGNED_COUNT
4063	41	50	if (cnt[0] < 0)
4064			{
4065	0		rc_error = "Negative minimum for curly";
4066	0		return -1;
4067			}
4068			#endif
4069
4070	41	100	if (cnt[0] > 1) /* FIXME: fails '(?:aa)+' => 'a{2,}' */
4071			{
4072	2		return compare_mismatch(anchored, a1, a2);
4073			}
4074
4075	39		left.origin = a1->origin;
4076	39		left.rn = p1 + 1;
4077	39		left.spent = 0;
4078
4079	39	100	if (cnt[1] != INFINITE_COUNT)
4080			{
4081	35		offs = get_jump_offset(p2);
4082	35	50	if (offs <= 0)
4083			{
4084	0		return -1;
4085			}
4086
4087	35		e2 = p2 + offs;
4088	35	50	if (e2->type != END)
4089			{
4090	0		return compare_mismatch(anchored, a1, a2);
4091			}
4092			}
4093
4094	39		right.origin = a2->origin;
4095	39		right.rn = p2 + 2;
4096	39		right.spent = 0;
4097
4098	39		rv = compare(anchored, &left, &right);
4099	41	50	return (!rv && !cnt[0]) ? compare_next(anchored, a1, a2) : rv;
		0
4100			}
4101
4102	11		static int compare_suspend_curly(int anchored, Arrow a1, Arrow a2)
4103			{
4104			assert(a1->rn->type == SUSPEND);
4105			assert(!a1->spent);
4106
4107	11		a1->rn += 2;
4108
4109	11		return compare(1, a1, a2);
4110			}
4111
4112	375		static void dec_curly_counts(CurlyCount *altcnt)
4113			{
4114	375		--altcnt[0];
4115	375	100	if (altcnt[1] < INFINITE_COUNT)
4116			{
4117	155		--altcnt[1];
4118			}
4119	375		}
4120
4121	634		static int compare_left_curly(int anchored, Arrow a1, Arrow a2)
4122			{
4123			regnode p1, alt, *q;
4124			Arrow left, right;
4125			int sz, rv, offs, end_offs;
4126			CurlyCount *cnt;
4127
4128			/* fprintf(stderr, "enter compare_left_curly(%d, %d, %d)\n", anchored,
4129			a1->rn->type, a2->rn->type); */
4130
4131	634		p1 = a1->rn;
4132			assert((p1->type == CURLY) \|\| (p1->type == CURLYM) \|\|
4133			(p1->type == CURLYX));
4134
4135	634		cnt = (CurlyCount *)(p1 + 1);
4136	634	100	if (!cnt[0])
4137			{
4138			/* fprintf(stderr, "curly from 0\n"); */
4139	8		return compare_mismatch(anchored, a1, a2);
4140			}
4141
4142	626		sz = get_size(p1);
4143	626	50	if (sz < 0)
4144			{
4145	0		return -1;
4146			}
4147
4148	626	50	if (sz < 3)
4149			{
4150	0		rc_error = "Left curly offset too small";
4151	0		return -1;
4152			}
4153
4154	626	100	if (cnt[0] > 1)
4155			{
4156			/* fprintf(stderr, "curly with non-trivial repeat count\n"); */
4157
4158	339	50	offs = GET_OFFSET(p1);
4159	339	50	if (offs < 0)
4160			{
4161	0		return -1;
4162			}
4163
4164	339	50	if (offs < 3)
4165			{
4166	0		rc_error = "Left curly offset is too small";
4167	0		return -1;
4168			}
4169
4170	339		alt = (regnode )malloc(sizeof(regnode) (offs - 2 + sz));
4171	339	50	if (!alt)
4172			{
4173	0		rc_error = "Could not allocate memory for unrolled curly";
4174	0		return -1;
4175			}
4176
4177	339		memcpy(alt, p1 + 2, (offs - 2) * sizeof(regnode));
4178	339		memcpy(alt + offs - 2, p1, sz * sizeof(regnode));
4179
4180	339		dec_curly_counts((CurlyCount *)(alt + offs - 1));
4181
4182	339		left.origin = a1->origin;
4183	339		left.rn = alt;
4184	339		left.spent = 0;
4185	339		rv = compare(1, &left, a2);
4186	339		free(alt);
4187	339		return rv;
4188			}
4189
4190	287	100	if (anchored && !((cnt[0] == 1) && (cnt[1] == 1)))
		50
		100
4191			{
4192			/* fprintf(stderr, "anchored curly with variable length\n"); */
4193
4194	7		alt = alloc_alt(p1 + 2, sz - 2);
4195	7	50	if (!alt)
4196			{
4197	0		return -1;
4198			}
4199
4200	7		offs = get_jump_offset(p1);
4201	7	50	if (offs <= 0)
4202			{
4203	0		return -1;
4204			}
4205
4206	7		q = p1 + offs;
4207	7	50	if (q->type != END)
4208			{
4209			/* repeat with a tail after it can be more strict than a
4210			fixed-length match only if the tail is at least as
4211			strict as the repeated regexp */
4212	0		left.origin = a1->origin;
4213	0		left.rn = q;
4214	0		left.spent = 0;
4215
4216	0		end_offs = offs - 1;
4217	0		alt[end_offs].type = END;
4218
4219	0		right.origin = a2->origin;
4220	0		right.rn = alt;
4221	0		right.spent = 0;
4222
4223			/* fprintf(stderr, "comparing %d to %d\n", left.rn->type,
4224			right.rn->type); */
4225	0		rv = compare(1, &left, &right);
4226	0		free(alt);
4227			/* fprintf(stderr, "compare returned %d\n", rv); */
4228	0	0	if (rv <= 0)
4229			{
4230	0		return rv;
4231			}
4232			}
4233			}
4234
4235	287		left.origin = a1->origin;
4236	287		left.rn = p1 + 2;
4237	287		left.spent = 0;
4238	634		return compare(anchored, &left, a2);
4239			}
4240
4241	475		static int compare_right_curly(int anchored, Arrow a1, Arrow a2)
4242			{
4243			regnode p2, alt;
4244			Arrow right;
4245			CurlyCount cnt, altcnt;
4246			int sz, rv, offs, nanch;
4247
4248			/* fprintf(stderr, "enter compare_right_curly(%d...: a1->spent = %d, a2->spent = %d\n", anchored, a1->spent, a2->spent); */
4249
4250	475		p2 = a2->rn;
4251
4252	475		cnt = (CurlyCount *)(p2 + 1);
4253			#ifndef RC_UNSIGNED_COUNT
4254	475	50	if (cnt[0] < 0)
4255			{
4256	0		rc_error = "Curly has negative minimum";
4257	0		return -1;
4258			}
4259			#endif
4260
4261			/* fprintf(stderr, "compare_right_curly: minimal repeat count = %d\n", cnt[0]); */
4262
4263	475		nanch = anchored;
4264
4265	475	100	if (cnt[0] > 0)
4266			{
4267			/* the repeated expression is mandatory: */
4268	165		sz = get_size(p2);
4269	165	50	if (sz < 0)
4270			{
4271	0		return sz;
4272			}
4273
4274	165	50	if (sz < 3)
4275			{
4276	0		rc_error = "Right curly offset too small";
4277	0		return -1;
4278			}
4279
4280	165		right.origin = a2->origin;
4281	165		right.rn = p2 + 2;
4282	165		right.spent = 0;
4283
4284	165		rv = compare(anchored, a1, &right);
4285			/* fprintf(stderr, "compare_right_curly: compare returned %d\n", rv); */
4286	165	50	if (rv < 0)
4287			{
4288	0		return rv;
4289			}
4290
4291	165	100	if (!rv)
4292			{
4293			/* ...or (if we aren't anchored yet) just do the left tail... */
4294	23		rv = compare_mismatch(anchored, a1, a2);
4295	23	50	if (rv)
4296			{
4297	0		return rv;
4298			}
4299
4300			/* ...or (last try) unroll the repeat (works for e.g.
4301			'abbc' vs. 'ab{2}c' */
4302	23	100	if (cnt[0] > 1)
4303			{
4304	15	50	offs = GET_OFFSET(p2);
4305	15	50	if (offs < 0)
4306			{
4307	0		return -1;
4308			}
4309
4310	15	50	if (offs < 3)
4311			{
4312	0		rc_error = "Left curly offset is too small";
4313	0		return -1;
4314			}
4315
4316	15		alt = (regnode )malloc(sizeof(regnode) (offs - 2 + sz));
4317	15	50	if (!alt)
4318			{
4319	0		rc_error = "Couldn't allocate memory for unrolled curly";
4320	0		return -1;
4321			}
4322
4323	15		memcpy(alt, p2 + 2, (offs - 2) * sizeof(regnode));
4324	15		memcpy(alt + offs - 2, p2, sz * sizeof(regnode));
4325
4326	15		dec_curly_counts((CurlyCount *)(alt + offs - 1));
4327
4328	15		right.origin = a2->origin;
4329	15		right.rn = alt;
4330	15		right.spent = 0;
4331
4332	15		rv = compare(anchored, a1, &right);
4333	15		free(alt);
4334	15		return rv;
4335			}
4336
4337	8		return 0;
4338			}
4339
4340	142	100	if (cnt[0] == 1)
4341			{
4342	81		return 1;
4343			}
4344
4345	61	100	if (a1->rn->type == END)
4346			{
4347			/* we presume the repeated argument matches something, which
4348			isn't guaranteed, but it is conservative */
4349	40		return 0;
4350			}
4351
4352			/* strictly speaking, matching one repeat didn't necessarily
4353			anchor the match, but we'll ignore such cases as
4354			pathological */
4355	21		nanch = 1;
4356
4357	21		alt = alloc_alt(p2, sz);
4358	21	50	if (!alt)
4359			{
4360	0		return -1;
4361			}
4362
4363	21		altcnt = (CurlyCount *)(alt + 1);
4364	21		dec_curly_counts(altcnt);
4365	21	50	if (altcnt[1] > 0)
4366			{
4367	21		right.origin = a2->origin;
4368	21		right.rn = alt;
4369	21		right.spent = 0;
4370
4371	21		rv = compare_right_curly(nanch, a1, &right);
4372			}
4373			else
4374			{
4375	0		rv = 1;
4376			}
4377
4378	21		free(alt);
4379
4380	21	100	if (rv <= 0)
4381			{
4382	2		return rv;
4383			}
4384
4385	19		a2->rn += sz - 1;
4386			assert(a2->rn->type == END);
4387	19		a2->spent = 0;
4388	19		return rv;
4389			}
4390
4391	475		return compare_right_curly_from_zero(nanch, a1, a2);
4392			}
4393
4394	342		static int compare_curly_curly(int anchored, Arrow a1, Arrow a2)
4395			{
4396			regnode p1, p2, *e2;
4397			Arrow left, right;
4398			CurlyCount cnt1, cnt2;
4399			int rv, offs;
4400
4401			/* fprintf(stderr, "enter compare_curly_curly(%d...)\n", anchored); */
4402
4403	342		p1 = a1->rn;
4404			assert((p1->type == CURLY) \|\| (p1->type == CURLYM) \|\|
4405			(p1->type == CURLYX));
4406	342		p2 = a2->rn;
4407			assert((p2->type == CURLY) \|\| (p2->type == CURLYM) \|\|
4408			(p2->type == CURLYX));
4409
4410	342		cnt1 = (CurlyCount *)(p1 + 1);
4411			#ifndef RC_UNSIGNED_COUNT
4412			/* fprintf(stderr, "cnt1 = %d\n", cnt1[0]); /
4413	342	50	if (cnt1[0] < 0)
4414			{
4415	0		rc_error = "Negative minimum for left curly";
4416	0		return -1;
4417			}
4418			#endif
4419
4420	342		cnt2 = (CurlyCount *)(p2 + 1);
4421			#ifndef RC_UNSIGNED_COUNT
4422			/* fprintf(stderr, "cnt2 = %d\n", cnt2[0]); /
4423	342	50	if (cnt2[0] < 0)
4424			{
4425	0		rc_error = "Negative minimum for right curly";
4426	0		return -1;
4427			}
4428			#endif
4429
4430	342	100	if (cnt2[0] > cnt1[0]) /* FIXME: fails '(?:aa){1,}' => 'a{2,}' */
4431			{
4432			/* fprintf(stderr, "curly mismatch\n"); */
4433	5		return compare_mismatch(anchored, a1, a2);
4434			}
4435
4436	337		left.origin = a1->origin;
4437	337		left.rn = p1 + 2;
4438	337		left.spent = 0;
4439
4440	337	100	if (cnt1[1] > cnt2[1])
4441			{
4442	36		offs = get_jump_offset(p2);
4443			/* fprintf(stderr, "offs = %d\n", offs); */
4444	36	50	if (offs <= 0)
4445			{
4446	0		return -1;
4447			}
4448
4449	36		e2 = p2 + offs;
4450			/* fprintf(stderr, "e2->type = %d\n", e2->type); */
4451	36	100	if (e2->type != END)
4452			{
4453	3		return compare_mismatch(anchored, a1, a2);
4454			}
4455			}
4456
4457	334		right.origin = a2->origin;
4458	334		right.rn = p2 + 2;
4459	334		right.spent = 0;
4460
4461			/* fprintf(stderr, "comparing tails\n"); */
4462
4463	334		rv = compare(anchored, &left, &right);
4464			/* fprintf(stderr, "tail compare returned %d\n", rv); */
4465	342	100	return (!rv && !cnt2[0]) ? compare_next(anchored, a1, a2) : rv;
		100
4466			}
4467
4468	119		static int compare_bound(int anchored, Arrow a1, Arrow a2,
4469			int move_left, unsigned char bitmap, char lookup,
4470			unsigned char *oktypes,
4471			unsigned char *regclasses, U32 regclasses_size)
4472			{
4473			Arrow left, right;
4474			unsigned char t;
4475			int i;
4476			char *seq;
4477
4478			assert((a2->rn->type == BOUND) \|\| (a2->rn->type == NBOUND));
4479
4480	119		left = *a1;
4481
4482	119	50	if (bump_with_check(&left) <= 0)
4483			{
4484	0		return -1;
4485			}
4486
4487	119		t = left.rn->type;
4488	119	50	if (t >= REGNODE_MAX)
4489			{
4490	0		rc_error = "Invalid node type";
4491	0		return -1;
4492			}
4493	119	100	else if (t == ANYOF)
4494			{
4495			/* fprintf(stderr, "next is bitmap; flags = 0x%x\n", left.rn->flags); */
4496
4497	1	50	if (left.rn->flags & ANYOF_MATCHES_ALL_ABOVE_BITMAP)
4498			{
4499	0		return compare_mismatch(anchored, a1, a2);
4500			}
4501
4502	33	100	for (i = 0; i < ANYOF_BITMAP_SIZE; ++i)
4503			{
4504	32	50	if (get_bitmap_byte(left.rn, i) & ~bitmap[i])
4505			{
4506	0		return compare_mismatch(anchored, a1, a2);
4507			}
4508			}
4509			}
4510	118	100	else if ((t == EXACT) \|\| (t == EXACTF) \|\| (t == EXACTFU))
		50
		100
4511			{
4512	87		seq = GET_LITERAL(&left);
4513	87	100	if (!lookup[(unsigned char)(*seq)])
4514			{
4515	43		return compare_mismatch(anchored, a1, a2);
4516			}
4517			}
4518	31	100	else if ((t == POSIXD) \|\| (t == NPOSIXD) \|\| (t == POSIXU) \|\| (t == NPOSIXU))
		50
		100
		50
4519	8		{
4520	8		U8 flags = left.rn->flags;
4521	8	50	if ((flags >= regclasses_size) \|\| !regclasses[flags])
		50
4522			{
4523	0		return compare_mismatch(anchored, a1, a2);
4524			}
4525			}
4526	23	100	else if (!oktypes[t])
4527			{
4528	17		return compare_mismatch(anchored, a1, a2);
4529			}
4530
4531	59		right = *a2;
4532	59	50	if (bump_with_check(&right) <= 0)
4533			{
4534	0		return -1;
4535			}
4536
4537	119	100	return move_left ? compare(1, &left, &right) :
4538			compare(anchored, a1, &right);
4539			}
4540
4541	8		static int compare_bol_word(int anchored, Arrow a1, Arrow a2)
4542			{
4543	8		return compare_bound(anchored, a1, a2, 1, word_bc.bitmap,
4544			word_bc.lookup, alphanumeric_classes,
4545			word_posix_regclasses, SIZEOF_ARRAY(word_posix_regclasses));
4546			}
4547
4548	2		static int compare_bol_nword(int anchored, Arrow a1, Arrow a2)
4549			{
4550	2		return compare_bound(anchored, a1, a2, 1, word_bc.nbitmap,
4551			word_bc.nlookup, non_alphanumeric_classes,
4552			non_word_posix_regclasses, SIZEOF_ARRAY(non_word_posix_regclasses));
4553			}
4554
4555	31		static int compare_next_word(int anchored, Arrow a1, Arrow a2)
4556			{
4557	31		return compare_bound(anchored, a1, a2, 0, word_bc.bitmap,
4558			word_bc.lookup, alphanumeric_classes,
4559			word_posix_regclasses, SIZEOF_ARRAY(word_posix_regclasses));
4560			}
4561
4562	78		static int compare_next_nword(int anchored, Arrow a1, Arrow a2)
4563			{
4564	78		return compare_bound(anchored, a1, a2, 0, word_bc.nbitmap,
4565			word_bc.nlookup, non_alphanumeric_classes,
4566			non_word_posix_regclasses, SIZEOF_ARRAY(non_word_posix_regclasses));
4567			}
4568
4569	6		static int compare_anyof_bounds(int anchored, Arrow a1, Arrow a2,
4570			unsigned char bitmap1, unsigned char bitmap2)
4571			{
4572			unsigned char loc;
4573			FCompare cmp[2];
4574			int i;
4575
4576	6		cmp[0] = compare_next_word;
4577	6		cmp[1] = compare_next_nword;
4578	179	100	for (i = 0; (i < ANYOF_BITMAP_SIZE) && (cmp[0] \|\| cmp[1]); ++i)
		100
		100
4579			{
4580	173	50	loc = bitmap1 ? bitmap1[i] : get_bitmap_byte(a1->rn, i);
4581
4582	173	100	if (loc & ~bitmap2[i])
4583			{
4584	13		cmp[0] = 0;
4585			}
4586
4587	173	100	if (loc & bitmap2[i])
4588			{
4589	4		cmp[1] = 0;
4590			}
4591			}
4592
4593	6	100	if (cmp[0] && cmp[1])
		50
4594			{
4595	0		rc_error = "Zero bitmap";
4596	0		return -1;
4597			}
4598
4599	10	100	for (i = 0; i < SIZEOF_ARRAY(cmp); ++i)
4600			{
4601	9	100	if (cmp[i])
4602			{
4603	5		return (cmp[i])(anchored, a1, a2);
4604			}
4605			}
4606
4607			/* if would be more elegant to use compare_mismatch as a sentinel
4608			in cmp, but VC 2003 then warns that this function might be
4609			missing a return... */
4610	6		return compare_mismatch(anchored, a1, a2);
4611			}
4612
4613	5		static int compare_anyof_bound(int anchored, Arrow a1, Arrow a2)
4614			{
4615			assert((a1->rn->type == ANYOF) \|\| (a1->rn->type == ANYOFD));
4616			assert(a2->rn->type == BOUND);
4617
4618	5	100	if (a1->rn->flags & ANYOF_MATCHES_ALL_ABOVE_BITMAP)
4619			{
4620	1		return compare_mismatch(anchored, a1, a2);
4621			}
4622
4623	4		return compare_anyof_bounds(anchored, a1, a2, 0, word_bc.nbitmap);
4624			}
4625
4626	3		static int compare_anyof_nbound(int anchored, Arrow a1, Arrow a2)
4627			{
4628			assert((a1->rn->type == ANYOF) \|\| (a1->rn->type == ANYOFD));
4629			assert(a2->rn->type == NBOUND);
4630
4631	3	100	if (a1->rn->flags & ANYOF_MATCHES_ALL_ABOVE_BITMAP)
4632			{
4633	1		return compare_mismatch(anchored, a1, a2);
4634			}
4635
4636	2		return compare_anyof_bounds(anchored, a1, a2, 0, word_bc.bitmap);
4637			}
4638
4639			#ifdef RC_ANYOFM
4640			static int compare_anyofm_bound(int anchored, Arrow a1, Arrow a2)
4641			{
4642			unsigned char left[ANYOF_BITMAP_SIZE];
4643
4644			assert(a1->rn->type == ANYOFM);
4645			assert(a2->rn->type == BOUND);
4646
4647			if (!convert_anyofm_to_bitmap(a1, left))
4648			{
4649			return compare_mismatch(anchored, a1, a2);
4650			}
4651
4652			return compare_anyof_bounds(anchored, a1, a2, left, word_bc.nbitmap);
4653			}
4654
4655			static int compare_anyofm_nbound(int anchored, Arrow a1, Arrow a2)
4656			{
4657			unsigned char left[ANYOF_BITMAP_SIZE];
4658
4659			assert(a1->rn->type == ANYOFM);
4660			assert(a2->rn->type == NBOUND);
4661
4662			if (!convert_anyofm_to_bitmap(a1, left))
4663			{
4664			return compare_mismatch(anchored, a1, a2);
4665			}
4666
4667			return compare_anyof_bounds(anchored, a1, a2, left, word_bc.bitmap);
4668			}
4669			#endif
4670
4671	64		static int compare_exact_bound(int anchored, Arrow a1, Arrow a2)
4672			{
4673			char *seq;
4674			FCompare cmp;
4675
4676			assert((a1->rn->type == EXACT) \|\| (a1->rn->type == EXACTF) \|\|
4677			(a1->rn->type == EXACTFU));
4678			assert(a2->rn->type == BOUND);
4679
4680	64		seq = GET_LITERAL(a1);
4681
4682	128		cmp = word_bc.lookup[(unsigned char)(*seq)] ?
4683	64	100	compare_next_nword : compare_next_word;
4684	64		return cmp(anchored, a1, a2);
4685			}
4686
4687	17		static int compare_exact_nbound(int anchored, Arrow a1, Arrow a2)
4688			{
4689			char *seq;
4690			FCompare cmp;
4691
4692			assert((a1->rn->type == EXACT) \|\| (a1->rn->type == EXACTF) \|\|
4693			(a1->rn->type == EXACTFU));
4694			assert(a2->rn->type == NBOUND);
4695
4696	17		seq = GET_LITERAL(a1);
4697
4698	34		cmp = word_bc.lookup[(unsigned char)(*seq)] ?
4699	17	100	compare_next_word : compare_next_nword;
4700	17		return cmp(anchored, a1, a2);
4701			}
4702
4703	10		static int compare_posix_bound(int anchored, Arrow a1, Arrow a2)
4704			{
4705			assert((a1->rn->type == POSIXD) \|\| (a1->rn->type == POSIXU) \|\|
4706			(a1->rn->type == POSIXA));
4707			assert(a2->rn->type == BOUND);
4708
4709	10		U8 flags = a1->rn->flags;
4710	10	50	if ((flags >= SIZEOF_ARRAY(word_posix_regclasses)) \|\|
		50
4711	10	100	(flags >= SIZEOF_ARRAY(non_word_posix_regclasses)) \|\|
4712	5	50	(!word_posix_regclasses[flags] && !non_word_posix_regclasses[flags]))
4713			{
4714	0		return compare_mismatch(anchored, a1, a2);
4715			}
4716
4717			assert(!word_posix_regclasses[flags] \|\| !non_word_posix_regclasses[flags]);
4718
4719	20		FCompare cmp = word_posix_regclasses[flags] ?
4720	10	100	compare_next_nword : compare_next_word;
4721	10		return cmp(anchored, a1, a2);
4722			}
4723
4724	9		static int compare_posix_nbound(int anchored, Arrow a1, Arrow a2)
4725			{
4726			assert((a1->rn->type == POSIXD) \|\| (a1->rn->type == POSIXU) \|\|
4727			(a1->rn->type == POSIXA));
4728			assert(a2->rn->type == NBOUND);
4729
4730	9		U8 flags = a1->rn->flags;
4731	9	50	if ((flags >= SIZEOF_ARRAY(word_posix_regclasses)) \|\|
		50
4732	9	100	(flags >= SIZEOF_ARRAY(non_word_posix_regclasses)) \|\|
4733	4	50	(!word_posix_regclasses[flags] && !non_word_posix_regclasses[flags]))
4734			{
4735	0		return compare_mismatch(anchored, a1, a2);
4736			}
4737
4738			assert(!word_posix_regclasses[flags] \|\| !non_word_posix_regclasses[flags]);
4739
4740	18		FCompare cmp = word_posix_regclasses[flags] ?
4741	9	100	compare_next_word : compare_next_nword;
4742	9		return cmp(anchored, a1, a2);
4743			}
4744
4745	5		static int compare_negative_posix_word_bound(int anchored, Arrow a1, Arrow a2)
4746			{
4747			assert((a1->rn->type == NPOSIXD) \|\| (a1->rn->type == NPOSIXU) \|\|
4748			(a1->rn->type == NPOSIXA));
4749			assert(a2->rn->type == BOUND);
4750
4751			/* we could accept _CC_ALPHANUMERIC as well but let's postpone it
4752			until we see the need */
4753	5	100	if (a1->rn->flags != _CC_WORDCHAR)
4754			{
4755	3		return compare_mismatch(anchored, a1, a2);
4756			}
4757
4758	2		return compare_next_word(anchored, a1, a2);
4759			}
4760
4761	9		static int compare_negative_posix_word_nbound(int anchored, Arrow a1, Arrow a2)
4762			{
4763			assert((a1->rn->type == NPOSIXD) \|\| (a1->rn->type == NPOSIXU) \|\|
4764			(a1->rn->type == NPOSIXA));
4765			assert(a2->rn->type == NBOUND);
4766
4767			/* we could accept _CC_ALPHANUMERIC as well but let's postpone it
4768			until we see the need */
4769	9	100	if (a1->rn->flags != _CC_WORDCHAR)
4770			{
4771	7		return compare_mismatch(anchored, a1, a2);
4772			}
4773
4774	2		return compare_next_nword(anchored, a1, a2);
4775			}
4776
4777	50		static int compare_open_open(int anchored, Arrow a1, Arrow a2)
4778			{
4779	50		return compare_tails(anchored, a1, a2);
4780			}
4781
4782	220		static int compare_left_open(int anchored, Arrow a1, Arrow a2)
4783			{
4784	220		return compare_left_tail(anchored, a1, a2);
4785			}
4786
4787	209		static int compare_right_open(int anchored, Arrow a1, Arrow a2)
4788			{
4789	209		return compare_next(anchored, a1, a2);
4790			}
4791
4792	10033		static int success(int anchored, Arrow a1, Arrow a2)
4793			{
4794	10033		return 1;
4795			}
4796
4797			/* #define DEBUG_dump */
4798
4799	9063		int rc_compare(REGEXP pt1, REGEXP pt2)
4800			{
4801			Arrow a1, a2;
4802			regnode p1, p2;
4803			#ifdef DEBUG_dump
4804			unsigned char *p;
4805			int i;
4806			#endif
4807
4808	9063		a1.origin = SvANY(pt1);
4809	9063		a2.origin = SvANY(pt2);
4810
4811	9063	100	if ((get_forced_semantics(pt1) \| get_forced_semantics(pt2)) == FORCED_MISMATCH)
4812			{
4813	7		return 0;
4814			}
4815
4816	9056		p1 = find_internal(a1.origin);
4817	9056	50	if (!p1)
4818			{
4819	0		return -1;
4820			}
4821
4822	9056		p2 = find_internal(a2.origin);
4823	9056	50	if (!p2)
4824			{
4825	0		return -1;
4826			}
4827
4828			#ifdef DEBUG_dump
4829			p = (unsigned char *)p1;
4830			for (i = 1; i <= 64; ++i)
4831			{
4832			fprintf(stderr, " %02x", (int)p[i - 1]);
4833			if (!(i % 4))
4834			{
4835			fprintf(stderr, "\n");
4836			}
4837			}
4838
4839			fprintf(stderr, "\n\n");
4840
4841			p = (unsigned char *)p2;
4842			for (i = 1; i <= 64; ++i)
4843			{
4844			fprintf(stderr, " %02x", (int)p[i - 1]);
4845			if (!(i % 4))
4846			{
4847			fprintf(stderr, "\n");
4848			}
4849			}
4850
4851			fprintf(stderr, "\n\n");
4852			#endif
4853
4854	9056		a1.rn = p1;
4855	9056		a1.spent = 0;
4856	9056		a2.rn = p2;
4857	9056		a2.spent = 0;
4858
4859	9063		return compare(0, &a1, &a2);
4860			}
4861
4862	37867		static int compare(int anchored, Arrow a1, Arrow a2)
4863			{
4864			FCompare cmp;
4865
4866			/* fprintf(stderr, "enter compare(%d, %d, %d)\n", anchored,
4867			a1->rn->type, a2->rn->type); */
4868
4869	37867	50	if ((a1->rn->type >= REGNODE_MAX) \|\| (a2->rn->type >= REGNODE_MAX))
		50
4870			{
4871	0		rc_error = "Invalid regexp node type";
4872	0		return -1;
4873			}
4874
4875	37867		cmp = dispatch[a1->rn->type][a2->rn->type];
4876	37867	100	if (!cmp)
4877			{
4878			/* fprintf(stderr, "no comparator\n"); */
4879	933		return 0;
4880			}
4881
4882	36934		return cmp(anchored, a1, a2);
4883			}
4884
4885	1		void rc_init()
4886			{
4887			int i, wstart;
4888
4889			/* could have used compile-time assertion, but why bother
4890			making it compatible... */
4891			assert(ANYOF_BITMAP_SIZE == 32);
4892
4893	1		init_forced_byte();
4894
4895	1		init_byte_class(&whitespace, whitespace_expl,
4896			SIZEOF_ARRAY(whitespace_expl));
4897	1		init_byte_class(&horizontal_whitespace, horizontal_whitespace_expl,
4898			SIZEOF_ARRAY(horizontal_whitespace_expl));
4899	1		init_byte_class(&vertical_whitespace, vertical_whitespace_expl,
4900			SIZEOF_ARRAY(vertical_whitespace_expl));
4901
4902	11	100	for (i = 0; i < SIZEOF_ARRAY(digit_expl); ++i)
4903			{
4904	10		digit_expl[i] = '0' + i;
4905			}
4906
4907	1		init_byte_class(&digit, digit_expl, SIZEOF_ARRAY(digit_expl));
4908
4909	1		memcpy(xdigit_expl, digit_expl, 10 * sizeof(char));
4910
4911	1		wstart = 10;
4912	7	100	for (i = 0; i < 6; ++i)
4913			{
4914	6		xdigit_expl[wstart + i] = 'a' + i;
4915			}
4916
4917	1		wstart += 6;
4918	7	100	for (i = 0; i < 6; ++i)
4919			{
4920	6		xdigit_expl[wstart + i] = 'A' + i;
4921			}
4922
4923	1		init_byte_class(&xdigit, xdigit_expl, SIZEOF_ARRAY(xdigit_expl));
4924
4925	1		init_byte_class(&ndot, ndot_expl, SIZEOF_ARRAY(ndot_expl));
4926
4927	1		alphanumeric_expl[0] = '_';
4928
4929	1		wstart = 1;
4930	1		memcpy(alphanumeric_expl + wstart, digit_expl, 10 * sizeof(char));
4931
4932	1		wstart += 10;
4933	27	100	for (i = 0; i < LETTER_COUNT; ++i)
4934			{
4935	26		alphanumeric_expl[wstart + i] = 'a' + i;
4936			}
4937
4938	1		wstart += LETTER_COUNT;
4939	27	100	for (i = 0; i < LETTER_COUNT; ++i)
4940			{
4941	26		alphanumeric_expl[wstart + i] = 'A' + i;
4942			}
4943
4944	1		init_byte_class(&word_bc, alphanumeric_expl,
4945			SIZEOF_ARRAY(alphanumeric_expl));
4946	1		init_byte_class(&alnum_bc, alphanumeric_expl + 1,
4947			SIZEOF_ARRAY(alphanumeric_expl) - 1);
4948
4949	27	100	for (i = 0; i < LETTER_COUNT; ++i)
4950			{
4951	26		alpha_expl[i] = lower_expl[i] = 'a' + i;
4952			}
4953
4954	1		wstart = LETTER_COUNT;
4955	27	100	for (i = 0; i < LETTER_COUNT; ++i)
4956			{
4957	26		alpha_expl[wstart + i] = upper_expl[i] = 'A' + i;
4958			}
4959
4960	1		init_byte_class(&alpha_bc, alpha_expl,
4961			SIZEOF_ARRAY(alpha_expl));
4962	1		init_byte_class(&lower_bc, lower_expl,
4963			SIZEOF_ARRAY(lower_expl));
4964	1		init_byte_class(&upper_bc, upper_expl,
4965			SIZEOF_ARRAY(upper_expl));
4966
4967	1		memset(alphanumeric_classes, 0, SIZEOF_ARRAY(alphanumeric_classes));
4968
4969	1		memset(non_alphanumeric_classes, 0,
4970			SIZEOF_ARRAY(non_alphanumeric_classes));
4971	1		non_alphanumeric_classes[EOS] = non_alphanumeric_classes[EOL] =
4972	1		non_alphanumeric_classes[SEOL] = 1;
4973
4974	1		posix_regclass_blocks[_CC_VERTSPACE] = VERTICAL_SPACE_BLOCK;
4975	1		posix_regclass_bitmaps[_CC_VERTSPACE] = vertical_whitespace.bitmap;
4976	1		posix_regclass_nbitmaps[_CC_VERTSPACE] = vertical_whitespace.nbitmap;
4977
4978	1		memset(word_posix_regclasses, 0,
4979			SIZEOF_ARRAY(word_posix_regclasses));
4980	1		word_posix_regclasses[_CC_WORDCHAR] =
4981	1		word_posix_regclasses[_CC_DIGIT] =
4982	1		word_posix_regclasses[_CC_ALPHA] =
4983	1		word_posix_regclasses[_CC_LOWER] =
4984	1		word_posix_regclasses[_CC_UPPER] =
4985	1		word_posix_regclasses[_CC_UPPER] =
4986	1		word_posix_regclasses[_CC_ALPHANUMERIC] =
4987	1		word_posix_regclasses[_CC_CASED] =
4988	1		word_posix_regclasses[_CC_XDIGIT] = 1;
4989
4990	1		memset(non_word_posix_regclasses, 0,
4991			SIZEOF_ARRAY(non_word_posix_regclasses));
4992	1		non_word_posix_regclasses[_CC_PUNCT] =
4993	1		non_word_posix_regclasses[_CC_SPACE] =
4994	1		non_word_posix_regclasses[_CC_BLANK] =
4995	1		non_word_posix_regclasses[_CC_VERTSPACE] = 1;
4996
4997	1		memset(newline_posix_regclasses, 0,
4998			SIZEOF_ARRAY(newline_posix_regclasses));
4999	1		newline_posix_regclasses[_CC_SPACE] =
5000	1		newline_posix_regclasses[_CC_CNTRL] =
5001	1		newline_posix_regclasses[_CC_ASCII] =
5002	1		newline_posix_regclasses[_CC_VERTSPACE] = 1;
5003
5004	1		memset(trivial_nodes, 0, SIZEOF_ARRAY(trivial_nodes));
5005	1		trivial_nodes[SUCCEED] = trivial_nodes[NOTHING] =
5006	1		trivial_nodes[TAIL] = trivial_nodes[WHILEM] = 1;
5007
5008	1		memset(dispatch, 0, sizeof(FCompare) * REGNODE_MAX * REGNODE_MAX);
5009
5010	93	100	for (i = 0; i < REGNODE_MAX; ++i)
5011			{
5012	92		dispatch[i][END] = success;
5013			}
5014
5015	93	100	for (i = 0; i < REGNODE_MAX; ++i)
5016			{
5017	92		dispatch[i][SUCCEED] = compare_next;
5018			}
5019
5020	1		dispatch[SUCCEED][SUCCEED] = compare_tails;
5021
5022	1		dispatch[SUCCEED][MBOL] = compare_left_tail;
5023	1		dispatch[MBOL][MBOL] = compare_tails;
5024	1		dispatch[SBOL][MBOL] = compare_tails;
5025	1		dispatch[REG_ANY][MBOL] = compare_mismatch;
5026	1		dispatch[SANY][MBOL] = compare_mismatch;
5027	1		dispatch[ANYOF][MBOL] = compare_anyof_multiline;
5028	1		dispatch[ANYOFD][MBOL] = compare_anyof_multiline;
5029			#ifdef RC_ANYOFM
5030			dispatch[ANYOFM][MBOL] = compare_anyofm_multiline;
5031			#endif
5032			#ifdef RC_NANYOFM
5033			dispatch[NANYOFM][MBOL] = compare_nanyofm_multiline;
5034			#endif
5035	1		dispatch[POSIXD][MBOL] = compare_mismatch;
5036	1		dispatch[POSIXU][MBOL] = compare_mismatch;
5037	1		dispatch[POSIXA][MBOL] = compare_mismatch;
5038	1		dispatch[NPOSIXD][MBOL] = compare_mismatch;
5039	1		dispatch[NPOSIXU][MBOL] = compare_mismatch;
5040	1		dispatch[NPOSIXA][MBOL] = compare_mismatch;
5041	1		dispatch[BRANCH][MBOL] = compare_left_branch;
5042	1		dispatch[EXACT][MBOL] = compare_exact_multiline;
5043	1		dispatch[EXACTF][MBOL] = compare_exact_multiline;
5044	1		dispatch[EXACTFU][MBOL] = compare_exact_multiline;
5045	1		dispatch[NOTHING][MBOL] = compare_left_tail;
5046	1		dispatch[TAIL][MBOL] = compare_left_tail;
5047	1		dispatch[STAR][MBOL] = compare_mismatch;
5048	1		dispatch[PLUS][MBOL] = compare_left_plus;
5049	1		dispatch[CURLY][MBOL] = compare_left_curly;
5050	1		dispatch[CURLYM][MBOL] = compare_left_curly;
5051	1		dispatch[CURLYX][MBOL] = compare_left_curly;
5052	1		dispatch[WHILEM][MBOL] = compare_left_tail;
5053	1		dispatch[OPEN][MBOL] = compare_left_open;
5054	1		dispatch[CLOSE][MBOL] = compare_left_tail;
5055	1		dispatch[IFMATCH][MBOL] = compare_after_assertion;
5056	1		dispatch[UNLESSM][MBOL] = compare_after_assertion;
5057	1		dispatch[MINMOD][MBOL] = compare_left_tail;
5058	1		dispatch[LNBREAK][MBOL] = compare_tails;
5059	1		dispatch[OPTIMIZED][MBOL] = compare_left_tail;
5060
5061	1		dispatch[SUCCEED][SBOL] = compare_left_tail;
5062	1		dispatch[SBOL][SBOL] = compare_tails;
5063	1		dispatch[BRANCH][SBOL] = compare_left_branch;
5064	1		dispatch[NOTHING][SBOL] = compare_left_tail;
5065	1		dispatch[TAIL][SBOL] = compare_left_tail;
5066	1		dispatch[STAR][SBOL] = compare_mismatch;
5067	1		dispatch[PLUS][SBOL] = compare_left_plus;
5068	1		dispatch[CURLY][SBOL] = compare_left_curly;
5069	1		dispatch[CURLYM][SBOL] = compare_left_curly;
5070	1		dispatch[CURLYX][SBOL] = compare_left_curly;
5071	1		dispatch[WHILEM][SBOL] = compare_left_tail;
5072	1		dispatch[OPEN][SBOL] = compare_left_open;
5073	1		dispatch[CLOSE][SBOL] = compare_left_tail;
5074	1		dispatch[IFMATCH][SBOL] = compare_after_assertion;
5075	1		dispatch[UNLESSM][SBOL] = compare_after_assertion;
5076	1		dispatch[MINMOD][SBOL] = compare_left_tail;
5077	1		dispatch[OPTIMIZED][SBOL] = compare_left_tail;
5078
5079	1		dispatch[SUCCEED][EOS] = compare_left_tail;
5080	1		dispatch[EOS][EOS] = compare_tails;
5081	1		dispatch[EOL][EOS] = compare_mismatch;
5082	1		dispatch[SEOL][EOS] = compare_mismatch;
5083	1		dispatch[BRANCH][EOS] = compare_left_branch;
5084	1		dispatch[NOTHING][EOS] = compare_left_tail;
5085	1		dispatch[TAIL][EOS] = compare_left_tail;
5086	1		dispatch[STAR][EOS] = compare_mismatch;
5087	1		dispatch[PLUS][EOS] = compare_left_plus;
5088	1		dispatch[CURLY][EOS] = compare_left_curly;
5089	1		dispatch[CURLYM][EOS] = compare_left_curly;
5090	1		dispatch[CURLYX][EOS] = compare_left_curly;
5091	1		dispatch[WHILEM][EOS] = compare_left_tail;
5092	1		dispatch[OPEN][EOS] = compare_left_open;
5093	1		dispatch[CLOSE][EOS] = compare_left_tail;
5094	1		dispatch[IFMATCH][EOS] = compare_after_assertion;
5095	1		dispatch[UNLESSM][EOS] = compare_after_assertion;
5096	1		dispatch[MINMOD][EOS] = compare_left_tail;
5097	1		dispatch[OPTIMIZED][EOS] = compare_left_tail;
5098
5099	1		dispatch[SUCCEED][EOL] = compare_left_tail;
5100	1		dispatch[EOS][EOL] = compare_tails;
5101	1		dispatch[EOL][EOL] = compare_tails;
5102	1		dispatch[SEOL][EOL] = compare_tails;
5103	1		dispatch[BRANCH][EOL] = compare_left_branch;
5104	1		dispatch[NOTHING][EOL] = compare_left_tail;
5105	1		dispatch[TAIL][EOL] = compare_left_tail;
5106	1		dispatch[STAR][EOL] = compare_mismatch;
5107	1		dispatch[PLUS][EOL] = compare_left_plus;
5108	1		dispatch[CURLY][EOL] = compare_left_curly;
5109	1		dispatch[CURLYM][EOL] = compare_left_curly;
5110	1		dispatch[CURLYX][EOL] = compare_left_curly;
5111	1		dispatch[WHILEM][EOL] = compare_left_tail;
5112	1		dispatch[OPEN][EOL] = compare_left_open;
5113	1		dispatch[CLOSE][EOL] = compare_left_tail;
5114	1		dispatch[IFMATCH][EOL] = compare_after_assertion;
5115	1		dispatch[UNLESSM][EOL] = compare_after_assertion;
5116	1		dispatch[MINMOD][EOL] = compare_left_tail;
5117	1		dispatch[OPTIMIZED][EOL] = compare_left_tail;
5118
5119	1		dispatch[SUCCEED][MEOL] = compare_left_tail;
5120	1		dispatch[EOS][MEOL] = compare_tails;
5121	1		dispatch[EOL][MEOL] = compare_tails;
5122	1		dispatch[MEOL][MEOL] = compare_tails;
5123	1		dispatch[SEOL][MEOL] = compare_tails;
5124	1		dispatch[REG_ANY][MEOL] = compare_mismatch;
5125	1		dispatch[SANY][MEOL] = compare_mismatch;
5126	1		dispatch[ANYOF][MEOL] = compare_anyof_multiline; /* not in tests; remove? */
5127	1		dispatch[POSIXD][MEOL] = compare_mismatch;
5128	1		dispatch[POSIXU][MEOL] = compare_mismatch;
5129	1		dispatch[POSIXA][MEOL] = compare_mismatch;
5130	1		dispatch[NPOSIXD][MEOL] = compare_mismatch;
5131	1		dispatch[NPOSIXU][MEOL] = compare_mismatch;
5132	1		dispatch[NPOSIXA][MEOL] = compare_mismatch;
5133	1		dispatch[BRANCH][MEOL] = compare_left_branch;
5134	1		dispatch[EXACT][MEOL] = compare_exact_multiline;
5135	1		dispatch[EXACTF][MEOL] = compare_exact_multiline;
5136	1		dispatch[EXACTFU][MEOL] = compare_exact_multiline;
5137	1		dispatch[NOTHING][MEOL] = compare_left_tail;
5138	1		dispatch[TAIL][MEOL] = compare_left_tail;
5139	1		dispatch[STAR][MEOL] = compare_mismatch;
5140	1		dispatch[PLUS][MEOL] = compare_left_plus;
5141	1		dispatch[CURLY][MEOL] = compare_left_curly;
5142	1		dispatch[CURLYM][MEOL] = compare_left_curly;
5143	1		dispatch[CURLYX][MEOL] = compare_left_curly;
5144	1		dispatch[WHILEM][MEOL] = compare_left_tail;
5145	1		dispatch[OPEN][MEOL] = compare_left_open;
5146	1		dispatch[CLOSE][MEOL] = compare_left_tail;
5147	1		dispatch[IFMATCH][MEOL] = compare_after_assertion;
5148	1		dispatch[UNLESSM][MEOL] = compare_after_assertion;
5149	1		dispatch[MINMOD][MEOL] = compare_left_tail;
5150	1		dispatch[LNBREAK][MEOL] = compare_mismatch;
5151	1		dispatch[OPTIMIZED][MEOL] = compare_left_tail;
5152
5153	1		dispatch[SUCCEED][SEOL] = compare_left_tail;
5154	1		dispatch[EOS][SEOL] = compare_tails;
5155	1		dispatch[EOL][SEOL] = compare_tails;
5156	1		dispatch[SEOL][SEOL] = compare_tails;
5157	1		dispatch[BRANCH][SEOL] = compare_left_branch;
5158	1		dispatch[NOTHING][SEOL] = compare_left_tail;
5159	1		dispatch[POSIXD][SEOL] = compare_mismatch;
5160	1		dispatch[POSIXU][SEOL] = compare_mismatch;
5161	1		dispatch[POSIXA][SEOL] = compare_mismatch;
5162	1		dispatch[NPOSIXD][SEOL] = compare_mismatch;
5163	1		dispatch[NPOSIXU][SEOL] = compare_mismatch;
5164	1		dispatch[NPOSIXA][SEOL] = compare_mismatch;
5165	1		dispatch[TAIL][SEOL] = compare_left_tail;
5166	1		dispatch[STAR][SEOL] = 0;
5167	1		dispatch[PLUS][SEOL] = compare_left_plus;
5168	1		dispatch[CURLY][SEOL] = compare_left_curly;
5169	1		dispatch[CURLYM][SEOL] = compare_left_curly;
5170	1		dispatch[CURLYX][SEOL] = compare_left_curly;
5171	1		dispatch[WHILEM][SEOL] = compare_left_tail;
5172	1		dispatch[OPEN][SEOL] = compare_left_open;
5173	1		dispatch[CLOSE][SEOL] = compare_left_tail;
5174	1		dispatch[IFMATCH][SEOL] = compare_after_assertion;
5175	1		dispatch[UNLESSM][SEOL] = compare_after_assertion;
5176	1		dispatch[MINMOD][SEOL] = compare_left_tail;
5177	1		dispatch[LNBREAK][SEOL] = compare_mismatch;
5178	1		dispatch[OPTIMIZED][SEOL] = compare_left_tail;
5179
5180	1		dispatch[SUCCEED][BOUND] = compare_left_tail;
5181	1		dispatch[MBOL][BOUND] = compare_bol_word;
5182	1		dispatch[SBOL][BOUND] = compare_bol_word;
5183	1		dispatch[BOUND][BOUND] = compare_tails;
5184	1		dispatch[NBOUND][BOUND] = compare_mismatch;
5185	1		dispatch[REG_ANY][BOUND] = compare_mismatch;
5186	1		dispatch[SANY][BOUND] = compare_mismatch;
5187	1		dispatch[ANYOF][BOUND] = compare_anyof_bound;
5188	1		dispatch[ANYOFD][BOUND] = compare_anyof_bound;
5189			#ifdef RC_ANYOFM
5190			dispatch[ANYOFM][BOUND] = compare_anyofm_bound;
5191			#endif
5192			#ifdef RC_NANYOFM
5193			dispatch[NANYOFM][BOUND] = compare_mismatch;
5194			#endif
5195	1		dispatch[POSIXD][BOUND] = compare_posix_bound;
5196	1		dispatch[POSIXU][BOUND] = compare_posix_bound;
5197	1		dispatch[POSIXA][BOUND] = compare_posix_bound;
5198	1		dispatch[NPOSIXD][BOUND] = compare_negative_posix_word_bound;
5199	1		dispatch[NPOSIXU][BOUND] = compare_mismatch; /* should be replaced, needs extra test */
5200	1		dispatch[NPOSIXA][BOUND] = compare_negative_posix_word_bound;
5201	1		dispatch[BRANCH][BOUND] = compare_left_branch;
5202	1		dispatch[EXACT][BOUND] = compare_exact_bound;
5203	1		dispatch[EXACTF][BOUND] = compare_exact_bound;
5204	1		dispatch[EXACTFU][BOUND] = compare_exact_bound;
5205	1		dispatch[NOTHING][BOUND] = compare_left_tail;
5206	1		dispatch[TAIL][BOUND] = compare_left_tail;
5207	1		dispatch[CURLY][BOUND] = compare_left_curly;
5208	1		dispatch[CURLYM][BOUND] = compare_left_curly;
5209	1		dispatch[CURLYX][BOUND] = compare_left_curly;
5210	1		dispatch[WHILEM][BOUND] = compare_left_tail;
5211	1		dispatch[OPEN][BOUND] = compare_left_open;
5212	1		dispatch[CLOSE][BOUND] = compare_left_tail;
5213	1		dispatch[IFMATCH][BOUND] = compare_after_assertion;
5214	1		dispatch[UNLESSM][BOUND] = compare_after_assertion;
5215	1		dispatch[MINMOD][BOUND] = compare_left_tail;
5216	1		dispatch[LNBREAK][BOUND] = compare_mismatch;
5217	1		dispatch[OPTIMIZED][BOUND] = compare_left_tail;
5218
5219	1		dispatch[SUCCEED][NBOUND] = compare_left_tail;
5220	1		dispatch[MBOL][NBOUND] = compare_bol_nword;
5221	1		dispatch[SBOL][NBOUND] = compare_bol_nword;
5222	1		dispatch[BOUND][NBOUND] = compare_mismatch;
5223	1		dispatch[NBOUND][NBOUND] = compare_tails;
5224	1		dispatch[REG_ANY][NBOUND] = compare_mismatch;
5225	1		dispatch[SANY][NBOUND] = compare_mismatch;
5226	1		dispatch[ANYOF][NBOUND] = compare_anyof_nbound;
5227	1		dispatch[ANYOFD][NBOUND] = compare_anyof_nbound;
5228			#ifdef RC_ANYOFM
5229			dispatch[ANYOFM][NBOUND] = compare_anyofm_nbound;
5230			#endif
5231			#ifdef RC_NANYOFM
5232			dispatch[NANYOFM][NBOUND] = compare_mismatch;
5233			#endif
5234	1		dispatch[POSIXD][NBOUND] = compare_posix_nbound;
5235	1		dispatch[POSIXU][NBOUND] = compare_posix_nbound;
5236	1		dispatch[POSIXA][NBOUND] = compare_posix_nbound;
5237	1		dispatch[NPOSIXD][NBOUND] = compare_negative_posix_word_nbound;
5238	1		dispatch[NPOSIXU][NBOUND] = compare_negative_posix_word_nbound;
5239	1		dispatch[NPOSIXA][NBOUND] = compare_negative_posix_word_nbound;
5240	1		dispatch[BRANCH][NBOUND] = compare_left_branch;
5241	1		dispatch[EXACT][NBOUND] = compare_exact_nbound;
5242	1		dispatch[EXACTF][NBOUND] = compare_exact_nbound;
5243	1		dispatch[EXACTFU][NBOUND] = compare_exact_nbound;
5244	1		dispatch[NOTHING][NBOUND] = compare_left_tail;
5245	1		dispatch[TAIL][NBOUND] = compare_left_tail;
5246	1		dispatch[CURLY][NBOUND] = compare_left_curly;
5247	1		dispatch[CURLYM][NBOUND] = compare_left_curly;
5248	1		dispatch[CURLYX][NBOUND] = compare_left_curly;
5249	1		dispatch[WHILEM][NBOUND] = compare_left_tail;
5250	1		dispatch[OPEN][NBOUND] = compare_left_open;
5251	1		dispatch[CLOSE][NBOUND] = compare_left_tail;
5252	1		dispatch[IFMATCH][NBOUND] = compare_after_assertion;
5253	1		dispatch[UNLESSM][NBOUND] = compare_after_assertion;
5254	1		dispatch[MINMOD][NBOUND] = compare_left_tail;
5255	1		dispatch[LNBREAK][NBOUND] = compare_mismatch;
5256	1		dispatch[OPTIMIZED][NBOUND] = compare_left_tail;
5257
5258	1		dispatch[SUCCEED][REG_ANY] = compare_left_tail;
5259	1		dispatch[MBOL][REG_ANY] = compare_bol;
5260	1		dispatch[SBOL][REG_ANY] = compare_bol;
5261	1		dispatch[BOUND][REG_ANY] = compare_mismatch;
5262	1		dispatch[NBOUND][REG_ANY] = compare_mismatch;
5263	1		dispatch[REG_ANY][REG_ANY] = compare_tails;
5264	1		dispatch[SANY][REG_ANY] = compare_mismatch;
5265	1		dispatch[ANYOF][REG_ANY] = compare_anyof_reg_any;
5266	1		dispatch[ANYOFD][REG_ANY] = compare_anyof_reg_any;
5267			#ifdef RC_ANYOFM
5268			dispatch[ANYOFM][REG_ANY] = compare_anyofm_reg_any;
5269			#endif
5270			#ifdef RC_NANYOFM
5271			dispatch[NANYOFM][REG_ANY] = compare_nanyofm_reg_any;
5272			#endif
5273	1		dispatch[POSIXD][REG_ANY] = compare_posix_reg_any;
5274	1		dispatch[POSIXU][REG_ANY] = compare_posix_reg_any;
5275	1		dispatch[POSIXA][REG_ANY] = compare_posix_reg_any;
5276	1		dispatch[NPOSIXD][REG_ANY] = compare_negative_posix_reg_any;
5277	1		dispatch[NPOSIXU][REG_ANY] = compare_negative_posix_reg_any;
5278	1		dispatch[NPOSIXA][REG_ANY] = compare_negative_posix_reg_any;
5279	1		dispatch[BRANCH][REG_ANY] = compare_left_branch;
5280	1		dispatch[EXACT][REG_ANY] = compare_exact_reg_any;
5281	1		dispatch[EXACTF][REG_ANY] = compare_exact_reg_any;
5282	1		dispatch[EXACTFU][REG_ANY] = compare_exact_reg_any;
5283	1		dispatch[NOTHING][REG_ANY] = compare_left_tail;
5284	1		dispatch[TAIL][REG_ANY] = compare_left_tail;
5285	1		dispatch[STAR][REG_ANY] = compare_mismatch;
5286	1		dispatch[PLUS][REG_ANY] = compare_left_plus;
5287	1		dispatch[CURLY][REG_ANY] = compare_left_curly;
5288	1		dispatch[CURLYM][REG_ANY] = compare_left_curly;
5289	1		dispatch[CURLYX][REG_ANY] = compare_left_curly;
5290	1		dispatch[WHILEM][REG_ANY] = compare_left_tail;
5291	1		dispatch[OPEN][REG_ANY] = compare_left_open;
5292	1		dispatch[CLOSE][REG_ANY] = compare_left_tail;
5293	1		dispatch[IFMATCH][REG_ANY] = compare_after_assertion;
5294	1		dispatch[UNLESSM][REG_ANY] = compare_after_assertion;
5295	1		dispatch[MINMOD][REG_ANY] = compare_left_tail;
5296	1		dispatch[LNBREAK][REG_ANY] = compare_mismatch;
5297	1		dispatch[OPTIMIZED][REG_ANY] = compare_left_tail;
5298
5299	1		dispatch[SUCCEED][SANY] = compare_left_tail;
5300	1		dispatch[MBOL][SANY] = compare_bol;
5301	1		dispatch[SBOL][SANY] = compare_bol;
5302	1		dispatch[BOUND][SANY] = compare_mismatch;
5303	1		dispatch[NBOUND][SANY] = compare_mismatch;
5304	1		dispatch[REG_ANY][SANY] = compare_tails;
5305	1		dispatch[SANY][SANY] = compare_tails;
5306	1		dispatch[ANYOF][SANY] = compare_tails;
5307	1		dispatch[ANYOFD][SANY] = compare_tails;
5308			#ifdef RC_ANYOFM
5309			dispatch[ANYOFM][SANY] = compare_tails;
5310			#endif
5311			#ifdef RC_NANYOFM
5312			dispatch[NANYOFM][SANY] = compare_tails;
5313			#endif
5314	1		dispatch[POSIXD][SANY] = compare_tails;
5315	1		dispatch[POSIXU][SANY] = compare_tails;
5316	1		dispatch[POSIXA][SANY] = compare_tails;
5317	1		dispatch[NPOSIXD][SANY] = compare_tails;
5318	1		dispatch[NPOSIXU][SANY] = compare_tails;
5319	1		dispatch[NPOSIXA][SANY] = compare_tails;
5320	1		dispatch[BRANCH][SANY] = compare_left_branch;
5321	1		dispatch[EXACT][SANY] = compare_tails;
5322	1		dispatch[EXACTF][SANY] = compare_tails;
5323	1		dispatch[EXACTFU][SANY] = compare_tails;
5324	1		dispatch[NOTHING][SANY] = compare_left_tail;
5325	1		dispatch[TAIL][SANY] = compare_left_tail;
5326	1		dispatch[STAR][SANY] = compare_mismatch;
5327	1		dispatch[PLUS][SANY] = compare_left_plus;
5328	1		dispatch[CURLY][SANY] = compare_left_curly;
5329	1		dispatch[CURLYM][SANY] = compare_left_curly;
5330	1		dispatch[CURLYX][SANY] = compare_left_curly;
5331	1		dispatch[WHILEM][SANY] = compare_left_tail;
5332	1		dispatch[OPEN][SANY] = compare_left_open;
5333	1		dispatch[CLOSE][SANY] = compare_left_tail;
5334	1		dispatch[IFMATCH][SANY] = compare_after_assertion;
5335	1		dispatch[UNLESSM][SANY] = compare_after_assertion;
5336	1		dispatch[MINMOD][SANY] = compare_left_tail;
5337	1		dispatch[LNBREAK][SANY] = compare_mismatch;
5338	1		dispatch[OPTIMIZED][SANY] = compare_left_tail;
5339
5340	1		dispatch[SUCCEED][ANYOF] = compare_left_tail;
5341	1		dispatch[MBOL][ANYOF] = compare_bol;
5342	1		dispatch[SBOL][ANYOF] = compare_bol;
5343	1		dispatch[BOUND][ANYOF] = compare_mismatch;
5344	1		dispatch[NBOUND][ANYOF] = compare_mismatch;
5345	1		dispatch[REG_ANY][ANYOF] = compare_reg_any_anyof;
5346	1		dispatch[SANY][ANYOF] = compare_sany_anyof;
5347	1		dispatch[ANYOF][ANYOF] = compare_anyof_anyof;
5348	1		dispatch[ANYOFD][ANYOF] = compare_anyof_anyof;
5349			#ifdef RC_ANYOFM
5350			dispatch[ANYOFM][ANYOF] = compare_anyofm_anyof;
5351			#endif
5352			#ifdef RC_NANYOFM
5353			dispatch[NANYOFM][ANYOF] = compare_mismatch;
5354			#endif
5355	1		dispatch[POSIXD][ANYOF] = compare_posix_anyof;
5356	1		dispatch[POSIXU][ANYOF] = compare_posix_anyof;
5357	1		dispatch[POSIXA][ANYOF] = compare_posix_anyof;
5358	1		dispatch[NPOSIXD][ANYOF] = compare_negative_posix_anyof;
5359	1		dispatch[NPOSIXU][ANYOF] = compare_negative_posix_anyof;
5360	1		dispatch[NPOSIXA][ANYOF] = compare_negative_posix_anyof;
5361	1		dispatch[BRANCH][ANYOF] = compare_left_branch;
5362	1		dispatch[EXACT][ANYOF] = compare_exact_anyof;
5363	1		dispatch[EXACTF][ANYOF] = compare_exactf_anyof;
5364	1		dispatch[EXACTFU][ANYOF] = compare_exactf_anyof;
5365	1		dispatch[NOTHING][ANYOF] = compare_left_tail;
5366	1		dispatch[TAIL][ANYOF] = compare_left_tail;
5367	1		dispatch[STAR][ANYOF] = compare_mismatch;
5368	1		dispatch[PLUS][ANYOF] = compare_left_plus;
5369	1		dispatch[CURLY][ANYOF] = compare_left_curly;
5370	1		dispatch[CURLYM][ANYOF] = compare_left_curly;
5371	1		dispatch[CURLYX][ANYOF] = compare_left_curly;
5372	1		dispatch[WHILEM][ANYOF] = compare_left_tail;
5373	1		dispatch[OPEN][ANYOF] = compare_left_open;
5374	1		dispatch[CLOSE][ANYOF] = compare_left_tail;
5375	1		dispatch[IFMATCH][ANYOF] = compare_after_assertion;
5376	1		dispatch[UNLESSM][ANYOF] = compare_after_assertion;
5377	1		dispatch[MINMOD][ANYOF] = compare_left_tail;
5378	1		dispatch[LNBREAK][ANYOF] = compare_mismatch;
5379	1		dispatch[OPTIMIZED][ANYOF] = compare_left_tail;
5380
5381	1		dispatch[SUCCEED][ANYOFD] = compare_left_tail;
5382	1		dispatch[MBOL][ANYOFD] = compare_bol;
5383	1		dispatch[SBOL][ANYOFD] = compare_bol;
5384	1		dispatch[BOUND][ANYOFD] = compare_mismatch;
5385	1		dispatch[NBOUND][ANYOFD] = compare_mismatch;
5386	1		dispatch[REG_ANY][ANYOFD] = compare_reg_any_anyof;
5387	1		dispatch[SANY][ANYOFD] = compare_sany_anyof;
5388	1		dispatch[ANYOF][ANYOFD] = compare_anyof_anyof;
5389	1		dispatch[ANYOFD][ANYOFD] = compare_anyof_anyof;
5390			#ifdef RC_ANYOFM
5391			dispatch[ANYOFM][ANYOFD] = compare_anyofm_anyof;
5392			#endif
5393			#ifdef RC_NANYOFM
5394			dispatch[NANYOFM][ANYOFD] = compare_mismatch;
5395			#endif
5396	1		dispatch[POSIXD][ANYOFD] = compare_posix_anyof;
5397	1		dispatch[POSIXU][ANYOFD] = compare_posix_anyof;
5398	1		dispatch[POSIXA][ANYOFD] = compare_posix_anyof;
5399	1		dispatch[NPOSIXD][ANYOFD] = compare_negative_posix_anyof;
5400	1		dispatch[NPOSIXU][ANYOFD] = compare_negative_posix_anyof;
5401	1		dispatch[NPOSIXA][ANYOFD] = compare_negative_posix_anyof;
5402	1		dispatch[BRANCH][ANYOFD] = compare_left_branch;
5403	1		dispatch[EXACT][ANYOFD] = compare_exact_anyof;
5404	1		dispatch[EXACTFU][ANYOFD] = compare_exactf_anyof;
5405	1		dispatch[NOTHING][ANYOFD] = compare_left_tail;
5406	1		dispatch[TAIL][ANYOFD] = compare_left_tail;
5407	1		dispatch[STAR][ANYOFD] = compare_mismatch;
5408	1		dispatch[PLUS][ANYOFD] = compare_left_plus;
5409	1		dispatch[CURLY][ANYOFD] = compare_left_curly;
5410	1		dispatch[CURLYM][ANYOFD] = compare_left_curly;
5411	1		dispatch[CURLYX][ANYOFD] = compare_left_curly;
5412	1		dispatch[OPEN][ANYOFD] = compare_left_open;
5413	1		dispatch[CLOSE][ANYOFD] = compare_left_tail;
5414	1		dispatch[IFMATCH][ANYOFD] = compare_after_assertion;
5415	1		dispatch[UNLESSM][ANYOFD] = compare_after_assertion;
5416	1		dispatch[MINMOD][ANYOFD] = compare_left_tail;
5417	1		dispatch[LNBREAK][ANYOFD] = compare_mismatch;
5418	1		dispatch[OPTIMIZED][ANYOFD] = compare_left_tail;
5419
5420			#ifdef RC_ANYOFM
5421			dispatch[SUCCEED][ANYOFM] = compare_left_tail;
5422			dispatch[MBOL][ANYOFM] = compare_bol;
5423			dispatch[SBOL][ANYOFM] = compare_bol;
5424			dispatch[BOUND][ANYOFM] = compare_mismatch;
5425			dispatch[NBOUND][ANYOFM] = compare_mismatch;
5426			dispatch[REG_ANY][ANYOFM] = compare_mismatch;
5427			dispatch[SANY][ANYOFM] = compare_mismatch;
5428			dispatch[ANYOF][ANYOFM] = compare_anyof_anyofm;
5429			dispatch[ANYOFD][ANYOFM] = compare_anyof_anyofm;
5430			dispatch[ANYOFM][ANYOFM] = compare_anyofm_anyofm;
5431			#ifdef RC_NANYOFM
5432			dispatch[NANYOFM][ANYOFM] = compare_mismatch;
5433			#endif
5434			dispatch[POSIXD][ANYOFM] = compare_mismatch;
5435			dispatch[POSIXU][ANYOFM] = compare_mismatch;
5436			dispatch[POSIXA][ANYOFM] = compare_mismatch;
5437			dispatch[NPOSIXD][ANYOFM] = compare_mismatch;
5438			dispatch[NPOSIXU][ANYOFM] = compare_mismatch;
5439			dispatch[NPOSIXA][ANYOFM] = compare_mismatch;
5440			dispatch[BRANCH][ANYOFM] = compare_left_branch;
5441			dispatch[EXACT][ANYOFM] = compare_exact_anyofm;
5442			dispatch[EXACTF][ANYOFM] = compare_exactf_anyofm;
5443			dispatch[EXACTFU][ANYOFM] = compare_exactf_anyofm;
5444			dispatch[NOTHING][ANYOFM] = compare_left_tail;
5445			dispatch[TAIL][ANYOFM] = compare_left_tail;
5446			dispatch[STAR][ANYOFM] = compare_mismatch;
5447			dispatch[PLUS][ANYOFM] = compare_left_plus;
5448			dispatch[CURLY][ANYOFM] = compare_left_curly;
5449			dispatch[CURLYM][ANYOFM] = compare_left_curly;
5450			dispatch[CURLYX][ANYOFM] = compare_left_curly;
5451			dispatch[OPEN][ANYOFM] = compare_left_open;
5452			dispatch[CLOSE][ANYOFM] = compare_left_tail;
5453			dispatch[IFMATCH][ANYOFM] = compare_after_assertion;
5454			dispatch[UNLESSM][ANYOFM] = compare_after_assertion;
5455			dispatch[MINMOD][ANYOFM] = compare_left_tail;
5456			dispatch[LNBREAK][ANYOFM] = compare_mismatch;
5457			dispatch[OPTIMIZED][ANYOFM] = compare_left_tail;
5458			#endif
5459
5460			#ifdef RC_NANYOFM
5461			dispatch[SUCCEED][NANYOFM] = compare_left_tail;
5462			dispatch[MBOL][NANYOFM] = compare_bol;
5463			dispatch[SBOL][NANYOFM] = compare_bol;
5464			dispatch[BOUND][NANYOFM] = compare_mismatch;
5465			dispatch[NBOUND][NANYOFM] = compare_mismatch;
5466			dispatch[REG_ANY][NANYOFM] = compare_mismatch;
5467			dispatch[SANY][NANYOFM] = compare_mismatch;
5468			dispatch[ANYOF][NANYOFM] = compare_anyof_nanyofm;
5469			dispatch[ANYOFD][NANYOFM] = compare_anyof_nanyofm;
5470			dispatch[ANYOFM][NANYOFM] = compare_anyofm_nanyofm;
5471			dispatch[NANYOFM][NANYOFM] = compare_nanyofm_nanyofm;
5472			dispatch[POSIXD][NANYOFM] = compare_posix_nanyofm;
5473			dispatch[POSIXU][NANYOFM] = compare_posix_nanyofm;
5474			dispatch[POSIXA][NANYOFM] = compare_posix_nanyofm;
5475			dispatch[NPOSIXD][NANYOFM] = compare_negative_posix_nanyofm;
5476			dispatch[NPOSIXU][NANYOFM] = compare_negative_posix_nanyofm;
5477			dispatch[NPOSIXA][NANYOFM] = compare_negative_posix_nanyofm;
5478			dispatch[BRANCH][NANYOFM] = compare_left_branch;
5479			dispatch[EXACT][NANYOFM] = compare_exact_nanyofm;
5480			dispatch[EXACTF][NANYOFM] = compare_exactf_nanyofm;
5481			dispatch[EXACTFU][NANYOFM] = compare_exactf_nanyofm;
5482			dispatch[NOTHING][NANYOFM] = compare_left_tail;
5483			dispatch[TAIL][NANYOFM] = compare_left_tail;
5484			dispatch[STAR][NANYOFM] = compare_mismatch;
5485			dispatch[PLUS][NANYOFM] = compare_left_plus;
5486			dispatch[CURLY][NANYOFM] = compare_left_curly;
5487			dispatch[CURLYM][NANYOFM] = compare_left_curly;
5488			dispatch[CURLYX][NANYOFM] = compare_left_curly;
5489			dispatch[OPEN][NANYOFM] = compare_left_open;
5490			dispatch[CLOSE][NANYOFM] = compare_left_tail;
5491			dispatch[IFMATCH][NANYOFM] = compare_after_assertion;
5492			dispatch[UNLESSM][NANYOFM] = compare_after_assertion;
5493			dispatch[MINMOD][NANYOFM] = compare_left_tail;
5494			dispatch[LNBREAK][NANYOFM] = compare_mismatch;
5495			dispatch[OPTIMIZED][NANYOFM] = compare_left_tail;
5496			#endif
5497
5498	1		dispatch[SUCCEED][POSIXD] = compare_left_tail;
5499	1		dispatch[MBOL][POSIXD] = compare_bol;
5500	1		dispatch[SBOL][POSIXD] = compare_bol;
5501	1		dispatch[BOUND][POSIXD] = compare_mismatch;
5502	1		dispatch[NBOUND][POSIXD] = compare_mismatch;
5503	1		dispatch[REG_ANY][POSIXD] = compare_mismatch;
5504	1		dispatch[SANY][POSIXD] = compare_mismatch;
5505	1		dispatch[ANYOF][POSIXD] = compare_anyof_posix;
5506	1		dispatch[ANYOFD][POSIXD] = compare_anyof_posix;
5507			#ifdef RC_ANYOFM
5508			dispatch[ANYOFM][POSIXD] = compare_anyofm_posix;
5509			#endif
5510			#ifdef RC_NANYOFM
5511			dispatch[NANYOFM][POSIXD] = compare_nanyofm_posix;
5512			#endif
5513	1		dispatch[POSIXD][POSIXD] = compare_posix_posix;
5514	1		dispatch[POSIXU][POSIXD] = compare_posix_posix;
5515	1		dispatch[POSIXA][POSIXD] = compare_posix_posix;
5516	1		dispatch[NPOSIXD][POSIXD] = compare_mismatch;
5517	1		dispatch[NPOSIXU][POSIXD] = compare_mismatch;
5518	1		dispatch[NPOSIXA][POSIXD] = compare_mismatch;
5519	1		dispatch[BRANCH][POSIXD] = compare_left_branch;
5520	1		dispatch[EXACT][POSIXD] = compare_exact_posix;
5521	1		dispatch[EXACTF][POSIXD] = compare_exactf_posix;
5522	1		dispatch[EXACTFU][POSIXD] = compare_exactf_posix;
5523	1		dispatch[NOTHING][POSIXD] = compare_left_tail;
5524	1		dispatch[STAR][POSIXD] = compare_mismatch;
5525	1		dispatch[PLUS][POSIXD] = compare_left_plus;
5526	1		dispatch[CURLY][POSIXD] = compare_left_curly;
5527	1		dispatch[CURLYM][POSIXD] = compare_left_curly;
5528	1		dispatch[CURLYX][POSIXD] = compare_left_curly;
5529	1		dispatch[OPEN][POSIXD] = compare_left_open;
5530	1		dispatch[CLOSE][POSIXD] = compare_left_tail;
5531	1		dispatch[IFMATCH][POSIXD] = compare_after_assertion;
5532	1		dispatch[UNLESSM][POSIXD] = compare_after_assertion;
5533	1		dispatch[MINMOD][POSIXD] = compare_left_tail;
5534	1		dispatch[LNBREAK][POSIXD] = compare_mismatch;
5535	1		dispatch[OPTIMIZED][POSIXD] = compare_left_tail;
5536
5537	1		dispatch[SUCCEED][POSIXU] = compare_left_tail;
5538	1		dispatch[MBOL][POSIXU] = compare_bol;
5539	1		dispatch[SBOL][POSIXU] = compare_bol;
5540	1		dispatch[BOUND][POSIXU] = compare_mismatch;
5541	1		dispatch[NBOUND][POSIXU] = compare_mismatch;
5542	1		dispatch[REG_ANY][POSIXU] = compare_mismatch;
5543	1		dispatch[SANY][POSIXU] = compare_mismatch;
5544	1		dispatch[ANYOF][POSIXU] = compare_anyof_posix;
5545	1		dispatch[ANYOFD][POSIXU] = compare_anyof_posix;
5546			#ifdef RC_ANYOFM
5547			dispatch[ANYOFM][POSIXU] = compare_anyofm_posix;
5548			#endif
5549			#ifdef RC_NANYOFM
5550			dispatch[NANYOFM][POSIXU] = compare_nanyofm_posix;
5551			#endif
5552	1		dispatch[POSIXD][POSIXU] = compare_posix_posix;
5553	1		dispatch[POSIXA][POSIXU] = compare_posix_posix;
5554	1		dispatch[POSIXU][POSIXU] = compare_posix_posix;
5555	1		dispatch[NPOSIXD][POSIXU] = compare_mismatch;
5556	1		dispatch[NPOSIXU][POSIXU] = compare_mismatch;
5557	1		dispatch[NPOSIXA][POSIXU] = compare_mismatch;
5558	1		dispatch[BRANCH][POSIXU] = compare_left_branch;
5559	1		dispatch[EXACT][POSIXU] = compare_exact_posix;
5560	1		dispatch[EXACTF][POSIXU] = compare_exact_posix;
5561	1		dispatch[EXACTFU][POSIXU] = compare_exact_posix;
5562	1		dispatch[NOTHING][POSIXU] = compare_left_tail;
5563	1		dispatch[TAIL][POSIXU] = compare_left_tail;
5564	1		dispatch[STAR][POSIXU] = compare_mismatch;
5565	1		dispatch[PLUS][POSIXU] = compare_left_plus;
5566	1		dispatch[CURLY][POSIXU] = compare_left_curly;
5567	1		dispatch[CURLYM][POSIXU] = compare_left_curly;
5568	1		dispatch[CURLYX][POSIXU] = compare_left_curly;
5569	1		dispatch[OPEN][POSIXU] = compare_left_open;
5570	1		dispatch[CLOSE][POSIXU] = compare_left_tail;
5571	1		dispatch[IFMATCH][POSIXU] = compare_after_assertion;
5572	1		dispatch[UNLESSM][POSIXU] = compare_after_assertion;
5573	1		dispatch[MINMOD][POSIXU] = compare_left_tail;
5574	1		dispatch[LNBREAK][POSIXU] = compare_mismatch;
5575	1		dispatch[OPTIMIZED][POSIXU] = compare_left_tail;
5576
5577	1		dispatch[SUCCEED][POSIXA] = compare_left_tail;
5578	1		dispatch[MBOL][POSIXA] = compare_bol;
5579	1		dispatch[SBOL][POSIXA] = compare_bol;
5580	1		dispatch[BOUND][POSIXA] = compare_mismatch;
5581	1		dispatch[NBOUND][POSIXA] = compare_mismatch;
5582	1		dispatch[REG_ANY][POSIXA] = compare_mismatch;
5583	1		dispatch[SANY][POSIXA] = compare_mismatch;
5584	1		dispatch[ANYOF][POSIXA] = compare_anyof_posixa;
5585	1		dispatch[ANYOFD][POSIXA] = compare_anyof_posixa;
5586			#ifdef RC_ANYOFM
5587			dispatch[ANYOFM][POSIXA] = compare_anyofm_posix;
5588			#endif
5589			#ifdef RC_NANYOFM
5590			dispatch[NANYOFM][POSIXA] = compare_nanyofm_posix;
5591			#endif
5592	1		dispatch[POSIXD][POSIXA] = compare_mismatch;
5593	1		dispatch[POSIXU][POSIXA] = compare_mismatch;
5594	1		dispatch[POSIXA][POSIXA] = compare_posix_posix;
5595	1		dispatch[NPOSIXD][POSIXA] = compare_mismatch;
5596	1		dispatch[NPOSIXU][POSIXA] = compare_mismatch;
5597	1		dispatch[NPOSIXA][POSIXA] = compare_mismatch;
5598	1		dispatch[BRANCH][POSIXA] = compare_left_branch;
5599	1		dispatch[EXACT][POSIXA] = compare_exact_posix;
5600	1		dispatch[EXACTF][POSIXA] = compare_exact_posix;
5601	1		dispatch[EXACTFU][POSIXA] = compare_exact_posix;
5602	1		dispatch[NOTHING][POSIXA] = compare_left_tail;
5603	1		dispatch[STAR][POSIXA] = compare_mismatch;
5604	1		dispatch[PLUS][POSIXA] = compare_left_plus;
5605	1		dispatch[CURLY][POSIXA] = compare_left_curly;
5606	1		dispatch[CURLYM][POSIXA] = compare_left_curly;
5607	1		dispatch[CURLYX][POSIXA] = compare_left_curly;
5608	1		dispatch[OPEN][POSIXA] = compare_left_open;
5609	1		dispatch[CLOSE][POSIXA] = compare_left_tail;
5610	1		dispatch[IFMATCH][POSIXA] = compare_after_assertion;
5611	1		dispatch[UNLESSM][POSIXA] = compare_after_assertion;
5612	1		dispatch[MINMOD][POSIXA] = compare_left_tail;
5613	1		dispatch[LNBREAK][POSIXA] = compare_mismatch;
5614	1		dispatch[OPTIMIZED][POSIXA] = compare_left_tail;
5615
5616	1		dispatch[SUCCEED][NPOSIXD] = compare_left_tail;
5617	1		dispatch[MBOL][NPOSIXD] = compare_bol;
5618	1		dispatch[SBOL][NPOSIXD] = compare_bol;
5619	1		dispatch[BOUND][NPOSIXD] = compare_mismatch;
5620	1		dispatch[NBOUND][NPOSIXD] = compare_mismatch;
5621	1		dispatch[REG_ANY][NPOSIXD] = compare_mismatch;
5622	1		dispatch[SANY][NPOSIXD] = compare_mismatch;
5623	1		dispatch[ANYOF][NPOSIXD] = compare_anyof_negative_posix;
5624	1		dispatch[ANYOFD][NPOSIXD] = compare_anyof_negative_posix;
5625			#ifdef RC_ANYOFM
5626			dispatch[ANYOFM][NPOSIXD] = compare_anyofm_negative_posix;
5627			#endif
5628			#ifdef RC_NANYOFM
5629			dispatch[NANYOFM][NPOSIXD] = compare_nanyofm_negative_posix;
5630			#endif
5631	1		dispatch[POSIXD][NPOSIXD] = compare_posix_negative_posix;
5632	1		dispatch[POSIXU][NPOSIXD] = compare_posix_negative_posix;
5633	1		dispatch[POSIXA][NPOSIXD] = compare_posix_negative_posix;
5634	1		dispatch[NPOSIXD][NPOSIXD] = compare_negative_posix_negative_posix;
5635	1		dispatch[NPOSIXU][NPOSIXD] = compare_negative_posix_negative_posix;
5636	1		dispatch[NPOSIXA][NPOSIXD] = compare_mismatch;
5637	1		dispatch[BRANCH][NPOSIXD] = compare_left_branch;
5638	1		dispatch[EXACT][NPOSIXD] = compare_exact_negative_posix;
5639	1		dispatch[EXACTF][NPOSIXD] = compare_exactf_negative_posix;
5640	1		dispatch[EXACTFU][NPOSIXD] = compare_exactf_negative_posix;
5641	1		dispatch[NOTHING][NPOSIXD] = compare_left_tail;
5642	1		dispatch[STAR][NPOSIXD] = compare_mismatch;
5643	1		dispatch[PLUS][NPOSIXD] = compare_left_plus;
5644	1		dispatch[CURLY][NPOSIXD] = compare_left_curly;
5645	1		dispatch[CURLYM][NPOSIXD] = compare_left_curly;
5646	1		dispatch[CURLYX][NPOSIXD] = compare_left_curly;
5647	1		dispatch[OPEN][NPOSIXD] = compare_left_open;
5648	1		dispatch[CLOSE][NPOSIXD] = compare_left_tail;
5649	1		dispatch[IFMATCH][NPOSIXD] = compare_after_assertion;
5650	1		dispatch[UNLESSM][NPOSIXD] = compare_after_assertion;
5651	1		dispatch[MINMOD][NPOSIXD] = compare_left_tail;
5652	1		dispatch[LNBREAK][NPOSIXD] = compare_mismatch;
5653	1		dispatch[OPTIMIZED][NPOSIXD] = compare_left_tail;
5654
5655	1		dispatch[SUCCEED][NPOSIXU] = compare_left_tail;
5656	1		dispatch[MBOL][NPOSIXU] = compare_bol;
5657	1		dispatch[SBOL][NPOSIXU] = compare_bol;
5658	1		dispatch[BOUND][NPOSIXU] = compare_mismatch;
5659	1		dispatch[NBOUND][NPOSIXU] = compare_mismatch;
5660	1		dispatch[REG_ANY][NPOSIXU] = compare_mismatch;
5661	1		dispatch[SANY][NPOSIXU] = compare_mismatch;
5662	1		dispatch[ANYOF][NPOSIXU] = compare_anyof_negative_posix;
5663	1		dispatch[ANYOFD][NPOSIXU] = compare_anyof_negative_posix;
5664			#ifdef RC_ANYOFM
5665			dispatch[ANYOFM][NPOSIXU] = compare_anyofm_negative_posix;
5666			#endif
5667			#ifdef RC_NANYOFM
5668			dispatch[NANYOFM][NPOSIXU] = compare_nanyofm_negative_posix;
5669			#endif
5670	1		dispatch[POSIXD][NPOSIXU] = compare_posix_negative_posix;
5671	1		dispatch[POSIXU][NPOSIXU] = compare_posix_negative_posix;
5672	1		dispatch[POSIXA][NPOSIXU] = compare_posix_negative_posix;
5673	1		dispatch[NPOSIXD][NPOSIXU] = compare_negative_posix_negative_posix;
5674	1		dispatch[NPOSIXU][NPOSIXU] = compare_negative_posix_negative_posix;
5675	1		dispatch[NPOSIXA][NPOSIXU] = compare_mismatch;
5676	1		dispatch[BRANCH][NPOSIXU] = compare_left_branch;
5677	1		dispatch[EXACT][NPOSIXU] = compare_exact_negative_posix;
5678	1		dispatch[EXACTF][NPOSIXU] = compare_exactf_negative_posix;
5679	1		dispatch[EXACTFU][NPOSIXU] = compare_exactf_negative_posix;
5680	1		dispatch[NOTHING][NPOSIXU] = compare_left_tail;
5681	1		dispatch[STAR][NPOSIXU] = compare_mismatch;
5682	1		dispatch[PLUS][NPOSIXU] = compare_left_plus;
5683	1		dispatch[CURLY][NPOSIXU] = compare_left_curly;
5684	1		dispatch[CURLYM][NPOSIXU] = compare_left_curly;
5685	1		dispatch[CURLYX][NPOSIXU] = compare_left_curly;
5686	1		dispatch[OPEN][NPOSIXU] = compare_left_open;
5687	1		dispatch[CLOSE][NPOSIXU] = compare_left_tail;
5688	1		dispatch[IFMATCH][NPOSIXU] = compare_after_assertion;
5689	1		dispatch[UNLESSM][NPOSIXU] = compare_after_assertion;
5690	1		dispatch[MINMOD][NPOSIXU] = compare_left_tail;
5691	1		dispatch[LNBREAK][NPOSIXU] = compare_mismatch;
5692	1		dispatch[OPTIMIZED][NPOSIXU] = compare_left_tail;
5693
5694	1		dispatch[SUCCEED][NPOSIXA] = compare_left_tail;
5695	1		dispatch[MBOL][NPOSIXA] = compare_bol;
5696	1		dispatch[SBOL][NPOSIXA] = compare_bol;
5697	1		dispatch[BOUND][NPOSIXA] = compare_mismatch;
5698	1		dispatch[NBOUND][NPOSIXA] = compare_mismatch;
5699	1		dispatch[REG_ANY][NPOSIXA] = compare_mismatch;
5700	1		dispatch[SANY][NPOSIXA] = compare_mismatch;
5701	1		dispatch[ANYOF][NPOSIXA] = compare_anyof_negative_posix;
5702	1		dispatch[ANYOFD][NPOSIXA] = compare_anyof_negative_posix;
5703			#ifdef RC_ANYOFM
5704			dispatch[ANYOFM][NPOSIXA] = compare_anyofm_negative_posix;
5705			#endif
5706			#ifdef RC_NANYOFM
5707			dispatch[NANYOFM][NPOSIXA] = compare_nanyofm_negative_posix;
5708			#endif
5709	1		dispatch[POSIXD][NPOSIXA] = compare_posix_negative_posix;
5710	1		dispatch[POSIXU][NPOSIXA] = compare_posix_negative_posix;
5711	1		dispatch[POSIXA][NPOSIXA] = compare_posix_negative_posix;
5712	1		dispatch[NPOSIXD][NPOSIXA] = compare_negative_posix_negative_posix;
5713	1		dispatch[NPOSIXU][NPOSIXA] = compare_negative_posix_negative_posix;
5714	1		dispatch[NPOSIXA][NPOSIXA] = compare_negative_posix_negative_posix;
5715	1		dispatch[BRANCH][NPOSIXA] = compare_left_branch;
5716	1		dispatch[EXACT][NPOSIXA] = compare_exact_negative_posix;
5717	1		dispatch[EXACTF][NPOSIXA] = compare_exactf_negative_posix;
5718	1		dispatch[EXACTFU][NPOSIXA] = compare_exactf_negative_posix;
5719	1		dispatch[NOTHING][NPOSIXA] = compare_left_tail;
5720	1		dispatch[STAR][NPOSIXA] = compare_mismatch;
5721	1		dispatch[PLUS][NPOSIXA] = compare_left_plus;
5722	1		dispatch[CURLY][NPOSIXA] = compare_left_curly;
5723	1		dispatch[CURLYM][NPOSIXA] = compare_left_curly;
5724	1		dispatch[CURLYX][NPOSIXA] = compare_left_curly;
5725	1		dispatch[OPEN][NPOSIXA] = compare_left_open;
5726	1		dispatch[CLOSE][NPOSIXA] = compare_left_tail;
5727	1		dispatch[IFMATCH][NPOSIXA] = compare_after_assertion;
5728	1		dispatch[UNLESSM][NPOSIXA] = compare_after_assertion;
5729	1		dispatch[MINMOD][NPOSIXA] = compare_left_tail;
5730	1		dispatch[LNBREAK][NPOSIXA] = compare_mismatch;
5731	1		dispatch[OPTIMIZED][NPOSIXA] = compare_left_tail;
5732
5733	93	100	for (i = 0; i < REGNODE_MAX; ++i)
5734			{
5735	92		dispatch[i][BRANCH] = compare_right_branch;
5736			}
5737
5738	1		dispatch[SUCCEED][BRANCH] = compare_left_tail;
5739	1		dispatch[ANYOF][BRANCH] = compare_anyof_branch;
5740	1		dispatch[ANYOFD][BRANCH] = compare_anyof_branch;
5741			#ifdef RC_ANYOFM
5742			dispatch[ANYOFM][BRANCH] = compare_anyofm_branch;
5743			#endif
5744	1		dispatch[BRANCH][BRANCH] = compare_left_branch;
5745	1		dispatch[NOTHING][BRANCH] = compare_left_tail;
5746	1		dispatch[TAIL][BRANCH] = compare_left_tail;
5747	1		dispatch[WHILEM][BRANCH] = compare_left_tail;
5748	1		dispatch[OPEN][BRANCH] = compare_left_open;
5749	1		dispatch[CLOSE][BRANCH] = compare_left_tail;
5750	1		dispatch[IFMATCH][BRANCH] = compare_after_assertion;
5751	1		dispatch[UNLESSM][BRANCH] = compare_after_assertion;
5752	1		dispatch[MINMOD][BRANCH] = compare_left_tail;
5753	1		dispatch[OPTIMIZED][BRANCH] = compare_left_tail;
5754
5755	1		dispatch[SUCCEED][EXACT] = compare_left_tail;
5756	1		dispatch[MBOL][EXACT] = compare_bol;
5757	1		dispatch[SBOL][EXACT] = compare_bol;
5758	1		dispatch[BOUND][EXACT] = compare_mismatch;
5759	1		dispatch[NBOUND][EXACT] = compare_mismatch;
5760	1		dispatch[REG_ANY][EXACT] = compare_mismatch;
5761	1		dispatch[SANY][EXACT] = compare_mismatch;
5762	1		dispatch[ANYOF][EXACT] = compare_anyof_exact;
5763	1		dispatch[ANYOFD][EXACT] = compare_anyof_exact;
5764			#ifdef RC_ANYOFM
5765			dispatch[ANYOFM][EXACT] = compare_anyofm_exact;
5766			#endif
5767			#ifdef RC_NANYOFM
5768			dispatch[NANYOFM][EXACT] = compare_mismatch;
5769			#endif
5770	1		dispatch[POSIXD][EXACT] = compare_mismatch;
5771	1		dispatch[POSIXU][EXACT] = compare_mismatch;
5772	1		dispatch[POSIXA][EXACT] = compare_mismatch;
5773	1		dispatch[NPOSIXD][EXACT] = compare_mismatch;
5774	1		dispatch[NPOSIXU][EXACT] = compare_mismatch;
5775	1		dispatch[NPOSIXA][EXACT] = compare_mismatch;
5776	1		dispatch[BRANCH][EXACT] = compare_left_branch;
5777	1		dispatch[EXACT][EXACT] = compare_exact_exact;
5778	1		dispatch[EXACTF][EXACT] = compare_exactf_exact;
5779	1		dispatch[EXACTFU][EXACT] = compare_exactf_exact;
5780	1		dispatch[NOTHING][EXACT] = compare_left_tail;
5781	1		dispatch[TAIL][EXACT] = compare_left_tail;
5782	1		dispatch[STAR][EXACT] = compare_mismatch;
5783	1		dispatch[PLUS][EXACT] = compare_left_plus;
5784	1		dispatch[CURLY][EXACT] = compare_left_curly;
5785	1		dispatch[CURLYM][EXACT] = compare_left_curly;
5786	1		dispatch[CURLYX][EXACT] = compare_left_curly;
5787	1		dispatch[WHILEM][EXACT] = compare_left_tail;
5788	1		dispatch[OPEN][EXACT] = compare_left_open;
5789	1		dispatch[CLOSE][EXACT] = compare_left_tail;
5790	1		dispatch[IFMATCH][EXACT] = compare_after_assertion;
5791	1		dispatch[UNLESSM][EXACT] = compare_after_assertion;
5792	1		dispatch[MINMOD][EXACT] = compare_left_tail;
5793	1		dispatch[LNBREAK][EXACT] = compare_mismatch;
5794	1		dispatch[OPTIMIZED][EXACT] = compare_left_tail;
5795
5796	1		dispatch[SUCCEED][EXACTF] = compare_left_tail;
5797	1		dispatch[MBOL][EXACTF] = compare_bol;
5798	1		dispatch[SBOL][EXACTF] = compare_bol;
5799	1		dispatch[BOUND][EXACTF] = compare_mismatch;
5800	1		dispatch[NBOUND][EXACTF] = compare_mismatch;
5801	1		dispatch[REG_ANY][EXACTF] = compare_mismatch;
5802	1		dispatch[SANY][EXACTF] = compare_mismatch;
5803	1		dispatch[ANYOF][EXACTF] = compare_anyof_exactf;
5804	1		dispatch[ANYOFD][EXACTF] = compare_anyof_exactf;
5805			#ifdef RC_ANYOFM
5806			dispatch[ANYOFM][EXACTF] = compare_anyofm_exactf;
5807			#endif
5808			#ifdef RC_NANYOFM
5809			dispatch[NANYOFM][EXACTF] = compare_mismatch;
5810			#endif
5811	1		dispatch[POSIXD][EXACTF] = compare_mismatch;
5812	1		dispatch[POSIXU][EXACTF] = compare_mismatch;
5813	1		dispatch[POSIXA][EXACTF] = compare_mismatch;
5814	1		dispatch[NPOSIXD][EXACTF] = compare_mismatch;
5815	1		dispatch[NPOSIXU][EXACTF] = compare_mismatch;
5816	1		dispatch[NPOSIXA][EXACTF] = compare_mismatch;
5817	1		dispatch[BRANCH][EXACTF] = compare_left_branch;
5818	1		dispatch[EXACT][EXACTF] = compare_exact_exactf;
5819	1		dispatch[EXACTF][EXACTF] = compare_exactf_exactf;
5820	1		dispatch[NOTHING][EXACTF] = compare_left_tail;
5821	1		dispatch[TAIL][EXACTF] = compare_left_tail;
5822	1		dispatch[STAR][EXACTF] = compare_mismatch;
5823	1		dispatch[PLUS][EXACTF] = compare_left_plus;
5824	1		dispatch[CURLY][EXACTF] = compare_left_curly;
5825	1		dispatch[CURLYM][EXACTF] = compare_left_curly;
5826	1		dispatch[CURLYX][EXACTF] = compare_left_curly;
5827	1		dispatch[WHILEM][EXACTF] = compare_left_tail;
5828	1		dispatch[OPEN][EXACTF] = compare_left_open;
5829	1		dispatch[CLOSE][EXACTF] = compare_left_tail;
5830	1		dispatch[IFMATCH][EXACTF] = compare_after_assertion;
5831	1		dispatch[UNLESSM][EXACTF] = compare_after_assertion;
5832	1		dispatch[MINMOD][EXACTF] = compare_left_tail;
5833	1		dispatch[LNBREAK][EXACTF] = compare_mismatch;
5834	1		dispatch[OPTIMIZED][EXACTF] = compare_left_tail;
5835
5836	1		dispatch[SUCCEED][EXACTFU] = compare_left_tail;
5837	1		dispatch[MBOL][EXACTFU] = compare_bol;
5838	1		dispatch[SBOL][EXACTFU] = compare_bol;
5839	1		dispatch[BOUND][EXACTFU] = compare_mismatch;
5840	1		dispatch[NBOUND][EXACTFU] = compare_mismatch;
5841	1		dispatch[REG_ANY][EXACTFU] = compare_mismatch;
5842	1		dispatch[SANY][EXACTFU] = compare_mismatch;
5843	1		dispatch[ANYOF][EXACTFU] = compare_anyof_exactf;
5844	1		dispatch[ANYOFD][EXACTFU] = compare_anyof_exactf;
5845			#ifdef RC_ANYOFM
5846			dispatch[ANYOFM][EXACTFU] = compare_anyofm_exactf;
5847			#endif
5848			#ifdef RC_NANYOFM
5849			dispatch[NANYOFM][EXACTFU] = compare_mismatch;
5850			#endif
5851	1		dispatch[POSIXD][EXACTFU] = compare_mismatch;
5852	1		dispatch[POSIXU][EXACTFU] = compare_mismatch;
5853	1		dispatch[POSIXA][EXACTFU] = compare_mismatch;
5854	1		dispatch[NPOSIXD][EXACTFU] = compare_mismatch;
5855	1		dispatch[NPOSIXU][EXACTFU] = compare_mismatch;
5856	1		dispatch[NPOSIXA][EXACTFU] = compare_mismatch;
5857	1		dispatch[BRANCH][EXACTFU] = compare_left_branch;
5858	1		dispatch[EXACT][EXACTFU] = compare_exact_exactf;
5859	1		dispatch[EXACTF][EXACTFU] = compare_exactf_exactf;
5860	1		dispatch[EXACTFU][EXACTFU] = compare_exactf_exactf;
5861	1		dispatch[NOTHING][EXACTFU] = compare_left_tail;
5862	1		dispatch[STAR][EXACTFU] = compare_mismatch;
5863	1		dispatch[PLUS][EXACTFU] = compare_left_plus;
5864	1		dispatch[CURLY][EXACTFU] = compare_left_curly;
5865	1		dispatch[CURLYM][EXACTFU] = compare_left_curly;
5866	1		dispatch[CURLYX][EXACTFU] = compare_left_curly;
5867	1		dispatch[OPEN][EXACTFU] = compare_left_open;
5868	1		dispatch[CLOSE][EXACTFU] = compare_left_tail;
5869	1		dispatch[IFMATCH][EXACTFU] = compare_after_assertion;
5870	1		dispatch[UNLESSM][EXACTFU] = compare_after_assertion;
5871	1		dispatch[MINMOD][EXACTFU] = compare_left_tail;
5872	1		dispatch[LNBREAK][EXACTFU] = compare_mismatch;
5873	1		dispatch[OPTIMIZED][EXACTFU] = compare_left_tail;
5874
5875			#ifdef RC_EXACT_ONLY8
5876			dispatch[EXACT_ONLY8][EXACT_ONLY8] = compare_exact_exact;
5877			#endif
5878
5879	93	100	for (i = 0; i < REGNODE_MAX; ++i)
5880			{
5881	92		dispatch[i][NOTHING] = compare_next;
5882			}
5883
5884	1		dispatch[SUCCEED][NOTHING] = compare_tails;
5885	1		dispatch[NOTHING][NOTHING] = compare_tails;
5886	1		dispatch[TAIL][NOTHING] = compare_tails;
5887	1		dispatch[WHILEM][NOTHING] = compare_tails;
5888	1		dispatch[CLOSE][NOTHING] = compare_tails;
5889	1		dispatch[MINMOD][NOTHING] = compare_tails;
5890	1		dispatch[OPTIMIZED][NOTHING] = compare_tails;
5891
5892	93	100	for (i = 0; i < REGNODE_MAX; ++i)
5893			{
5894	92		dispatch[i][TAIL] = compare_next;
5895			}
5896
5897	1		dispatch[SUCCEED][TAIL] = compare_tails;
5898	1		dispatch[NOTHING][TAIL] = compare_tails;
5899	1		dispatch[TAIL][TAIL] = compare_tails;
5900	1		dispatch[WHILEM][TAIL] = compare_tails;
5901	1		dispatch[CLOSE][TAIL] = compare_tails;
5902	1		dispatch[MINMOD][TAIL] = compare_tails;
5903	1		dispatch[OPTIMIZED][TAIL] = compare_tails;
5904
5905	93	100	for (i = 0; i < REGNODE_MAX; ++i)
5906			{
5907	92		dispatch[i][STAR] = compare_right_star;
5908			}
5909
5910	1		dispatch[SUCCEED][STAR] = compare_left_tail;
5911	1		dispatch[EOS][STAR] = compare_tails;
5912	1		dispatch[EOL][STAR] = compare_tails;
5913	1		dispatch[MEOL][STAR] = compare_tails;
5914	1		dispatch[SEOL][STAR] = compare_tails;
5915	1		dispatch[NOTHING][STAR] = compare_left_tail;
5916	1		dispatch[TAIL][STAR] = compare_left_tail;
5917	1		dispatch[STAR][STAR] = compare_repeat_star;
5918	1		dispatch[PLUS][STAR] = compare_repeat_star;
5919	1		dispatch[CURLY][STAR] = compare_curly_star;
5920	1		dispatch[CURLYM][STAR] = compare_curly_star;
5921	1		dispatch[CURLYX][STAR] = compare_curly_star;
5922	1		dispatch[WHILEM][STAR] = compare_left_tail;
5923	1		dispatch[OPEN][STAR] = compare_left_open;
5924	1		dispatch[CLOSE][STAR] = compare_left_tail;
5925	1		dispatch[IFMATCH][STAR] = compare_after_assertion;
5926	1		dispatch[UNLESSM][STAR] = compare_after_assertion;
5927	1		dispatch[MINMOD][STAR] = compare_left_tail;
5928	1		dispatch[OPTIMIZED][STAR] = compare_left_tail;
5929
5930	93	100	for (i = 0; i < REGNODE_MAX; ++i)
5931			{
5932	92		dispatch[i][PLUS] = compare_right_plus;
5933			}
5934
5935	1		dispatch[SUCCEED][PLUS] = compare_left_tail;
5936	1		dispatch[NOTHING][PLUS] = compare_left_tail;
5937	1		dispatch[TAIL][PLUS] = compare_left_tail;
5938	1		dispatch[PLUS][PLUS] = compare_plus_plus;
5939	1		dispatch[CURLY][PLUS] = compare_curly_plus;
5940	1		dispatch[CURLYM][PLUS] = compare_curly_plus;
5941	1		dispatch[CURLYX][PLUS] = compare_curly_plus;
5942	1		dispatch[WHILEM][PLUS] = compare_left_tail;
5943	1		dispatch[OPEN][PLUS] = compare_left_open;
5944	1		dispatch[CLOSE][PLUS] = compare_left_tail;
5945	1		dispatch[IFMATCH][PLUS] = compare_after_assertion;
5946	1		dispatch[UNLESSM][PLUS] = compare_after_assertion;
5947	1		dispatch[MINMOD][PLUS] = compare_left_tail;
5948	1		dispatch[OPTIMIZED][PLUS] = compare_left_tail;
5949
5950	93	100	for (i = 0; i < REGNODE_MAX; ++i)
5951			{
5952	92		dispatch[i][CURLY] = compare_right_curly;
5953			}
5954
5955	1		dispatch[SUCCEED][CURLY] = compare_left_tail;
5956	1		dispatch[NOTHING][CURLY] = compare_left_tail;
5957	1		dispatch[TAIL][CURLY] = compare_left_tail;
5958	1		dispatch[PLUS][CURLY] = compare_plus_curly;
5959	1		dispatch[CURLY][CURLY] = compare_curly_curly;
5960	1		dispatch[CURLYM][CURLY] = compare_curly_curly;
5961	1		dispatch[CURLYX][CURLY] = compare_curly_curly;
5962	1		dispatch[WHILEM][CURLY] = compare_left_tail;
5963	1		dispatch[OPEN][CURLY] = compare_left_open;
5964	1		dispatch[CLOSE][CURLY] = compare_left_tail;
5965	1		dispatch[IFMATCH][CURLY] = compare_after_assertion;
5966	1		dispatch[UNLESSM][CURLY] = compare_after_assertion;
5967	1		dispatch[SUSPEND][CURLY] = compare_suspend_curly;
5968	1		dispatch[MINMOD][CURLY] = compare_left_tail;
5969	1		dispatch[OPTIMIZED][CURLY] = compare_left_tail;
5970
5971	93	100	for (i = 0; i < REGNODE_MAX; ++i)
5972			{
5973	92		dispatch[i][CURLYM] = compare_right_curly;
5974			}
5975
5976	1		dispatch[SUCCEED][CURLYM] = compare_left_tail;
5977	1		dispatch[NOTHING][CURLYM] = compare_left_tail;
5978	1		dispatch[TAIL][CURLYM] = compare_left_tail;
5979	1		dispatch[PLUS][CURLYM] = compare_plus_curly;
5980	1		dispatch[CURLY][CURLYM] = compare_curly_curly;
5981	1		dispatch[CURLYM][CURLYM] = compare_curly_curly;
5982	1		dispatch[CURLYX][CURLYM] = compare_curly_curly;
5983	1		dispatch[WHILEM][CURLYM] = compare_left_tail;
5984	1		dispatch[OPEN][CURLYM] = compare_left_open;
5985	1		dispatch[CLOSE][CURLYM] = compare_left_tail;
5986	1		dispatch[IFMATCH][CURLYM] = compare_after_assertion;
5987	1		dispatch[UNLESSM][CURLYM] = compare_after_assertion;
5988	1		dispatch[SUSPEND][CURLYM] = compare_suspend_curly;
5989	1		dispatch[MINMOD][CURLYM] = compare_left_tail;
5990	1		dispatch[OPTIMIZED][CURLYM] = compare_left_tail;
5991
5992	93	100	for (i = 0; i < REGNODE_MAX; ++i)
5993			{
5994	92		dispatch[i][CURLYX] = compare_right_curly;
5995			}
5996
5997	1		dispatch[SUCCEED][CURLYX] = compare_left_tail;
5998	1		dispatch[NOTHING][CURLYX] = compare_left_tail;
5999	1		dispatch[TAIL][CURLYX] = compare_left_tail;
6000	1		dispatch[PLUS][CURLYX] = compare_plus_curly;
6001	1		dispatch[CURLY][CURLYX] = compare_curly_curly;
6002	1		dispatch[CURLYM][CURLYX] = compare_curly_curly;
6003	1		dispatch[CURLYX][CURLYX] = compare_curly_curly;
6004	1		dispatch[WHILEM][CURLYX] = compare_left_tail;
6005	1		dispatch[OPEN][CURLYX] = compare_left_open;
6006	1		dispatch[CLOSE][CURLYX] = compare_left_tail;
6007	1		dispatch[IFMATCH][CURLYX] = compare_after_assertion;
6008	1		dispatch[UNLESSM][CURLYX] = compare_after_assertion;
6009	1		dispatch[SUSPEND][CURLYX] = compare_suspend_curly;
6010	1		dispatch[MINMOD][CURLYX] = compare_left_tail;
6011	1		dispatch[OPTIMIZED][CURLYX] = compare_left_tail;
6012
6013	93	100	for (i = 0; i < REGNODE_MAX; ++i)
6014			{
6015	92		dispatch[i][WHILEM] = compare_next;
6016			}
6017
6018	1		dispatch[SUCCEED][WHILEM] = compare_tails;
6019	1		dispatch[NOTHING][WHILEM] = compare_tails;
6020	1		dispatch[TAIL][WHILEM] = compare_tails;
6021	1		dispatch[WHILEM][WHILEM] = compare_tails;
6022	1		dispatch[CLOSE][WHILEM] = compare_tails;
6023	1		dispatch[MINMOD][WHILEM] = compare_tails;
6024	1		dispatch[OPTIMIZED][WHILEM] = compare_tails;
6025
6026	93	100	for (i = 0; i < REGNODE_MAX; ++i)
6027			{
6028	92		dispatch[i][OPEN] = compare_right_open;
6029			}
6030
6031	1		dispatch[OPEN][OPEN] = compare_open_open;
6032
6033	93	100	for (i = 0; i < REGNODE_MAX; ++i)
6034			{
6035	92		dispatch[i][CLOSE] = compare_next;
6036			}
6037
6038	1		dispatch[SUCCEED][CLOSE] = compare_tails;
6039	1		dispatch[NOTHING][CLOSE] = compare_tails;
6040	1		dispatch[TAIL][CLOSE] = compare_tails;
6041	1		dispatch[WHILEM][CLOSE] = compare_tails;
6042	1		dispatch[CLOSE][CLOSE] = compare_tails;
6043	1		dispatch[MINMOD][CLOSE] = compare_tails;
6044	1		dispatch[OPTIMIZED][CLOSE] = compare_tails;
6045
6046	1		dispatch[SUCCEED][IFMATCH] = compare_left_tail;
6047	1		dispatch[MBOL][IFMATCH] = compare_bol;
6048	1		dispatch[SBOL][IFMATCH] = compare_bol;
6049	1		dispatch[BOUND][IFMATCH] = compare_mismatch;
6050	1		dispatch[NBOUND][IFMATCH] = compare_mismatch;
6051	1		dispatch[REG_ANY][IFMATCH] = compare_mismatch;
6052	1		dispatch[SANY][IFMATCH] = compare_mismatch;
6053	1		dispatch[ANYOF][IFMATCH] = compare_mismatch;
6054	1		dispatch[ANYOFD][IFMATCH] = compare_mismatch;
6055			#ifdef RC_ANYOFM
6056			dispatch[ANYOFM][IFMATCH] = compare_mismatch;
6057			#endif
6058			#ifdef RC_NANYOFM
6059			dispatch[NANYOFM][IFMATCH] = compare_mismatch;
6060			#endif
6061	1		dispatch[POSIXD][IFMATCH] = compare_mismatch;
6062	1		dispatch[POSIXU][IFMATCH] = compare_mismatch;
6063	1		dispatch[POSIXA][IFMATCH] = compare_mismatch;
6064	1		dispatch[NPOSIXD][IFMATCH] = compare_mismatch;
6065	1		dispatch[NPOSIXU][IFMATCH] = compare_mismatch;
6066	1		dispatch[NPOSIXA][IFMATCH] = compare_mismatch;
6067	1		dispatch[BRANCH][IFMATCH] = compare_mismatch;
6068	1		dispatch[EXACT][IFMATCH] = compare_mismatch;
6069	1		dispatch[EXACTF][IFMATCH] = compare_mismatch;
6070	1		dispatch[EXACTFU][IFMATCH] = compare_mismatch;
6071	1		dispatch[NOTHING][IFMATCH] = compare_left_tail;
6072	1		dispatch[TAIL][IFMATCH] = compare_left_tail;
6073	1		dispatch[STAR][IFMATCH] = compare_mismatch;
6074	1		dispatch[PLUS][IFMATCH] = compare_mismatch;
6075	1		dispatch[CURLY][IFMATCH] = compare_mismatch;
6076	1		dispatch[CURLYM][IFMATCH] = compare_mismatch;
6077	1		dispatch[CURLYX][IFMATCH] = compare_mismatch;
6078	1		dispatch[WHILEM][IFMATCH] = compare_left_tail;
6079	1		dispatch[OPEN][IFMATCH] = compare_left_open;
6080	1		dispatch[CLOSE][IFMATCH] = compare_left_tail;
6081	1		dispatch[IFMATCH][IFMATCH] = compare_positive_assertions;
6082	1		dispatch[UNLESSM][IFMATCH] = compare_mismatch;
6083	1		dispatch[MINMOD][IFMATCH] = compare_left_tail;
6084	1		dispatch[LNBREAK][IFMATCH] = compare_mismatch;
6085	1		dispatch[OPTIMIZED][IFMATCH] = compare_left_tail;
6086
6087	1		dispatch[SUCCEED][UNLESSM] = compare_left_tail;
6088	1		dispatch[MBOL][UNLESSM] = compare_bol;
6089	1		dispatch[SBOL][UNLESSM] = compare_bol;
6090	1		dispatch[BOUND][UNLESSM] = compare_mismatch;
6091	1		dispatch[NBOUND][UNLESSM] = compare_mismatch;
6092	1		dispatch[REG_ANY][UNLESSM] = compare_mismatch;
6093	1		dispatch[SANY][UNLESSM] = compare_mismatch;
6094	1		dispatch[ANYOF][UNLESSM] = compare_mismatch;
6095	1		dispatch[ANYOFD][UNLESSM] = compare_mismatch;
6096			#ifdef RC_ANYOFM
6097			dispatch[ANYOFM][UNLESSM] = compare_mismatch;
6098			#endif
6099			#ifdef RC_NANYOFM
6100			dispatch[NANYOFM][UNLESSM] = compare_mismatch;
6101			#endif
6102	1		dispatch[POSIXD][UNLESSM] = compare_mismatch;
6103	1		dispatch[POSIXU][UNLESSM] = compare_mismatch;
6104	1		dispatch[POSIXA][UNLESSM] = compare_mismatch;
6105	1		dispatch[NPOSIXD][UNLESSM] = compare_mismatch;
6106	1		dispatch[NPOSIXU][UNLESSM] = compare_mismatch;
6107	1		dispatch[NPOSIXA][UNLESSM] = compare_mismatch;
6108	1		dispatch[BRANCH][UNLESSM] = compare_mismatch;
6109	1		dispatch[EXACT][UNLESSM] = compare_mismatch;
6110	1		dispatch[EXACTF][UNLESSM] = compare_mismatch;
6111	1		dispatch[EXACTFU][UNLESSM] = compare_mismatch;
6112	1		dispatch[NOTHING][UNLESSM] = compare_left_tail;
6113	1		dispatch[TAIL][UNLESSM] = compare_left_tail;
6114	1		dispatch[STAR][UNLESSM] = compare_mismatch;
6115	1		dispatch[PLUS][UNLESSM] = compare_mismatch;
6116	1		dispatch[CURLY][UNLESSM] = compare_mismatch;
6117	1		dispatch[CURLYM][UNLESSM] = compare_mismatch;
6118	1		dispatch[CURLYX][UNLESSM] = compare_mismatch;
6119	1		dispatch[WHILEM][UNLESSM] = compare_left_tail;
6120	1		dispatch[OPEN][UNLESSM] = compare_left_open;
6121	1		dispatch[CLOSE][UNLESSM] = compare_left_tail;
6122	1		dispatch[IFMATCH][UNLESSM] = compare_mismatch;
6123	1		dispatch[UNLESSM][UNLESSM] = compare_negative_assertions;
6124	1		dispatch[MINMOD][UNLESSM] = compare_left_tail;
6125	1		dispatch[LNBREAK][UNLESSM] = compare_mismatch;
6126	1		dispatch[OPTIMIZED][UNLESSM] = compare_left_tail;
6127
6128	1		dispatch[SUSPEND][SUSPEND] = compare_subexpressions;
6129
6130	93	100	for (i = 0; i < REGNODE_MAX; ++i)
6131			{
6132	92		dispatch[i][MINMOD] = compare_next;
6133			}
6134
6135	1		dispatch[SUCCEED][MINMOD] = compare_tails;
6136	1		dispatch[NOTHING][MINMOD] = compare_tails;
6137	1		dispatch[TAIL][MINMOD] = compare_tails;
6138	1		dispatch[WHILEM][MINMOD] = compare_tails;
6139	1		dispatch[CLOSE][MINMOD] = compare_tails;
6140	1		dispatch[MINMOD][MINMOD] = compare_tails;
6141	1		dispatch[OPTIMIZED][MINMOD] = compare_tails;
6142
6143	1		dispatch[SUCCEED][LNBREAK] = compare_left_tail;
6144	1		dispatch[SBOL][LNBREAK] = compare_bol;
6145	1		dispatch[MBOL][LNBREAK] = compare_bol;
6146	1		dispatch[BOUND][LNBREAK] = compare_mismatch;
6147	1		dispatch[NBOUND][LNBREAK] = compare_mismatch;
6148	1		dispatch[REG_ANY][LNBREAK] = compare_mismatch;
6149	1		dispatch[SANY][LNBREAK] = compare_mismatch;
6150	1		dispatch[ANYOF][LNBREAK] = compare_anyof_lnbreak;
6151	1		dispatch[ANYOFD][LNBREAK] = compare_anyof_lnbreak;
6152			#ifdef RC_ANYOFM
6153			dispatch[ANYOFM][LNBREAK] = compare_mismatch;
6154			#endif
6155			#ifdef RC_NANYOFM
6156			dispatch[NANYOFM][LNBREAK] = compare_mismatch;
6157			#endif
6158	1		dispatch[POSIXD][LNBREAK] = compare_posix_lnbreak;
6159	1		dispatch[POSIXU][LNBREAK] = compare_posix_lnbreak;
6160	1		dispatch[POSIXA][LNBREAK] = compare_posix_lnbreak;
6161	1		dispatch[NPOSIXD][LNBREAK] = compare_mismatch;
6162	1		dispatch[NPOSIXU][LNBREAK] = compare_mismatch;
6163	1		dispatch[NPOSIXA][LNBREAK] = compare_mismatch;
6164	1		dispatch[BRANCH][LNBREAK] = compare_left_branch;
6165	1		dispatch[EXACT][LNBREAK] = compare_exact_lnbreak;
6166	1		dispatch[EXACTFU][LNBREAK] = compare_exact_lnbreak;
6167	1		dispatch[NOTHING][LNBREAK] = compare_left_tail;
6168	1		dispatch[TAIL][LNBREAK] = compare_left_tail;
6169	1		dispatch[STAR][LNBREAK] = compare_mismatch;
6170	1		dispatch[PLUS][LNBREAK] = compare_left_plus;
6171	1		dispatch[CURLY][LNBREAK] = compare_left_curly;
6172	1		dispatch[CURLYM][LNBREAK] = compare_left_curly;
6173	1		dispatch[CURLYX][LNBREAK] = compare_left_curly;
6174	1		dispatch[WHILEM][LNBREAK] = compare_left_tail;
6175	1		dispatch[OPEN][LNBREAK] = compare_left_open;
6176	1		dispatch[CLOSE][LNBREAK] = compare_left_tail;
6177	1		dispatch[IFMATCH][LNBREAK] = compare_after_assertion;
6178	1		dispatch[UNLESSM][LNBREAK] = compare_after_assertion;
6179	1		dispatch[MINMOD][LNBREAK] = compare_left_tail;
6180	1		dispatch[LNBREAK][LNBREAK] = compare_tails;
6181
6182	93	100	for (i = 0; i < REGNODE_MAX; ++i)
6183			{
6184	92		dispatch[i][OPTIMIZED] = compare_next;
6185			}
6186
6187	1		dispatch[SUCCEED][OPTIMIZED] = compare_tails;
6188	1		dispatch[NOTHING][OPTIMIZED] = compare_tails;
6189	1		dispatch[TAIL][OPTIMIZED] = compare_tails;
6190	1		dispatch[WHILEM][OPTIMIZED] = compare_tails;
6191	1		dispatch[CLOSE][OPTIMIZED] = compare_tails;
6192	1		dispatch[MINMOD][OPTIMIZED] = compare_tails;
6193	1		dispatch[OPTIMIZED][OPTIMIZED] = compare_tails;
6194	1		}