File Coverage

engine.c

Criterion	Covered	Total	%
statement	2104	2386	88.1
branch	629	906	69.4
condition			n/a
subroutine			n/a
pod			n/a
total	2733	3292	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	12740		static void init_bit_flag(BitFlag *bf, int c)
275			{
276			assert(c >= 0);
277
278	12740		bf->offs = c / 8;
279	12740		bf->mask = 1 << (c % 8);
280	12740		}
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	2892		static int get_size(regnode *rn)
1079			{
1080			int offs;
1081	2892		regnode *e = rn;
1082
1083	6998	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	2892		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	16097		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	16097	100	offs = GET_OFFSET(a->rn);
1338	16097	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	16097	100	if (++(a->spent) >= a->rn->flags)
1354			{
1355	10771		a->spent = 0;
1356	10771		a->rn += offs;
1357			}
1358
1359	16097		return 1;
1360			}
1361
1362	18812		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	18812	100	offs = GET_OFFSET(a->rn);
1372	18812	50	if (offs <= 0)
1373			{
1374	0		return -1;
1375			}
1376
1377	18812		a->rn += offs;
1378	18812		return 1;
1379			}
1380
1381	33096		static int bump_with_check(Arrow *a)
1382			{
1383	33096	100	if (a->rn->type == END)
1384			{
1385	73		return 0;
1386			}
1387	33023	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	16097		return bump_exact(a);
1394			}
1395			else
1396			{
1397	16926		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	6481		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	6481	100	if (anchored)
1462			{
1463	672		return 0;
1464			}
1465			else
1466			{
1467	5809		rv = bump_with_check(a1);
1468	5809	100	if (rv <= 0)
1469			{
1470	73		return rv;
1471			}
1472
1473	5736		return compare(0, a1, a2);
1474			}
1475			}
1476
1477	13144		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	13144		tail1 = *a1;
1484	13144		rv = bump_with_check(&tail1);
1485	13144	50	if (rv <= 0)
1486			{
1487	0		return rv;
1488			}
1489
1490	13144		tail2 = *a2;
1491	13144		rv = bump_with_check(&tail2);
1492	13144	50	if (rv <= 0)
1493			{
1494	0		return rv;
1495			}
1496
1497	13144		rv = compare(1, &tail1, &tail2);
1498	13144	50	if (rv < 0)
1499			{
1500	0		return rv;
1501			}
1502
1503	13144	100	if (!rv)
1504			{
1505	257		rv = compare_mismatch(anchored, a1, a2);
1506			}
1507			else
1508			{
1509	12887		*a1 = tail1;
1510	12887		*a2 = tail2;
1511			}
1512
1513	13144		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	47776		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	47776		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	47776		loc = bitmap[i];
1775			#endif
1776	47776	100	if (p->flags & ANYOF_INVERT)
1777			{
1778	234		loc = ~loc;
1779			}
1780
1781	47776		return loc;
1782			}
1783
1784	955		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	26952	100	for (i = 0; i < ANYOF_BITMAP_SIZE; ++i)
1797			{
1798	26160	100	loc1 = b1 ? b1[i] : get_bitmap_byte(a1->rn, i);
1799	26160	100	loc2 = b2 ? b2[i] : get_bitmap_byte(a2->rn, i);
1800	26160	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	792		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	513		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	513		extra_left = ANYOF_FLAGS(a1->rn) &
1976			ANYOF_SHARED_d_UPPER_LATIN1_UTF8_STRING_MATCHES_non_d_RUNTIME_USER_PROP;
1977	513	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	422		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 == ANYOFM);
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	876		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	876		seq = GET_LITERAL(a1);
2518	876		init_bit_flag(&bf, (unsigned char)(*seq));
2519
2520	876	100	if (!(get_bitmap_byte(a2->rn, bf.offs) & bf.mask))
2521			{
2522	288		return compare_mismatch(anchored, a1, a2);
2523			}
2524
2525	876		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 == ANYOFM);
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	18		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	18	50	offs = GET_OFFSET(a1->rn);
3420	18	50	if (offs <= 0)
3421			{
3422	0		return -1;
3423			}
3424
3425	18		t1 = a1->rn + offs;
3426	18		sz = get_size(t1);
3427	18	50	if (sz < 0)
3428			{
3429	0		return sz;
3430			}
3431
3432	18		alt = (regnode )malloc(sizeof(regnode) (2 + sz));
3433	18	50	if (!alt)
3434			{
3435	0		rc_error = "Couldn't allocate memory for alternative copy";
3436	0		return -1;
3437			}
3438
3439	18		alt[0].flags = 1;
3440	18		alt[0].type = EXACT;
3441	18		alt[0].next_off = 2;
3442	18		memcpy(alt + 2, t1, sizeof(regnode) * sz);
3443
3444	18		left.origin = a1->origin;
3445	18		right.origin = a2->origin;
3446	18		right.rn = 0;
3447
3448	574	100	for (i = 0; i < ANYOF_BITMAP_SIZE; ++i)
3449			{
3450	557		power = 1;
3451	5008	100	for (j = 0; j < 8; ++j)
3452			{
3453	4452	50	loc = b1 ? b1[i] : get_bitmap_byte(a1->rn, i);
3454	4452	100	if (loc & power)
3455			{
3456	465		alt[1].flags = 8 * i + j;
3457	465		left.rn = alt;
3458	465		left.spent = 0;
3459
3460	465		right.rn = a2->rn;
3461	465		right.spent = a2->spent;
3462
3463	465		rv = compare_right_branch(anchored, &left, &right);
3464	465	50	if (rv < 0)
3465			{
3466	0		free(alt);
3467	0		return rv;
3468			}
3469
3470	465	100	if (!rv)
3471			{
3472	1		free(alt);
3473	1		return compare_mismatch(anchored, a1, a2);
3474			}
3475			}
3476
3477	4451		power *= 2;
3478			}
3479			}
3480
3481	17		free(alt);
3482
3483	17	50	if (!right.rn)
3484			{
3485	0		rc_error = "Empty mask not supported";
3486	0		return -1;
3487			}
3488
3489	17		a1->rn = t1 + sz - 1;
3490			assert(a1->rn->type == END);
3491	17		a1->spent = 0;
3492
3493	17		a2->rn = right.rn;
3494	17		a2->spent = right.spent;
3495
3496	18		return 1;
3497			}
3498
3499	18		static int compare_anyof_branch(int anchored, Arrow a1, Arrow a2)
3500			{
3501			assert((a1->rn->type == ANYOF) \|\| (a1->rn->type == ANYOFD));
3502			assert(a2->rn->type == BRANCH);
3503
3504	18		return compare_set(anchored, a1, a2, 0);
3505			}
3506
3507			#ifdef RC_ANYOFM
3508			static int compare_anyofm_branch(int anchored, Arrow a1, Arrow a2)
3509			{
3510			unsigned char left[ANYOF_BITMAP_SIZE];
3511
3512			assert(a1->rn->type == ANYOFM);
3513			assert(a2->rn->type == BRANCH);
3514
3515			if (!convert_anyofm_to_bitmap(a1, left))
3516			{
3517			return compare_mismatch(anchored, a1, a2);
3518			}
3519
3520			return compare_set(anchored, a1, a2, left);
3521			}
3522			#endif
3523
3524	1691		static int compare_right_branch(int anchored, Arrow a1, Arrow a2)
3525			{
3526			int rv;
3527			regnode *p2;
3528			Arrow left, right;
3529
3530			/* fprintf(stderr, "enter compare_right_branch\n"); */
3531
3532			assert(a2->rn->type == BRANCH);
3533
3534			/* origins stay the same throughout the cycle */
3535	1691		left.origin = a1->origin;
3536	1691		right.origin = a2->origin;
3537	1691		p2 = a2->rn;
3538	1691		rv = 0;
3539	4264	100	while ((p2->type == BRANCH) && !rv)
		100
3540			{
3541			/* fprintf(stderr, "p2->type = %d\n", p2->type); */
3542
3543	2573		left.rn = a1->rn;
3544	2573		left.spent = a1->spent;
3545
3546	2573	50	if (p2->next_off == 0)
3547			{
3548	0		rc_error = "Branch with offset zero";
3549	0		return -1;
3550			}
3551
3552	2573		right.rn = p2 + 1;
3553	2573		right.spent = 0;
3554
3555	2573		rv = compare(anchored, &left, &right);
3556			/* fprintf(stderr, "got %d\n", rv); */
3557
3558	2573		p2 += p2->next_off;
3559			}
3560
3561	1691	50	if (rv < 0)
3562			{
3563	0		return rv;
3564			}
3565
3566	1691	100	if (!rv)
3567			{
3568	132		return compare_mismatch(anchored, a1, a2);
3569			}
3570
3571	1559		a1->rn = left.rn;
3572	1559		a1->spent = left.spent;
3573
3574	1559		a2->rn = right.rn;
3575	1559		a2->spent = right.spent;
3576
3577	1691		return 1;
3578			}
3579
3580	413		static int compare_right_star(int anchored, Arrow a1, Arrow a2)
3581			{
3582			regnode *p2;
3583			Arrow left, right;
3584			int sz, rv, offs;
3585
3586			/* fprintf(stderr, "enter compare_right_star\n"); */
3587
3588	413		p2 = a2->rn;
3589			assert(p2->type == STAR);
3590
3591	413		sz = get_size(p2);
3592	413	50	if (sz < 0)
3593			{
3594	0		return sz;
3595			}
3596
3597	413		left.origin = a1->origin;
3598	413		left.rn = a1->rn;
3599	413		left.spent = a1->spent;
3600
3601	413	50	offs = GET_OFFSET(p2);
3602	413	50	if (offs <= 0)
3603			{
3604	0		return -1;
3605			}
3606
3607	413		right.origin = a2->origin;
3608	413		right.rn = p2 + offs;
3609	413		right.spent = 0;
3610
3611	413		rv = compare(anchored, &left, &right);
3612	413	50	if (rv < 0)
3613			{
3614	0		return rv;
3615			}
3616
3617	413	100	if (rv == 0)
3618			{
3619	9		right.rn = p2 + 1;
3620	9		right.spent = 0;
3621
3622	9		rv = compare(anchored, a1, &right);
3623	9	50	if (rv < 0)
3624			{
3625	0		return rv;
3626			}
3627
3628	9	100	if (!rv)
3629			{
3630	4		return compare_mismatch(anchored, a1, a2);
3631			}
3632
3633	5		right.rn = p2;
3634	5		right.spent = 0;
3635
3636	5	50	if (!anchored)
3637			{
3638	0		rv = compare_right_star(1, a1, &right);
3639			}
3640			}
3641
3642	409	50	if (rv <= 0)
3643			{
3644	0		return rv;
3645			}
3646
3647	409		a2->rn += sz - 1;
3648			assert(a2->rn->type == END);
3649	409		a2->spent = 0;
3650
3651	413		return rv;
3652			}
3653
3654	136		static int compare_plus_plus(int anchored, Arrow a1, Arrow a2)
3655			{
3656			regnode p1, p2;
3657			Arrow left, right;
3658			int rv, offs;
3659
3660	136		p1 = a1->rn;
3661			assert(p1->type == PLUS);
3662	136		p2 = a2->rn;
3663			assert(p2->type == PLUS);
3664
3665	136		left.origin = a1->origin;
3666	136		left.rn = p1 + 1;
3667	136		left.spent = 0;
3668
3669	136		right.origin = a2->origin;
3670	136		right.rn = p2 + 1;
3671	136		right.spent = 0;
3672
3673	136		rv = compare(1, &left, &right);
3674	136	100	if (rv)
3675			{
3676	123		return rv;
3677			}
3678
3679	13	50	offs = GET_OFFSET(p1);
3680			/* fprintf(stderr, "offs = %d\n", offs); */
3681	13	50	if (offs <= 0)
3682			{
3683	0		return -1;
3684			}
3685
3686	13		left.origin = a1->origin;
3687	13		left.rn = p1 + offs;
3688	13		left.spent = 0;
3689	136		return compare(1, &left, a2);
3690			}
3691
3692	156		static int compare_repeat_star(int anchored, Arrow a1, Arrow a2)
3693			{
3694			regnode p1, p2;
3695			Arrow left, right;
3696			int rv, offs;
3697
3698	156		p1 = a1->rn;
3699			assert((p1->type == PLUS) \|\| (p1->type == STAR));
3700	156		p2 = a2->rn;
3701			assert(p2->type == STAR);
3702			/* fprintf(stderr, "enter compare_repeat_star(%d, %d, %d)\n",
3703			anchored, p1->type, p2->type); */
3704
3705	156		left.origin = a1->origin;
3706	156		left.rn = p1 + 1;
3707	156		left.spent = 0;
3708
3709	156		right.origin = a2->origin;
3710	156		right.rn = p2 + 1;
3711	156		right.spent = 0;
3712
3713	156		rv = compare(1, &left, &right);
3714			/* fprintf(stderr, "inclusive compare returned %d\n", rv); */
3715	156	100	if (rv)
3716			{
3717	140		return rv;
3718			}
3719
3720	16	50	offs = GET_OFFSET(p2);
3721			/* fprintf(stderr, "offs = %d\n", offs); */
3722	16	50	if (offs <= 0)
3723			{
3724	0		return -1;
3725			}
3726
3727	16		right.origin = a2->origin;
3728	16		right.rn = p2 + offs;
3729	16		right.spent = 0;
3730	156		return compare(1, &left, &right);
3731			}
3732
3733	310		static int compare_right_curly_from_zero(int anchored, Arrow a1, Arrow a2)
3734			{
3735			regnode p2, alt;
3736			CurlyCount *cnt;
3737			#ifndef RC_UNSIGNED_COUNT
3738			CurlyCount n;
3739			#endif
3740			Arrow left, right;
3741			int sz, rv, offs;
3742
3743	310		p2 = a2->rn;
3744
3745			#ifndef RC_UNSIGNED_COUNT
3746	310		n = ((CurlyCount *)(p2 + 1))[1];
3747	310	50	if (n <= 0)
3748			{
3749	0		rc_error = "Curly must have positive maximum";
3750	0		return -1;
3751			}
3752			#endif
3753
3754	310		sz = get_size(p2);
3755	310	50	if (sz < 0)
3756			{
3757	0		return sz;
3758			}
3759
3760	310		left.origin = a1->origin;
3761	310		left.rn = a1->rn;
3762	310		left.spent = a1->spent;
3763
3764	310	50	offs = GET_OFFSET(p2);
3765	310	50	if (offs <= 0)
3766			{
3767	0		return -1;
3768			}
3769
3770	310		right.origin = a2->origin;
3771	310		right.rn = p2 + offs;
3772	310		right.spent = 0;
3773
3774	310		rv = compare(anchored, &left, &right);
3775	310	50	if (rv < 0)
3776			{
3777	0		return rv;
3778			}
3779
3780	310	100	if (rv == 0)
3781			{
3782	4		alt = alloc_alt(p2, sz);
3783	4	50	if (!alt)
3784			{
3785	0		return -1;
3786			}
3787
3788	4		right.rn = alt + 2;
3789	4		right.spent = 0;
3790
3791	4		rv = compare(anchored, a1, &right);
3792	4	50	if (rv < 0)
3793			{
3794	0		free(alt);
3795	0		return rv;
3796			}
3797
3798	4	100	if (!rv)
3799			{
3800	2		free(alt);
3801	2		return compare_mismatch(anchored, a1, a2);
3802			}
3803
3804	2		cnt = (CurlyCount *)(alt + 1);
3805	2	50	if (cnt[1] < INFINITE_COUNT)
3806			{
3807	2		--cnt[1];
3808			}
3809
3810	2	100	if ((cnt[1] > 0) && !anchored)
		50
3811			{
3812	0		right.rn = alt;
3813	0		right.spent = 0;
3814
3815	0		rv = compare_right_curly_from_zero(1, a1, &right);
3816			}
3817			else
3818			{
3819	2		rv = 1;
3820			}
3821
3822	2		free(alt);
3823			}
3824
3825	308	50	if (rv <= 0)
3826			{
3827	0		return rv;
3828			}
3829
3830	308		a2->rn += sz - 1;
3831			assert(a2->rn->type == END);
3832	308		a2->spent = 0;
3833
3834	310		return rv;
3835			}
3836
3837	505		static int compare_left_plus(int anchored, Arrow a1, Arrow a2)
3838			{
3839			regnode p1, alt, *q;
3840			Arrow left, right;
3841			int sz, rv, offs, end_offs;
3842			unsigned char orig_type;
3843
3844	505		p1 = a1->rn;
3845			assert(p1->type == PLUS);
3846
3847	505		sz = get_size(p1);
3848	505	50	if (sz < 0)
3849			{
3850	0		return -1;
3851			}
3852
3853	505	50	if (sz < 2)
3854			{
3855	0		rc_error = "Left plus offset too small";
3856	0		return -1;
3857			}
3858
3859	505		alt = alloc_alt(p1 + 1, sz - 1);
3860	505	50	if (!alt)
3861			{
3862	0		return -1;
3863			}
3864
3865	505	100	if (anchored)
3866			{
3867	14		offs = get_jump_offset(p1);
3868	14	50	if (offs <= 0)
3869			{
3870	0		return -1;
3871			}
3872
3873	14		q = p1 + offs;
3874	14	100	if (q->type != END)
3875			{
3876			/* repeat with a tail after it can be more strict than a
3877			fixed-length match only if the tail is at least as
3878			strict as the repeated regexp */
3879	6		left.origin = a1->origin;
3880	6		left.rn = q;
3881	6		left.spent = 0;
3882
3883	6		end_offs = offs - 1;
3884	6		orig_type = alt[end_offs].type;
3885	6		alt[end_offs].type = END;
3886
3887	6		right.origin = a2->origin;
3888	6		right.rn = alt;
3889	6		right.spent = 0;
3890
3891			/* fprintf(stderr, "comparing %d to %d\n", left.rn->type,
3892			right.rn->type); */
3893	6		rv = compare(1, &left, &right);
3894			/* fprintf(stderr, "compare returned %d\n", rv); */
3895	6	100	if (rv <= 0)
3896			{
3897	4		free(alt);
3898	4		return rv;
3899			}
3900
3901	2		alt[end_offs].type = orig_type;
3902			}
3903			}
3904
3905	501		left.origin = a1->origin;
3906	501		left.rn = alt;
3907	501		left.spent = 0;
3908	501		rv = compare(anchored, &left, a2);
3909	501		free(alt);
3910	505		return rv;
3911			}
3912
3913	275		static int compare_right_plus(int anchored, Arrow a1, Arrow a2)
3914			{
3915			regnode *p2;
3916			Arrow right;
3917			int sz, rv;
3918
3919	275		p2 = a2->rn;
3920			assert(p2->type == PLUS);
3921
3922			/* fprintf(stderr, "enter compare_right_plus\n"); */
3923
3924	275		sz = get_size(p2);
3925	275	50	if (sz < 0)
3926			{
3927	0		return -1;
3928			}
3929
3930	275	50	if (sz < 2)
3931			{
3932	0		rc_error = "Plus offset too small";
3933	0		return -1;
3934			}
3935
3936			/* fprintf(stderr, "sz = %d\n", sz); */
3937
3938	275		right.origin = a2->origin;
3939	275		right.rn = p2 + 1;
3940	275		right.spent = 0;
3941
3942	275		rv = compare(anchored, a1, &right);
3943
3944	275	50	if (rv < 0)
3945			{
3946	0		return rv;
3947			}
3948
3949	275	100	if (!rv)
3950			{
3951	24		return compare_mismatch(anchored, a1, a2);
3952			}
3953
3954	251		a2->rn += sz - 1;
3955			assert(a2->rn->type == END);
3956	251		a2->spent = 0;
3957
3958	275		return rv;
3959			}
3960
3961	1257		static int compare_next(int anchored, Arrow a1, Arrow a2)
3962			{
3963	1257	50	if (bump_regular(a2) <= 0)
3964			{
3965	0		return -1;
3966			}
3967
3968	1257		return compare(anchored, a1, a2);
3969			}
3970
3971	21		static int compare_curly_plus(int anchored, Arrow a1, Arrow a2)
3972			{
3973			regnode p1, p2;
3974			Arrow left, right;
3975			CurlyCount *cnt;
3976
3977	21		p1 = a1->rn;
3978			assert((p1->type == CURLY) \|\| (p1->type == CURLYM) \|\|
3979			(p1->type == CURLYX));
3980	21		p2 = a2->rn;
3981			assert(p2->type == PLUS);
3982
3983	21		cnt = (CurlyCount *)(p1 + 1);
3984			#ifndef RC_UNSIGNED_COUNT
3985	21	50	if (cnt[0] < 0)
3986			{
3987	0		rc_error = "Left curly has negative minimum";
3988	0		return -1;
3989			}
3990			#endif
3991
3992	21	50	if (!cnt[0])
3993			{
3994	0		return compare_mismatch(anchored, a1, a2);
3995			}
3996
3997	21		left.origin = a1->origin;
3998	21		left.rn = p1 + 2;
3999	21		left.spent = 0;
4000
4001	21		right.origin = a2->origin;
4002	21		right.rn = p2 + 1;
4003	21		right.spent = 0;
4004
4005	21	100	if (cnt[0] > 1)
4006			{
4007	9		anchored = 1;
4008			}
4009
4010	21		return compare(anchored, &left, &right);
4011			}
4012
4013	30		static int compare_curly_star(int anchored, Arrow a1, Arrow a2)
4014			{
4015			regnode p1, p2;
4016			Arrow left, right;
4017			int rv;
4018
4019	30		p1 = a1->rn;
4020			assert((p1->type == CURLY) \|\| (p1->type == CURLYM) \|\|
4021			(p1->type == CURLYX));
4022	30		p2 = a2->rn;
4023			assert(p2->type == STAR);
4024
4025	30		left.origin = a1->origin;
4026	30		left.rn = p1 + 2;
4027	30		left.spent = 0;
4028
4029	30		right.origin = a2->origin;
4030	30		right.rn = p2 + 1;
4031	30		right.spent = 0;
4032
4033	30		rv = compare(1, &left, &right);
4034	30	100	if (!rv)
4035			{
4036	11		rv = compare_next(anchored, a1, a2);
4037			}
4038
4039	30		return rv;
4040			}
4041
4042	41		static int compare_plus_curly(int anchored, Arrow a1, Arrow a2)
4043			{
4044			regnode p1, p2, *e2;
4045			Arrow left, right;
4046			CurlyCount *cnt;
4047			int rv, offs;
4048
4049	41		p1 = a1->rn;
4050			assert(p1->type == PLUS);
4051	41		p2 = a2->rn;
4052			assert((p2->type == CURLY) \|\| (p2->type == CURLYM) \|\|
4053			(p2->type == CURLYX));
4054
4055	41		cnt = (CurlyCount *)(p2 + 1);
4056			#ifndef RC_UNSIGNED_COUNT
4057	41	50	if (cnt[0] < 0)
4058			{
4059	0		rc_error = "Negative minimum for curly";
4060	0		return -1;
4061			}
4062			#endif
4063
4064	41	100	if (cnt[0] > 1) /* FIXME: fails '(?:aa)+' => 'a{2,}' */
4065			{
4066	2		return compare_mismatch(anchored, a1, a2);
4067			}
4068
4069	39		left.origin = a1->origin;
4070	39		left.rn = p1 + 1;
4071	39		left.spent = 0;
4072
4073	39	100	if (cnt[1] != INFINITE_COUNT)
4074			{
4075	35		offs = get_jump_offset(p2);
4076	35	50	if (offs <= 0)
4077			{
4078	0		return -1;
4079			}
4080
4081	35		e2 = p2 + offs;
4082	35	50	if (e2->type != END)
4083			{
4084	0		return compare_mismatch(anchored, a1, a2);
4085			}
4086			}
4087
4088	39		right.origin = a2->origin;
4089	39		right.rn = p2 + 2;
4090	39		right.spent = 0;
4091
4092	39		rv = compare(anchored, &left, &right);
4093	41	50	return (!rv && !cnt[0]) ? compare_next(anchored, a1, a2) : rv;
		0
4094			}
4095
4096	11		static int compare_suspend_curly(int anchored, Arrow a1, Arrow a2)
4097			{
4098			assert(a1->rn->type == SUSPEND);
4099			assert(!a1->spent);
4100
4101	11		a1->rn += 2;
4102
4103	11		return compare(1, a1, a2);
4104			}
4105
4106	375		static void dec_curly_counts(CurlyCount *altcnt)
4107			{
4108	375		--altcnt[0];
4109	375	100	if (altcnt[1] < INFINITE_COUNT)
4110			{
4111	155		--altcnt[1];
4112			}
4113	375		}
4114
4115	634		static int compare_left_curly(int anchored, Arrow a1, Arrow a2)
4116			{
4117			regnode p1, alt, *q;
4118			Arrow left, right;
4119			int sz, rv, offs, end_offs;
4120			CurlyCount *cnt;
4121
4122			/* fprintf(stderr, "enter compare_left_curly(%d, %d, %d)\n", anchored,
4123			a1->rn->type, a2->rn->type); */
4124
4125	634		p1 = a1->rn;
4126			assert((p1->type == CURLY) \|\| (p1->type == CURLYM) \|\|
4127			(p1->type == CURLYX));
4128
4129	634		cnt = (CurlyCount *)(p1 + 1);
4130	634	100	if (!cnt[0])
4131			{
4132			/* fprintf(stderr, "curly from 0\n"); */
4133	8		return compare_mismatch(anchored, a1, a2);
4134			}
4135
4136	626		sz = get_size(p1);
4137	626	50	if (sz < 0)
4138			{
4139	0		return -1;
4140			}
4141
4142	626	50	if (sz < 3)
4143			{
4144	0		rc_error = "Left curly offset too small";
4145	0		return -1;
4146			}
4147
4148	626	100	if (cnt[0] > 1)
4149			{
4150			/* fprintf(stderr, "curly with non-trivial repeat count\n"); */
4151
4152	339	50	offs = GET_OFFSET(p1);
4153	339	50	if (offs < 0)
4154			{
4155	0		return -1;
4156			}
4157
4158	339	50	if (offs < 3)
4159			{
4160	0		rc_error = "Left curly offset is too small";
4161	0		return -1;
4162			}
4163
4164	339		alt = (regnode )malloc(sizeof(regnode) (offs - 2 + sz));
4165	339	50	if (!alt)
4166			{
4167	0		rc_error = "Could not allocate memory for unrolled curly";
4168	0		return -1;
4169			}
4170
4171	339		memcpy(alt, p1 + 2, (offs - 2) * sizeof(regnode));
4172	339		memcpy(alt + offs - 2, p1, sz * sizeof(regnode));
4173
4174	339		dec_curly_counts((CurlyCount *)(alt + offs - 1));
4175
4176	339		left.origin = a1->origin;
4177	339		left.rn = alt;
4178	339		left.spent = 0;
4179	339		rv = compare(1, &left, a2);
4180	339		free(alt);
4181	339		return rv;
4182			}
4183
4184	287	100	if (anchored && !((cnt[0] == 1) && (cnt[1] == 1)))
		50
		100
4185			{
4186			/* fprintf(stderr, "anchored curly with variable length\n"); */
4187
4188	7		alt = alloc_alt(p1 + 2, sz - 2);
4189	7	50	if (!alt)
4190			{
4191	0		return -1;
4192			}
4193
4194	7		offs = get_jump_offset(p1);
4195	7	50	if (offs <= 0)
4196			{
4197	0		return -1;
4198			}
4199
4200	7		q = p1 + offs;
4201	7	50	if (q->type != END)
4202			{
4203			/* repeat with a tail after it can be more strict than a
4204			fixed-length match only if the tail is at least as
4205			strict as the repeated regexp */
4206	0		left.origin = a1->origin;
4207	0		left.rn = q;
4208	0		left.spent = 0;
4209
4210	0		end_offs = offs - 1;
4211	0		alt[end_offs].type = END;
4212
4213	0		right.origin = a2->origin;
4214	0		right.rn = alt;
4215	0		right.spent = 0;
4216
4217			/* fprintf(stderr, "comparing %d to %d\n", left.rn->type,
4218			right.rn->type); */
4219	0		rv = compare(1, &left, &right);
4220	0		free(alt);
4221			/* fprintf(stderr, "compare returned %d\n", rv); */
4222	0	0	if (rv <= 0)
4223			{
4224	0		return rv;
4225			}
4226			}
4227			}
4228
4229	287		left.origin = a1->origin;
4230	287		left.rn = p1 + 2;
4231	287		left.spent = 0;
4232	634		return compare(anchored, &left, a2);
4233			}
4234
4235	475		static int compare_right_curly(int anchored, Arrow a1, Arrow a2)
4236			{
4237			regnode p2, alt;
4238			Arrow right;
4239			CurlyCount cnt, altcnt;
4240			int sz, rv, offs, nanch;
4241
4242			/* fprintf(stderr, "enter compare_right_curly(%d...: a1->spent = %d, a2->spent = %d\n", anchored, a1->spent, a2->spent); */
4243
4244	475		p2 = a2->rn;
4245
4246	475		cnt = (CurlyCount *)(p2 + 1);
4247			#ifndef RC_UNSIGNED_COUNT
4248	475	50	if (cnt[0] < 0)
4249			{
4250	0		rc_error = "Curly has negative minimum";
4251	0		return -1;
4252			}
4253			#endif
4254
4255			/* fprintf(stderr, "compare_right_curly: minimal repeat count = %d\n", cnt[0]); */
4256
4257	475		nanch = anchored;
4258
4259	475	100	if (cnt[0] > 0)
4260			{
4261			/* the repeated expression is mandatory: */
4262	165		sz = get_size(p2);
4263	165	50	if (sz < 0)
4264			{
4265	0		return sz;
4266			}
4267
4268	165	50	if (sz < 3)
4269			{
4270	0		rc_error = "Right curly offset too small";
4271	0		return -1;
4272			}
4273
4274	165		right.origin = a2->origin;
4275	165		right.rn = p2 + 2;
4276	165		right.spent = 0;
4277
4278	165		rv = compare(anchored, a1, &right);
4279			/* fprintf(stderr, "compare_right_curly: compare returned %d\n", rv); */
4280	165	50	if (rv < 0)
4281			{
4282	0		return rv;
4283			}
4284
4285	165	100	if (!rv)
4286			{
4287			/* ...or (if we aren't anchored yet) just do the left tail... */
4288	23		rv = compare_mismatch(anchored, a1, a2);
4289	23	50	if (rv)
4290			{
4291	0		return rv;
4292			}
4293
4294			/* ...or (last try) unroll the repeat (works for e.g.
4295			'abbc' vs. 'ab{2}c' */
4296	23	100	if (cnt[0] > 1)
4297			{
4298	15	50	offs = GET_OFFSET(p2);
4299	15	50	if (offs < 0)
4300			{
4301	0		return -1;
4302			}
4303
4304	15	50	if (offs < 3)
4305			{
4306	0		rc_error = "Left curly offset is too small";
4307	0		return -1;
4308			}
4309
4310	15		alt = (regnode )malloc(sizeof(regnode) (offs - 2 + sz));
4311	15	50	if (!alt)
4312			{
4313	0		rc_error = "Couldn't allocate memory for unrolled curly";
4314	0		return -1;
4315			}
4316
4317	15		memcpy(alt, p2 + 2, (offs - 2) * sizeof(regnode));
4318	15		memcpy(alt + offs - 2, p2, sz * sizeof(regnode));
4319
4320	15		dec_curly_counts((CurlyCount *)(alt + offs - 1));
4321
4322	15		right.origin = a2->origin;
4323	15		right.rn = alt;
4324	15		right.spent = 0;
4325
4326	15		rv = compare(anchored, a1, &right);
4327	15		free(alt);
4328	15		return rv;
4329			}
4330
4331	8		return 0;
4332			}
4333
4334	142	100	if (cnt[0] == 1)
4335			{
4336	81		return 1;
4337			}
4338
4339	61	100	if (a1->rn->type == END)
4340			{
4341			/* we presume the repeated argument matches something, which
4342			isn't guaranteed, but it is conservative */
4343	40		return 0;
4344			}
4345
4346			/* strictly speaking, matching one repeat didn't necessarily
4347			anchor the match, but we'll ignore such cases as
4348			pathological */
4349	21		nanch = 1;
4350
4351	21		alt = alloc_alt(p2, sz);
4352	21	50	if (!alt)
4353			{
4354	0		return -1;
4355			}
4356
4357	21		altcnt = (CurlyCount *)(alt + 1);
4358	21		dec_curly_counts(altcnt);
4359	21	50	if (altcnt[1] > 0)
4360			{
4361	21		right.origin = a2->origin;
4362	21		right.rn = alt;
4363	21		right.spent = 0;
4364
4365	21		rv = compare_right_curly(nanch, a1, &right);
4366			}
4367			else
4368			{
4369	0		rv = 1;
4370			}
4371
4372	21		free(alt);
4373
4374	21	100	if (rv <= 0)
4375			{
4376	2		return rv;
4377			}
4378
4379	19		a2->rn += sz - 1;
4380			assert(a2->rn->type == END);
4381	19		a2->spent = 0;
4382	19		return rv;
4383			}
4384
4385	475		return compare_right_curly_from_zero(nanch, a1, a2);
4386			}
4387
4388	342		static int compare_curly_curly(int anchored, Arrow a1, Arrow a2)
4389			{
4390			regnode p1, p2, *e2;
4391			Arrow left, right;
4392			CurlyCount cnt1, cnt2;
4393			int rv, offs;
4394
4395			/* fprintf(stderr, "enter compare_curly_curly(%d...)\n", anchored); */
4396
4397	342		p1 = a1->rn;
4398			assert((p1->type == CURLY) \|\| (p1->type == CURLYM) \|\|
4399			(p1->type == CURLYX));
4400	342		p2 = a2->rn;
4401			assert((p2->type == CURLY) \|\| (p2->type == CURLYM) \|\|
4402			(p2->type == CURLYX));
4403
4404	342		cnt1 = (CurlyCount *)(p1 + 1);
4405			#ifndef RC_UNSIGNED_COUNT
4406			/* fprintf(stderr, "cnt1 = %d\n", cnt1[0]); /
4407	342	50	if (cnt1[0] < 0)
4408			{
4409	0		rc_error = "Negative minimum for left curly";
4410	0		return -1;
4411			}
4412			#endif
4413
4414	342		cnt2 = (CurlyCount *)(p2 + 1);
4415			#ifndef RC_UNSIGNED_COUNT
4416			/* fprintf(stderr, "cnt2 = %d\n", cnt2[0]); /
4417	342	50	if (cnt2[0] < 0)
4418			{
4419	0		rc_error = "Negative minimum for right curly";
4420	0		return -1;
4421			}
4422			#endif
4423
4424	342	100	if (cnt2[0] > cnt1[0]) /* FIXME: fails '(?:aa){1,}' => 'a{2,}' */
4425			{
4426			/* fprintf(stderr, "curly mismatch\n"); */
4427	5		return compare_mismatch(anchored, a1, a2);
4428			}
4429
4430	337		left.origin = a1->origin;
4431	337		left.rn = p1 + 2;
4432	337		left.spent = 0;
4433
4434	337	100	if (cnt1[1] > cnt2[1])
4435			{
4436	36		offs = get_jump_offset(p2);
4437			/* fprintf(stderr, "offs = %d\n", offs); */
4438	36	50	if (offs <= 0)
4439			{
4440	0		return -1;
4441			}
4442
4443	36		e2 = p2 + offs;
4444			/* fprintf(stderr, "e2->type = %d\n", e2->type); */
4445	36	100	if (e2->type != END)
4446			{
4447	3		return compare_mismatch(anchored, a1, a2);
4448			}
4449			}
4450
4451	334		right.origin = a2->origin;
4452	334		right.rn = p2 + 2;
4453	334		right.spent = 0;
4454
4455			/* fprintf(stderr, "comparing tails\n"); */
4456
4457	334		rv = compare(anchored, &left, &right);
4458			/* fprintf(stderr, "tail compare returned %d\n", rv); */
4459	342	100	return (!rv && !cnt2[0]) ? compare_next(anchored, a1, a2) : rv;
		100
4460			}
4461
4462	119		static int compare_bound(int anchored, Arrow a1, Arrow a2,
4463			int move_left, unsigned char bitmap, char lookup,
4464			unsigned char *oktypes,
4465			unsigned char *regclasses, U32 regclasses_size)
4466			{
4467			Arrow left, right;
4468			unsigned char t;
4469			int i;
4470			char *seq;
4471
4472			assert((a2->rn->type == BOUND) \|\| (a2->rn->type == NBOUND));
4473
4474	119		left = *a1;
4475
4476	119	50	if (bump_with_check(&left) <= 0)
4477			{
4478	0		return -1;
4479			}
4480
4481	119		t = left.rn->type;
4482	119	50	if (t >= REGNODE_MAX)
4483			{
4484	0		rc_error = "Invalid node type";
4485	0		return -1;
4486			}
4487	119	100	else if (t == ANYOF)
4488			{
4489			/* fprintf(stderr, "next is bitmap; flags = 0x%x\n", left.rn->flags); */
4490
4491	1	50	if (left.rn->flags & ANYOF_MATCHES_ALL_ABOVE_BITMAP)
4492			{
4493	0		return compare_mismatch(anchored, a1, a2);
4494			}
4495
4496	33	100	for (i = 0; i < ANYOF_BITMAP_SIZE; ++i)
4497			{
4498	32	50	if (get_bitmap_byte(left.rn, i) & ~bitmap[i])
4499			{
4500	0		return compare_mismatch(anchored, a1, a2);
4501			}
4502			}
4503			}
4504	118	100	else if ((t == EXACT) \|\| (t == EXACTF) \|\| (t == EXACTFU))
		50
		100
4505			{
4506	87		seq = GET_LITERAL(&left);
4507	87	100	if (!lookup[(unsigned char)(*seq)])
4508			{
4509	43		return compare_mismatch(anchored, a1, a2);
4510			}
4511			}
4512	31	100	else if ((t == POSIXD) \|\| (t == NPOSIXD) \|\| (t == POSIXU) \|\| (t == NPOSIXU))
		50
		100
		50
4513	8		{
4514	8		U8 flags = left.rn->flags;
4515	8	50	if ((flags >= regclasses_size) \|\| !regclasses[flags])
		50
4516			{
4517	0		return compare_mismatch(anchored, a1, a2);
4518			}
4519			}
4520	23	100	else if (!oktypes[t])
4521			{
4522	17		return compare_mismatch(anchored, a1, a2);
4523			}
4524
4525	59		right = *a2;
4526	59	50	if (bump_with_check(&right) <= 0)
4527			{
4528	0		return -1;
4529			}
4530
4531	119	100	return move_left ? compare(1, &left, &right) :
4532			compare(anchored, a1, &right);
4533			}
4534
4535	8		static int compare_bol_word(int anchored, Arrow a1, Arrow a2)
4536			{
4537	8		return compare_bound(anchored, a1, a2, 1, word_bc.bitmap,
4538			word_bc.lookup, alphanumeric_classes,
4539			word_posix_regclasses, SIZEOF_ARRAY(word_posix_regclasses));
4540			}
4541
4542	2		static int compare_bol_nword(int anchored, Arrow a1, Arrow a2)
4543			{
4544	2		return compare_bound(anchored, a1, a2, 1, word_bc.nbitmap,
4545			word_bc.nlookup, non_alphanumeric_classes,
4546			non_word_posix_regclasses, SIZEOF_ARRAY(non_word_posix_regclasses));
4547			}
4548
4549	31		static int compare_next_word(int anchored, Arrow a1, Arrow a2)
4550			{
4551	31		return compare_bound(anchored, a1, a2, 0, word_bc.bitmap,
4552			word_bc.lookup, alphanumeric_classes,
4553			word_posix_regclasses, SIZEOF_ARRAY(word_posix_regclasses));
4554			}
4555
4556	78		static int compare_next_nword(int anchored, Arrow a1, Arrow a2)
4557			{
4558	78		return compare_bound(anchored, a1, a2, 0, word_bc.nbitmap,
4559			word_bc.nlookup, non_alphanumeric_classes,
4560			non_word_posix_regclasses, SIZEOF_ARRAY(non_word_posix_regclasses));
4561			}
4562
4563	6		static int compare_anyof_bounds(int anchored, Arrow a1, Arrow a2,
4564			unsigned char bitmap1, unsigned char bitmap2)
4565			{
4566			unsigned char loc;
4567			FCompare cmp[2];
4568			int i;
4569
4570	6		cmp[0] = compare_next_word;
4571	6		cmp[1] = compare_next_nword;
4572	179	100	for (i = 0; (i < ANYOF_BITMAP_SIZE) && (cmp[0] \|\| cmp[1]); ++i)
		100
		100
4573			{
4574	173	50	loc = bitmap1 ? bitmap1[i] : get_bitmap_byte(a1->rn, i);
4575
4576	173	100	if (loc & ~bitmap2[i])
4577			{
4578	13		cmp[0] = 0;
4579			}
4580
4581	173	100	if (loc & bitmap2[i])
4582			{
4583	4		cmp[1] = 0;
4584			}
4585			}
4586
4587	6	100	if (cmp[0] && cmp[1])
		50
4588			{
4589	0		rc_error = "Zero bitmap";
4590	0		return -1;
4591			}
4592
4593	10	100	for (i = 0; i < SIZEOF_ARRAY(cmp); ++i)
4594			{
4595	9	100	if (cmp[i])
4596			{
4597	5		return (cmp[i])(anchored, a1, a2);
4598			}
4599			}
4600
4601			/* if would be more elegant to use compare_mismatch as a sentinel
4602			in cmp, but VC 2003 then warns that this function might be
4603			missing a return... */
4604	6		return compare_mismatch(anchored, a1, a2);
4605			}
4606
4607	5		static int compare_anyof_bound(int anchored, Arrow a1, Arrow a2)
4608			{
4609			assert((a1->rn->type == ANYOF) \|\| (a1->rn->type == ANYOFD));
4610			assert(a2->rn->type == BOUND);
4611
4612	5	100	if (a1->rn->flags & ANYOF_MATCHES_ALL_ABOVE_BITMAP)
4613			{
4614	1		return compare_mismatch(anchored, a1, a2);
4615			}
4616
4617	4		return compare_anyof_bounds(anchored, a1, a2, 0, word_bc.nbitmap);
4618			}
4619
4620	3		static int compare_anyof_nbound(int anchored, Arrow a1, Arrow a2)
4621			{
4622			assert((a1->rn->type == ANYOF) \|\| (a1->rn->type == ANYOFD));
4623			assert(a2->rn->type == NBOUND);
4624
4625	3	100	if (a1->rn->flags & ANYOF_MATCHES_ALL_ABOVE_BITMAP)
4626			{
4627	1		return compare_mismatch(anchored, a1, a2);
4628			}
4629
4630	2		return compare_anyof_bounds(anchored, a1, a2, 0, word_bc.bitmap);
4631			}
4632
4633			#ifdef RC_ANYOFM
4634			static int compare_anyofm_bound(int anchored, Arrow a1, Arrow a2)
4635			{
4636			unsigned char left[ANYOF_BITMAP_SIZE];
4637
4638			assert(a1->rn->type == ANYOFM);
4639			assert(a2->rn->type == BOUND);
4640
4641			if (!convert_anyofm_to_bitmap(a1, left))
4642			{
4643			return compare_mismatch(anchored, a1, a2);
4644			}
4645
4646			return compare_anyof_bounds(anchored, a1, a2, left, word_bc.nbitmap);
4647			}
4648
4649			static int compare_anyofm_nbound(int anchored, Arrow a1, Arrow a2)
4650			{
4651			unsigned char left[ANYOF_BITMAP_SIZE];
4652
4653			assert(a1->rn->type == ANYOFM);
4654			assert(a2->rn->type == BOUND);
4655
4656			if (!convert_anyofm_to_bitmap(a1, left))
4657			{
4658			return compare_mismatch(anchored, a1, a2);
4659			}
4660
4661			return compare_anyof_bounds(anchored, a1, a2, left, word_bc.bitmap);
4662			}
4663			#endif
4664
4665	64		static int compare_exact_bound(int anchored, Arrow a1, Arrow a2)
4666			{
4667			char *seq;
4668			FCompare cmp;
4669
4670			assert((a1->rn->type == EXACT) \|\| (a1->rn->type == EXACTF) \|\|
4671			(a1->rn->type == EXACTFU));
4672			assert(a2->rn->type == BOUND);
4673
4674	64		seq = GET_LITERAL(a1);
4675
4676	128		cmp = word_bc.lookup[(unsigned char)(*seq)] ?
4677	64	100	compare_next_nword : compare_next_word;
4678	64		return cmp(anchored, a1, a2);
4679			}
4680
4681	17		static int compare_exact_nbound(int anchored, Arrow a1, Arrow a2)
4682			{
4683			char *seq;
4684			FCompare cmp;
4685
4686			assert((a1->rn->type == EXACT) \|\| (a1->rn->type == EXACTF) \|\|
4687			(a1->rn->type == EXACTFU));
4688			assert(a2->rn->type == NBOUND);
4689
4690	17		seq = GET_LITERAL(a1);
4691
4692	34		cmp = word_bc.lookup[(unsigned char)(*seq)] ?
4693	17	100	compare_next_word : compare_next_nword;
4694	17		return cmp(anchored, a1, a2);
4695			}
4696
4697	10		static int compare_posix_bound(int anchored, Arrow a1, Arrow a2)
4698			{
4699			assert((a1->rn->type == POSIXD) \|\| (a1->rn->type == POSIXU) \|\|
4700			(a1->rn->type == POSIXA));
4701			assert(a2->rn->type == BOUND);
4702
4703	10		U8 flags = a1->rn->flags;
4704	10	50	if ((flags >= SIZEOF_ARRAY(word_posix_regclasses)) \|\|
		50
4705	10	100	(flags >= SIZEOF_ARRAY(non_word_posix_regclasses)) \|\|
4706	5	50	(!word_posix_regclasses[flags] && !non_word_posix_regclasses[flags]))
4707			{
4708	0		return compare_mismatch(anchored, a1, a2);
4709			}
4710
4711			assert(!word_posix_regclasses[flags] \|\| !non_word_posix_regclasses[flags]);
4712
4713	20		FCompare cmp = word_posix_regclasses[flags] ?
4714	10	100	compare_next_nword : compare_next_word;
4715	10		return cmp(anchored, a1, a2);
4716			}
4717
4718	9		static int compare_posix_nbound(int anchored, Arrow a1, Arrow a2)
4719			{
4720			assert((a1->rn->type == POSIXD) \|\| (a1->rn->type == POSIXU) \|\|
4721			(a1->rn->type == POSIXA));
4722			assert(a2->rn->type == NBOUND);
4723
4724	9		U8 flags = a1->rn->flags;
4725	9	50	if ((flags >= SIZEOF_ARRAY(word_posix_regclasses)) \|\|
		50
4726	9	100	(flags >= SIZEOF_ARRAY(non_word_posix_regclasses)) \|\|
4727	4	50	(!word_posix_regclasses[flags] && !non_word_posix_regclasses[flags]))
4728			{
4729	0		return compare_mismatch(anchored, a1, a2);
4730			}
4731
4732			assert(!word_posix_regclasses[flags] \|\| !non_word_posix_regclasses[flags]);
4733
4734	18		FCompare cmp = word_posix_regclasses[flags] ?
4735	9	100	compare_next_word : compare_next_nword;
4736	9		return cmp(anchored, a1, a2);
4737			}
4738
4739	5		static int compare_negative_posix_word_bound(int anchored, Arrow a1, Arrow a2)
4740			{
4741			assert((a1->rn->type == NPOSIXD) \|\| (a1->rn->type == NPOSIXU) \|\|
4742			(a1->rn->type == NPOSIXA));
4743			assert(a2->rn->type == BOUND);
4744
4745			/* we could accept _CC_ALPHANUMERIC as well but let's postpone it
4746			until we see the need */
4747	5	100	if (a1->rn->flags != _CC_WORDCHAR)
4748			{
4749	3		return compare_mismatch(anchored, a1, a2);
4750			}
4751
4752	2		return compare_next_word(anchored, a1, a2);
4753			}
4754
4755	9		static int compare_negative_posix_word_nbound(int anchored, Arrow a1, Arrow a2)
4756			{
4757			assert((a1->rn->type == NPOSIXD) \|\| (a1->rn->type == NPOSIXU) \|\|
4758			(a1->rn->type == NPOSIXA));
4759			assert(a2->rn->type == NBOUND);
4760
4761			/* we could accept _CC_ALPHANUMERIC as well but let's postpone it
4762			until we see the need */
4763	9	100	if (a1->rn->flags != _CC_WORDCHAR)
4764			{
4765	7		return compare_mismatch(anchored, a1, a2);
4766			}
4767
4768	2		return compare_next_nword(anchored, a1, a2);
4769			}
4770
4771	50		static int compare_open_open(int anchored, Arrow a1, Arrow a2)
4772			{
4773	50		return compare_tails(anchored, a1, a2);
4774			}
4775
4776	220		static int compare_left_open(int anchored, Arrow a1, Arrow a2)
4777			{
4778	220		return compare_left_tail(anchored, a1, a2);
4779			}
4780
4781	209		static int compare_right_open(int anchored, Arrow a1, Arrow a2)
4782			{
4783	209		return compare_next(anchored, a1, a2);
4784			}
4785
4786	10159		static int success(int anchored, Arrow a1, Arrow a2)
4787			{
4788	10159		return 1;
4789			}
4790
4791			/* #define DEBUG_dump */
4792
4793	9063		int rc_compare(REGEXP pt1, REGEXP pt2)
4794			{
4795			Arrow a1, a2;
4796			regnode p1, p2;
4797			#ifdef DEBUG_dump
4798			unsigned char *p;
4799			int i;
4800			#endif
4801
4802	9063		a1.origin = SvANY(pt1);
4803	9063		a2.origin = SvANY(pt2);
4804
4805	9063	100	if ((get_forced_semantics(pt1) \| get_forced_semantics(pt2)) == FORCED_MISMATCH)
4806			{
4807	7		return 0;
4808			}
4809
4810	9056		p1 = find_internal(a1.origin);
4811	9056	50	if (!p1)
4812			{
4813	0		return -1;
4814			}
4815
4816	9056		p2 = find_internal(a2.origin);
4817	9056	50	if (!p2)
4818			{
4819	0		return -1;
4820			}
4821
4822			#ifdef DEBUG_dump
4823			p = (unsigned char *)p1;
4824			for (i = 1; i <= 64; ++i)
4825			{
4826			fprintf(stderr, " %02x", (int)p[i - 1]);
4827			if (!(i % 4))
4828			{
4829			fprintf(stderr, "\n");
4830			}
4831			}
4832
4833			fprintf(stderr, "\n\n");
4834
4835			p = (unsigned char *)p2;
4836			for (i = 1; i <= 64; ++i)
4837			{
4838			fprintf(stderr, " %02x", (int)p[i - 1]);
4839			if (!(i % 4))
4840			{
4841			fprintf(stderr, "\n");
4842			}
4843			}
4844
4845			fprintf(stderr, "\n\n");
4846			#endif
4847
4848	9056		a1.rn = p1;
4849	9056		a1.spent = 0;
4850	9056		a2.rn = p2;
4851	9056		a2.spent = 0;
4852
4853	9063		return compare(0, &a1, &a2);
4854			}
4855
4856	38246		static int compare(int anchored, Arrow a1, Arrow a2)
4857			{
4858			FCompare cmp;
4859
4860			/* fprintf(stderr, "enter compare(%d, %d, %d)\n", anchored,
4861			a1->rn->type, a2->rn->type); */
4862
4863	38246	50	if ((a1->rn->type >= REGNODE_MAX) \|\| (a2->rn->type >= REGNODE_MAX))
		50
4864			{
4865	0		rc_error = "Invalid regexp node type";
4866	0		return -1;
4867			}
4868
4869	38246		cmp = dispatch[a1->rn->type][a2->rn->type];
4870	38246	100	if (!cmp)
4871			{
4872			/* fprintf(stderr, "no comparator\n"); */
4873	933		return 0;
4874			}
4875
4876	37313		return cmp(anchored, a1, a2);
4877			}
4878
4879	1		void rc_init()
4880			{
4881			int i, wstart;
4882
4883			/* could have used compile-time assertion, but why bother
4884			making it compatible... */
4885			assert(ANYOF_BITMAP_SIZE == 32);
4886
4887	1		init_forced_byte();
4888
4889	1		init_byte_class(&whitespace, whitespace_expl,
4890			SIZEOF_ARRAY(whitespace_expl));
4891	1		init_byte_class(&horizontal_whitespace, horizontal_whitespace_expl,
4892			SIZEOF_ARRAY(horizontal_whitespace_expl));
4893	1		init_byte_class(&vertical_whitespace, vertical_whitespace_expl,
4894			SIZEOF_ARRAY(vertical_whitespace_expl));
4895
4896	11	100	for (i = 0; i < SIZEOF_ARRAY(digit_expl); ++i)
4897			{
4898	10		digit_expl[i] = '0' + i;
4899			}
4900
4901	1		init_byte_class(&digit, digit_expl, SIZEOF_ARRAY(digit_expl));
4902
4903	1		memcpy(xdigit_expl, digit_expl, 10 * sizeof(char));
4904
4905	1		wstart = 10;
4906	7	100	for (i = 0; i < 6; ++i)
4907			{
4908	6		xdigit_expl[wstart + i] = 'a' + i;
4909			}
4910
4911	1		wstart += 6;
4912	7	100	for (i = 0; i < 6; ++i)
4913			{
4914	6		xdigit_expl[wstart + i] = 'A' + i;
4915			}
4916
4917	1		init_byte_class(&xdigit, xdigit_expl, SIZEOF_ARRAY(xdigit_expl));
4918
4919	1		init_byte_class(&ndot, ndot_expl, SIZEOF_ARRAY(ndot_expl));
4920
4921	1		alphanumeric_expl[0] = '_';
4922
4923	1		wstart = 1;
4924	1		memcpy(alphanumeric_expl + wstart, digit_expl, 10 * sizeof(char));
4925
4926	1		wstart += 10;
4927	27	100	for (i = 0; i < LETTER_COUNT; ++i)
4928			{
4929	26		alphanumeric_expl[wstart + i] = 'a' + i;
4930			}
4931
4932	1		wstart += LETTER_COUNT;
4933	27	100	for (i = 0; i < LETTER_COUNT; ++i)
4934			{
4935	26		alphanumeric_expl[wstart + i] = 'A' + i;
4936			}
4937
4938	1		init_byte_class(&word_bc, alphanumeric_expl,
4939			SIZEOF_ARRAY(alphanumeric_expl));
4940	1		init_byte_class(&alnum_bc, alphanumeric_expl + 1,
4941			SIZEOF_ARRAY(alphanumeric_expl) - 1);
4942
4943	27	100	for (i = 0; i < LETTER_COUNT; ++i)
4944			{
4945	26		alpha_expl[i] = lower_expl[i] = 'a' + i;
4946			}
4947
4948	1		wstart = LETTER_COUNT;
4949	27	100	for (i = 0; i < LETTER_COUNT; ++i)
4950			{
4951	26		alpha_expl[wstart + i] = upper_expl[i] = 'A' + i;
4952			}
4953
4954	1		init_byte_class(&alpha_bc, alpha_expl,
4955			SIZEOF_ARRAY(alpha_expl));
4956	1		init_byte_class(&lower_bc, lower_expl,
4957			SIZEOF_ARRAY(lower_expl));
4958	1		init_byte_class(&upper_bc, upper_expl,
4959			SIZEOF_ARRAY(upper_expl));
4960
4961	1		memset(alphanumeric_classes, 0, SIZEOF_ARRAY(alphanumeric_classes));
4962
4963	1		memset(non_alphanumeric_classes, 0,
4964			SIZEOF_ARRAY(non_alphanumeric_classes));
4965	1		non_alphanumeric_classes[EOS] = non_alphanumeric_classes[EOL] =
4966	1		non_alphanumeric_classes[SEOL] = 1;
4967
4968	1		posix_regclass_blocks[_CC_VERTSPACE] = VERTICAL_SPACE_BLOCK;
4969	1		posix_regclass_bitmaps[_CC_VERTSPACE] = vertical_whitespace.bitmap;
4970	1		posix_regclass_nbitmaps[_CC_VERTSPACE] = vertical_whitespace.nbitmap;
4971
4972	1		memset(word_posix_regclasses, 0,
4973			SIZEOF_ARRAY(word_posix_regclasses));
4974	1		word_posix_regclasses[_CC_WORDCHAR] =
4975	1		word_posix_regclasses[_CC_DIGIT] =
4976	1		word_posix_regclasses[_CC_ALPHA] =
4977	1		word_posix_regclasses[_CC_LOWER] =
4978	1		word_posix_regclasses[_CC_UPPER] =
4979	1		word_posix_regclasses[_CC_UPPER] =
4980	1		word_posix_regclasses[_CC_ALPHANUMERIC] =
4981	1		word_posix_regclasses[_CC_CASED] =
4982	1		word_posix_regclasses[_CC_XDIGIT] = 1;
4983
4984	1		memset(non_word_posix_regclasses, 0,
4985			SIZEOF_ARRAY(non_word_posix_regclasses));
4986	1		non_word_posix_regclasses[_CC_PUNCT] =
4987	1		non_word_posix_regclasses[_CC_SPACE] =
4988	1		non_word_posix_regclasses[_CC_BLANK] =
4989	1		non_word_posix_regclasses[_CC_VERTSPACE] = 1;
4990
4991	1		memset(newline_posix_regclasses, 0,
4992			SIZEOF_ARRAY(newline_posix_regclasses));
4993	1		newline_posix_regclasses[_CC_SPACE] =
4994	1		newline_posix_regclasses[_CC_CNTRL] =
4995	1		newline_posix_regclasses[_CC_ASCII] =
4996	1		newline_posix_regclasses[_CC_VERTSPACE] = 1;
4997
4998	1		memset(trivial_nodes, 0, SIZEOF_ARRAY(trivial_nodes));
4999	1		trivial_nodes[SUCCEED] = trivial_nodes[NOTHING] =
5000	1		trivial_nodes[TAIL] = trivial_nodes[WHILEM] = 1;
5001
5002	1		memset(dispatch, 0, sizeof(FCompare) * REGNODE_MAX * REGNODE_MAX);
5003
5004	93	100	for (i = 0; i < REGNODE_MAX; ++i)
5005			{
5006	92		dispatch[i][END] = success;
5007			}
5008
5009	93	100	for (i = 0; i < REGNODE_MAX; ++i)
5010			{
5011	92		dispatch[i][SUCCEED] = compare_next;
5012			}
5013
5014	1		dispatch[SUCCEED][SUCCEED] = compare_tails;
5015
5016	1		dispatch[SUCCEED][MBOL] = compare_left_tail;
5017	1		dispatch[MBOL][MBOL] = compare_tails;
5018	1		dispatch[SBOL][MBOL] = compare_tails;
5019	1		dispatch[REG_ANY][MBOL] = compare_mismatch;
5020	1		dispatch[SANY][MBOL] = compare_mismatch;
5021	1		dispatch[ANYOF][MBOL] = compare_anyof_multiline;
5022	1		dispatch[ANYOFD][MBOL] = compare_anyof_multiline;
5023			#ifdef RC_ANYOFM
5024			dispatch[ANYOFM][MBOL] = compare_anyofm_multiline;
5025			#endif
5026			#ifdef RC_NANYOFM
5027			dispatch[NANYOFM][MBOL] = compare_nanyofm_multiline;
5028			#endif
5029	1		dispatch[POSIXD][MBOL] = compare_mismatch;
5030	1		dispatch[POSIXU][MBOL] = compare_mismatch;
5031	1		dispatch[POSIXA][MBOL] = compare_mismatch;
5032	1		dispatch[NPOSIXD][MBOL] = compare_mismatch;
5033	1		dispatch[NPOSIXU][MBOL] = compare_mismatch;
5034	1		dispatch[NPOSIXA][MBOL] = compare_mismatch;
5035	1		dispatch[BRANCH][MBOL] = compare_left_branch;
5036	1		dispatch[EXACT][MBOL] = compare_exact_multiline;
5037	1		dispatch[EXACTF][MBOL] = compare_exact_multiline;
5038	1		dispatch[EXACTFU][MBOL] = compare_exact_multiline;
5039	1		dispatch[NOTHING][MBOL] = compare_left_tail;
5040	1		dispatch[TAIL][MBOL] = compare_left_tail;
5041	1		dispatch[STAR][MBOL] = compare_mismatch;
5042	1		dispatch[PLUS][MBOL] = compare_left_plus;
5043	1		dispatch[CURLY][MBOL] = compare_left_curly;
5044	1		dispatch[CURLYM][MBOL] = compare_left_curly;
5045	1		dispatch[CURLYX][MBOL] = compare_left_curly;
5046	1		dispatch[WHILEM][MBOL] = compare_left_tail;
5047	1		dispatch[OPEN][MBOL] = compare_left_open;
5048	1		dispatch[CLOSE][MBOL] = compare_left_tail;
5049	1		dispatch[IFMATCH][MBOL] = compare_after_assertion;
5050	1		dispatch[UNLESSM][MBOL] = compare_after_assertion;
5051	1		dispatch[MINMOD][MBOL] = compare_left_tail;
5052	1		dispatch[LNBREAK][MBOL] = compare_tails;
5053	1		dispatch[OPTIMIZED][MBOL] = compare_left_tail;
5054
5055	1		dispatch[SUCCEED][SBOL] = compare_left_tail;
5056	1		dispatch[SBOL][SBOL] = compare_tails;
5057	1		dispatch[BRANCH][SBOL] = compare_left_branch;
5058	1		dispatch[NOTHING][SBOL] = compare_left_tail;
5059	1		dispatch[TAIL][SBOL] = compare_left_tail;
5060	1		dispatch[STAR][SBOL] = compare_mismatch;
5061	1		dispatch[PLUS][SBOL] = compare_left_plus;
5062	1		dispatch[CURLY][SBOL] = compare_left_curly;
5063	1		dispatch[CURLYM][SBOL] = compare_left_curly;
5064	1		dispatch[CURLYX][SBOL] = compare_left_curly;
5065	1		dispatch[WHILEM][SBOL] = compare_left_tail;
5066	1		dispatch[OPEN][SBOL] = compare_left_open;
5067	1		dispatch[CLOSE][SBOL] = compare_left_tail;
5068	1		dispatch[IFMATCH][SBOL] = compare_after_assertion;
5069	1		dispatch[UNLESSM][SBOL] = compare_after_assertion;
5070	1		dispatch[MINMOD][SBOL] = compare_left_tail;
5071	1		dispatch[OPTIMIZED][SBOL] = compare_left_tail;
5072
5073	1		dispatch[SUCCEED][EOS] = compare_left_tail;
5074	1		dispatch[EOS][EOS] = compare_tails;
5075	1		dispatch[EOL][EOS] = compare_mismatch;
5076	1		dispatch[SEOL][EOS] = compare_mismatch;
5077	1		dispatch[BRANCH][EOS] = compare_left_branch;
5078	1		dispatch[NOTHING][EOS] = compare_left_tail;
5079	1		dispatch[TAIL][EOS] = compare_left_tail;
5080	1		dispatch[STAR][EOS] = compare_mismatch;
5081	1		dispatch[PLUS][EOS] = compare_left_plus;
5082	1		dispatch[CURLY][EOS] = compare_left_curly;
5083	1		dispatch[CURLYM][EOS] = compare_left_curly;
5084	1		dispatch[CURLYX][EOS] = compare_left_curly;
5085	1		dispatch[WHILEM][EOS] = compare_left_tail;
5086	1		dispatch[OPEN][EOS] = compare_left_open;
5087	1		dispatch[CLOSE][EOS] = compare_left_tail;
5088	1		dispatch[IFMATCH][EOS] = compare_after_assertion;
5089	1		dispatch[UNLESSM][EOS] = compare_after_assertion;
5090	1		dispatch[MINMOD][EOS] = compare_left_tail;
5091	1		dispatch[OPTIMIZED][EOS] = compare_left_tail;
5092
5093	1		dispatch[SUCCEED][EOL] = compare_left_tail;
5094	1		dispatch[EOS][EOL] = compare_tails;
5095	1		dispatch[EOL][EOL] = compare_tails;
5096	1		dispatch[SEOL][EOL] = compare_tails;
5097	1		dispatch[BRANCH][EOL] = compare_left_branch;
5098	1		dispatch[NOTHING][EOL] = compare_left_tail;
5099	1		dispatch[TAIL][EOL] = compare_left_tail;
5100	1		dispatch[STAR][EOL] = compare_mismatch;
5101	1		dispatch[PLUS][EOL] = compare_left_plus;
5102	1		dispatch[CURLY][EOL] = compare_left_curly;
5103	1		dispatch[CURLYM][EOL] = compare_left_curly;
5104	1		dispatch[CURLYX][EOL] = compare_left_curly;
5105	1		dispatch[WHILEM][EOL] = compare_left_tail;
5106	1		dispatch[OPEN][EOL] = compare_left_open;
5107	1		dispatch[CLOSE][EOL] = compare_left_tail;
5108	1		dispatch[IFMATCH][EOL] = compare_after_assertion;
5109	1		dispatch[UNLESSM][EOL] = compare_after_assertion;
5110	1		dispatch[MINMOD][EOL] = compare_left_tail;
5111	1		dispatch[OPTIMIZED][EOL] = compare_left_tail;
5112
5113	1		dispatch[SUCCEED][MEOL] = compare_left_tail;
5114	1		dispatch[EOS][MEOL] = compare_tails;
5115	1		dispatch[EOL][MEOL] = compare_tails;
5116	1		dispatch[MEOL][MEOL] = compare_tails;
5117	1		dispatch[SEOL][MEOL] = compare_tails;
5118	1		dispatch[REG_ANY][MEOL] = compare_mismatch;
5119	1		dispatch[SANY][MEOL] = compare_mismatch;
5120	1		dispatch[ANYOF][MEOL] = compare_anyof_multiline; /* not in tests; remove? */
5121	1		dispatch[POSIXD][MEOL] = compare_mismatch;
5122	1		dispatch[POSIXU][MEOL] = compare_mismatch;
5123	1		dispatch[POSIXA][MEOL] = compare_mismatch;
5124	1		dispatch[NPOSIXD][MEOL] = compare_mismatch;
5125	1		dispatch[NPOSIXU][MEOL] = compare_mismatch;
5126	1		dispatch[NPOSIXA][MEOL] = compare_mismatch;
5127	1		dispatch[BRANCH][MEOL] = compare_left_branch;
5128	1		dispatch[EXACT][MEOL] = compare_exact_multiline;
5129	1		dispatch[EXACTF][MEOL] = compare_exact_multiline;
5130	1		dispatch[EXACTFU][MEOL] = compare_exact_multiline;
5131	1		dispatch[NOTHING][MEOL] = compare_left_tail;
5132	1		dispatch[TAIL][MEOL] = compare_left_tail;
5133	1		dispatch[STAR][MEOL] = compare_mismatch;
5134	1		dispatch[PLUS][MEOL] = compare_left_plus;
5135	1		dispatch[CURLY][MEOL] = compare_left_curly;
5136	1		dispatch[CURLYM][MEOL] = compare_left_curly;
5137	1		dispatch[CURLYX][MEOL] = compare_left_curly;
5138	1		dispatch[WHILEM][MEOL] = compare_left_tail;
5139	1		dispatch[OPEN][MEOL] = compare_left_open;
5140	1		dispatch[CLOSE][MEOL] = compare_left_tail;
5141	1		dispatch[IFMATCH][MEOL] = compare_after_assertion;
5142	1		dispatch[UNLESSM][MEOL] = compare_after_assertion;
5143	1		dispatch[MINMOD][MEOL] = compare_left_tail;
5144	1		dispatch[LNBREAK][MEOL] = compare_mismatch;
5145	1		dispatch[OPTIMIZED][MEOL] = compare_left_tail;
5146
5147	1		dispatch[SUCCEED][SEOL] = compare_left_tail;
5148	1		dispatch[EOS][SEOL] = compare_tails;
5149	1		dispatch[EOL][SEOL] = compare_tails;
5150	1		dispatch[SEOL][SEOL] = compare_tails;
5151	1		dispatch[BRANCH][SEOL] = compare_left_branch;
5152	1		dispatch[NOTHING][SEOL] = compare_left_tail;
5153	1		dispatch[POSIXD][SEOL] = compare_mismatch;
5154	1		dispatch[POSIXU][SEOL] = compare_mismatch;
5155	1		dispatch[POSIXA][SEOL] = compare_mismatch;
5156	1		dispatch[NPOSIXD][SEOL] = compare_mismatch;
5157	1		dispatch[NPOSIXU][SEOL] = compare_mismatch;
5158	1		dispatch[NPOSIXA][SEOL] = compare_mismatch;
5159	1		dispatch[TAIL][SEOL] = compare_left_tail;
5160	1		dispatch[STAR][SEOL] = 0;
5161	1		dispatch[PLUS][SEOL] = compare_left_plus;
5162	1		dispatch[CURLY][SEOL] = compare_left_curly;
5163	1		dispatch[CURLYM][SEOL] = compare_left_curly;
5164	1		dispatch[CURLYX][SEOL] = compare_left_curly;
5165	1		dispatch[WHILEM][SEOL] = compare_left_tail;
5166	1		dispatch[OPEN][SEOL] = compare_left_open;
5167	1		dispatch[CLOSE][SEOL] = compare_left_tail;
5168	1		dispatch[IFMATCH][SEOL] = compare_after_assertion;
5169	1		dispatch[UNLESSM][SEOL] = compare_after_assertion;
5170	1		dispatch[MINMOD][SEOL] = compare_left_tail;
5171	1		dispatch[LNBREAK][SEOL] = compare_mismatch;
5172	1		dispatch[OPTIMIZED][SEOL] = compare_left_tail;
5173
5174	1		dispatch[SUCCEED][BOUND] = compare_left_tail;
5175	1		dispatch[MBOL][BOUND] = compare_bol_word;
5176	1		dispatch[SBOL][BOUND] = compare_bol_word;
5177	1		dispatch[BOUND][BOUND] = compare_tails;
5178	1		dispatch[NBOUND][BOUND] = compare_mismatch;
5179	1		dispatch[REG_ANY][BOUND] = compare_mismatch;
5180	1		dispatch[SANY][BOUND] = compare_mismatch;
5181	1		dispatch[ANYOF][BOUND] = compare_anyof_bound;
5182	1		dispatch[ANYOFD][BOUND] = compare_anyof_bound;
5183			#ifdef RC_ANYOFM
5184			dispatch[ANYOFM][BOUND] = compare_anyofm_bound;
5185			#endif
5186			#ifdef RC_NANYOFM
5187			dispatch[NANYOFM][BOUND] = compare_mismatch;
5188			#endif
5189	1		dispatch[POSIXD][BOUND] = compare_posix_bound;
5190	1		dispatch[POSIXU][BOUND] = compare_posix_bound;
5191	1		dispatch[POSIXA][BOUND] = compare_posix_bound;
5192	1		dispatch[NPOSIXD][BOUND] = compare_negative_posix_word_bound;
5193	1		dispatch[NPOSIXU][BOUND] = compare_mismatch; /* should be replaced, needs extra test */
5194	1		dispatch[NPOSIXA][BOUND] = compare_negative_posix_word_bound;
5195	1		dispatch[BRANCH][BOUND] = compare_left_branch;
5196	1		dispatch[EXACT][BOUND] = compare_exact_bound;
5197	1		dispatch[EXACTF][BOUND] = compare_exact_bound;
5198	1		dispatch[EXACTFU][BOUND] = compare_exact_bound;
5199	1		dispatch[NOTHING][BOUND] = compare_left_tail;
5200	1		dispatch[TAIL][BOUND] = compare_left_tail;
5201	1		dispatch[CURLY][BOUND] = compare_left_curly;
5202	1		dispatch[CURLYM][BOUND] = compare_left_curly;
5203	1		dispatch[CURLYX][BOUND] = compare_left_curly;
5204	1		dispatch[WHILEM][BOUND] = compare_left_tail;
5205	1		dispatch[OPEN][BOUND] = compare_left_open;
5206	1		dispatch[CLOSE][BOUND] = compare_left_tail;
5207	1		dispatch[IFMATCH][BOUND] = compare_after_assertion;
5208	1		dispatch[UNLESSM][BOUND] = compare_after_assertion;
5209	1		dispatch[MINMOD][BOUND] = compare_left_tail;
5210	1		dispatch[LNBREAK][BOUND] = compare_mismatch;
5211	1		dispatch[OPTIMIZED][BOUND] = compare_left_tail;
5212
5213	1		dispatch[SUCCEED][NBOUND] = compare_left_tail;
5214	1		dispatch[MBOL][NBOUND] = compare_bol_nword;
5215	1		dispatch[SBOL][NBOUND] = compare_bol_nword;
5216	1		dispatch[BOUND][NBOUND] = compare_mismatch;
5217	1		dispatch[NBOUND][NBOUND] = compare_tails;
5218	1		dispatch[REG_ANY][NBOUND] = compare_mismatch;
5219	1		dispatch[SANY][NBOUND] = compare_mismatch;
5220	1		dispatch[ANYOF][NBOUND] = compare_anyof_nbound;
5221	1		dispatch[ANYOFD][NBOUND] = compare_anyof_nbound;
5222			#ifdef RC_ANYOFM
5223			dispatch[ANYOFM][NBOUND] = compare_anyofm_nbound;
5224			#endif
5225			#ifdef RC_NANYOFM
5226			dispatch[NANYOFM][NBOUND] = compare_mismatch;
5227			#endif
5228	1		dispatch[POSIXD][NBOUND] = compare_posix_nbound;
5229	1		dispatch[POSIXU][NBOUND] = compare_posix_nbound;
5230	1		dispatch[POSIXA][NBOUND] = compare_posix_nbound;
5231	1		dispatch[NPOSIXD][NBOUND] = compare_negative_posix_word_nbound;
5232	1		dispatch[NPOSIXU][NBOUND] = compare_negative_posix_word_nbound;
5233	1		dispatch[NPOSIXA][NBOUND] = compare_negative_posix_word_nbound;
5234	1		dispatch[BRANCH][NBOUND] = compare_left_branch;
5235	1		dispatch[EXACT][NBOUND] = compare_exact_nbound;
5236	1		dispatch[EXACTF][NBOUND] = compare_exact_nbound;
5237	1		dispatch[EXACTFU][NBOUND] = compare_exact_nbound;
5238	1		dispatch[NOTHING][NBOUND] = compare_left_tail;
5239	1		dispatch[TAIL][NBOUND] = compare_left_tail;
5240	1		dispatch[CURLY][NBOUND] = compare_left_curly;
5241	1		dispatch[CURLYM][NBOUND] = compare_left_curly;
5242	1		dispatch[CURLYX][NBOUND] = compare_left_curly;
5243	1		dispatch[WHILEM][NBOUND] = compare_left_tail;
5244	1		dispatch[OPEN][NBOUND] = compare_left_open;
5245	1		dispatch[CLOSE][NBOUND] = compare_left_tail;
5246	1		dispatch[IFMATCH][NBOUND] = compare_after_assertion;
5247	1		dispatch[UNLESSM][NBOUND] = compare_after_assertion;
5248	1		dispatch[MINMOD][NBOUND] = compare_left_tail;
5249	1		dispatch[LNBREAK][NBOUND] = compare_mismatch;
5250	1		dispatch[OPTIMIZED][NBOUND] = compare_left_tail;
5251
5252	1		dispatch[SUCCEED][REG_ANY] = compare_left_tail;
5253	1		dispatch[MBOL][REG_ANY] = compare_bol;
5254	1		dispatch[SBOL][REG_ANY] = compare_bol;
5255	1		dispatch[BOUND][REG_ANY] = compare_mismatch;
5256	1		dispatch[NBOUND][REG_ANY] = compare_mismatch;
5257	1		dispatch[REG_ANY][REG_ANY] = compare_tails;
5258	1		dispatch[SANY][REG_ANY] = compare_mismatch;
5259	1		dispatch[ANYOF][REG_ANY] = compare_anyof_reg_any;
5260	1		dispatch[ANYOFD][REG_ANY] = compare_anyof_reg_any;
5261			#ifdef RC_ANYOFM
5262			dispatch[ANYOFM][REG_ANY] = compare_anyofm_reg_any;
5263			#endif
5264			#ifdef RC_NANYOFM
5265			dispatch[NANYOFM][REG_ANY] = compare_nanyofm_reg_any;
5266			#endif
5267	1		dispatch[POSIXD][REG_ANY] = compare_posix_reg_any;
5268	1		dispatch[POSIXU][REG_ANY] = compare_posix_reg_any;
5269	1		dispatch[POSIXA][REG_ANY] = compare_posix_reg_any;
5270	1		dispatch[NPOSIXD][REG_ANY] = compare_negative_posix_reg_any;
5271	1		dispatch[NPOSIXU][REG_ANY] = compare_negative_posix_reg_any;
5272	1		dispatch[NPOSIXA][REG_ANY] = compare_negative_posix_reg_any;
5273	1		dispatch[BRANCH][REG_ANY] = compare_left_branch;
5274	1		dispatch[EXACT][REG_ANY] = compare_exact_reg_any;
5275	1		dispatch[EXACTF][REG_ANY] = compare_exact_reg_any;
5276	1		dispatch[EXACTFU][REG_ANY] = compare_exact_reg_any;
5277	1		dispatch[NOTHING][REG_ANY] = compare_left_tail;
5278	1		dispatch[TAIL][REG_ANY] = compare_left_tail;
5279	1		dispatch[STAR][REG_ANY] = compare_mismatch;
5280	1		dispatch[PLUS][REG_ANY] = compare_left_plus;
5281	1		dispatch[CURLY][REG_ANY] = compare_left_curly;
5282	1		dispatch[CURLYM][REG_ANY] = compare_left_curly;
5283	1		dispatch[CURLYX][REG_ANY] = compare_left_curly;
5284	1		dispatch[WHILEM][REG_ANY] = compare_left_tail;
5285	1		dispatch[OPEN][REG_ANY] = compare_left_open;
5286	1		dispatch[CLOSE][REG_ANY] = compare_left_tail;
5287	1		dispatch[IFMATCH][REG_ANY] = compare_after_assertion;
5288	1		dispatch[UNLESSM][REG_ANY] = compare_after_assertion;
5289	1		dispatch[MINMOD][REG_ANY] = compare_left_tail;
5290	1		dispatch[LNBREAK][REG_ANY] = compare_mismatch;
5291	1		dispatch[OPTIMIZED][REG_ANY] = compare_left_tail;
5292
5293	1		dispatch[SUCCEED][SANY] = compare_left_tail;
5294	1		dispatch[MBOL][SANY] = compare_bol;
5295	1		dispatch[SBOL][SANY] = compare_bol;
5296	1		dispatch[BOUND][SANY] = compare_mismatch;
5297	1		dispatch[NBOUND][SANY] = compare_mismatch;
5298	1		dispatch[REG_ANY][SANY] = compare_tails;
5299	1		dispatch[SANY][SANY] = compare_tails;
5300	1		dispatch[ANYOF][SANY] = compare_tails;
5301	1		dispatch[ANYOFD][SANY] = compare_tails;
5302			#ifdef RC_ANYOFM
5303			dispatch[ANYOFM][SANY] = compare_tails;
5304			#endif
5305			#ifdef RC_NANYOFM
5306			dispatch[NANYOFM][SANY] = compare_tails;
5307			#endif
5308	1		dispatch[POSIXD][SANY] = compare_tails;
5309	1		dispatch[POSIXU][SANY] = compare_tails;
5310	1		dispatch[POSIXA][SANY] = compare_tails;
5311	1		dispatch[NPOSIXD][SANY] = compare_tails;
5312	1		dispatch[NPOSIXU][SANY] = compare_tails;
5313	1		dispatch[NPOSIXA][SANY] = compare_tails;
5314	1		dispatch[BRANCH][SANY] = compare_left_branch;
5315	1		dispatch[EXACT][SANY] = compare_tails;
5316	1		dispatch[EXACTF][SANY] = compare_tails;
5317	1		dispatch[EXACTFU][SANY] = compare_tails;
5318	1		dispatch[NOTHING][SANY] = compare_left_tail;
5319	1		dispatch[TAIL][SANY] = compare_left_tail;
5320	1		dispatch[STAR][SANY] = compare_mismatch;
5321	1		dispatch[PLUS][SANY] = compare_left_plus;
5322	1		dispatch[CURLY][SANY] = compare_left_curly;
5323	1		dispatch[CURLYM][SANY] = compare_left_curly;
5324	1		dispatch[CURLYX][SANY] = compare_left_curly;
5325	1		dispatch[WHILEM][SANY] = compare_left_tail;
5326	1		dispatch[OPEN][SANY] = compare_left_open;
5327	1		dispatch[CLOSE][SANY] = compare_left_tail;
5328	1		dispatch[IFMATCH][SANY] = compare_after_assertion;
5329	1		dispatch[UNLESSM][SANY] = compare_after_assertion;
5330	1		dispatch[MINMOD][SANY] = compare_left_tail;
5331	1		dispatch[LNBREAK][SANY] = compare_mismatch;
5332	1		dispatch[OPTIMIZED][SANY] = compare_left_tail;
5333
5334	1		dispatch[SUCCEED][ANYOF] = compare_left_tail;
5335	1		dispatch[MBOL][ANYOF] = compare_bol;
5336	1		dispatch[SBOL][ANYOF] = compare_bol;
5337	1		dispatch[BOUND][ANYOF] = compare_mismatch;
5338	1		dispatch[NBOUND][ANYOF] = compare_mismatch;
5339	1		dispatch[REG_ANY][ANYOF] = compare_reg_any_anyof;
5340	1		dispatch[SANY][ANYOF] = compare_sany_anyof;
5341	1		dispatch[ANYOF][ANYOF] = compare_anyof_anyof;
5342	1		dispatch[ANYOFD][ANYOF] = compare_anyof_anyof;
5343			#ifdef RC_ANYOFM
5344			dispatch[ANYOFM][ANYOF] = compare_anyofm_anyof;
5345			#endif
5346			#ifdef RC_NANYOFM
5347			dispatch[NANYOFM][ANYOF] = compare_mismatch;
5348			#endif
5349	1		dispatch[POSIXD][ANYOF] = compare_posix_anyof;
5350	1		dispatch[POSIXU][ANYOF] = compare_posix_anyof;
5351	1		dispatch[POSIXA][ANYOF] = compare_posix_anyof;
5352	1		dispatch[NPOSIXD][ANYOF] = compare_negative_posix_anyof;
5353	1		dispatch[NPOSIXU][ANYOF] = compare_negative_posix_anyof;
5354	1		dispatch[NPOSIXA][ANYOF] = compare_negative_posix_anyof;
5355	1		dispatch[BRANCH][ANYOF] = compare_left_branch;
5356	1		dispatch[EXACT][ANYOF] = compare_exact_anyof;
5357	1		dispatch[EXACTF][ANYOF] = compare_exactf_anyof;
5358	1		dispatch[EXACTFU][ANYOF] = compare_exactf_anyof;
5359	1		dispatch[NOTHING][ANYOF] = compare_left_tail;
5360	1		dispatch[TAIL][ANYOF] = compare_left_tail;
5361	1		dispatch[STAR][ANYOF] = compare_mismatch;
5362	1		dispatch[PLUS][ANYOF] = compare_left_plus;
5363	1		dispatch[CURLY][ANYOF] = compare_left_curly;
5364	1		dispatch[CURLYM][ANYOF] = compare_left_curly;
5365	1		dispatch[CURLYX][ANYOF] = compare_left_curly;
5366	1		dispatch[WHILEM][ANYOF] = compare_left_tail;
5367	1		dispatch[OPEN][ANYOF] = compare_left_open;
5368	1		dispatch[CLOSE][ANYOF] = compare_left_tail;
5369	1		dispatch[IFMATCH][ANYOF] = compare_after_assertion;
5370	1		dispatch[UNLESSM][ANYOF] = compare_after_assertion;
5371	1		dispatch[MINMOD][ANYOF] = compare_left_tail;
5372	1		dispatch[LNBREAK][ANYOF] = compare_mismatch;
5373	1		dispatch[OPTIMIZED][ANYOF] = compare_left_tail;
5374
5375	1		dispatch[SUCCEED][ANYOFD] = compare_left_tail;
5376	1		dispatch[MBOL][ANYOFD] = compare_bol;
5377	1		dispatch[SBOL][ANYOFD] = compare_bol;
5378	1		dispatch[BOUND][ANYOFD] = compare_mismatch;
5379	1		dispatch[NBOUND][ANYOFD] = compare_mismatch;
5380	1		dispatch[REG_ANY][ANYOFD] = compare_reg_any_anyof;
5381	1		dispatch[SANY][ANYOFD] = compare_sany_anyof;
5382	1		dispatch[ANYOF][ANYOFD] = compare_anyof_anyof;
5383	1		dispatch[ANYOFD][ANYOFD] = compare_anyof_anyof;
5384			#ifdef RC_ANYOFM
5385			dispatch[ANYOFM][ANYOFD] = compare_anyofm_anyof;
5386			#endif
5387			#ifdef RC_NANYOFM
5388			dispatch[NANYOFM][ANYOFD] = compare_mismatch;
5389			#endif
5390	1		dispatch[POSIXD][ANYOFD] = compare_posix_anyof;
5391	1		dispatch[POSIXU][ANYOFD] = compare_posix_anyof;
5392	1		dispatch[POSIXA][ANYOFD] = compare_posix_anyof;
5393	1		dispatch[NPOSIXD][ANYOFD] = compare_negative_posix_anyof;
5394	1		dispatch[NPOSIXU][ANYOFD] = compare_negative_posix_anyof;
5395	1		dispatch[NPOSIXA][ANYOFD] = compare_negative_posix_anyof;
5396	1		dispatch[BRANCH][ANYOFD] = compare_left_branch;
5397	1		dispatch[EXACT][ANYOFD] = compare_exact_anyof;
5398	1		dispatch[EXACTFU][ANYOFD] = compare_exactf_anyof;
5399	1		dispatch[NOTHING][ANYOFD] = compare_left_tail;
5400	1		dispatch[TAIL][ANYOFD] = compare_left_tail;
5401	1		dispatch[STAR][ANYOFD] = compare_mismatch;
5402	1		dispatch[PLUS][ANYOFD] = compare_left_plus;
5403	1		dispatch[CURLY][ANYOFD] = compare_left_curly;
5404	1		dispatch[CURLYM][ANYOFD] = compare_left_curly;
5405	1		dispatch[CURLYX][ANYOFD] = compare_left_curly;
5406	1		dispatch[OPEN][ANYOFD] = compare_left_open;
5407	1		dispatch[CLOSE][ANYOFD] = compare_left_tail;
5408	1		dispatch[IFMATCH][ANYOFD] = compare_after_assertion;
5409	1		dispatch[UNLESSM][ANYOFD] = compare_after_assertion;
5410	1		dispatch[MINMOD][ANYOFD] = compare_left_tail;
5411	1		dispatch[LNBREAK][ANYOFD] = compare_mismatch;
5412	1		dispatch[OPTIMIZED][ANYOFD] = compare_left_tail;
5413
5414			#ifdef RC_ANYOFM
5415			dispatch[SUCCEED][ANYOFM] = compare_left_tail;
5416			dispatch[MBOL][ANYOFM] = compare_bol;
5417			dispatch[SBOL][ANYOFM] = compare_bol;
5418			dispatch[BOUND][ANYOFM] = compare_mismatch;
5419			dispatch[NBOUND][ANYOFM] = compare_mismatch;
5420			dispatch[REG_ANY][ANYOFM] = compare_mismatch;
5421			dispatch[SANY][ANYOFM] = compare_mismatch;
5422			dispatch[ANYOF][ANYOFM] = compare_anyof_anyofm;
5423			dispatch[ANYOFD][ANYOFM] = compare_anyof_anyofm;
5424			dispatch[ANYOFM][ANYOFM] = compare_anyofm_anyofm;
5425			#ifdef RC_NANYOFM
5426			dispatch[NANYOFM][ANYOFM] = compare_mismatch;
5427			#endif
5428			dispatch[POSIXD][ANYOFM] = compare_mismatch;
5429			dispatch[POSIXU][ANYOFM] = compare_mismatch;
5430			dispatch[POSIXA][ANYOFM] = compare_mismatch;
5431			dispatch[NPOSIXD][ANYOFM] = compare_mismatch;
5432			dispatch[NPOSIXU][ANYOFM] = compare_mismatch;
5433			dispatch[NPOSIXA][ANYOFM] = compare_mismatch;
5434			dispatch[BRANCH][ANYOFM] = compare_left_branch;
5435			dispatch[EXACT][ANYOFM] = compare_exact_anyofm;
5436			dispatch[EXACTF][ANYOFM] = compare_exactf_anyofm;
5437			dispatch[EXACTFU][ANYOFM] = compare_exactf_anyofm;
5438			dispatch[NOTHING][ANYOFM] = compare_left_tail;
5439			dispatch[TAIL][ANYOFM] = compare_left_tail;
5440			dispatch[STAR][ANYOFM] = compare_mismatch;
5441			dispatch[PLUS][ANYOFM] = compare_left_plus;
5442			dispatch[CURLY][ANYOFM] = compare_left_curly;
5443			dispatch[CURLYM][ANYOFM] = compare_left_curly;
5444			dispatch[CURLYX][ANYOFM] = compare_left_curly;
5445			dispatch[OPEN][ANYOFM] = compare_left_open;
5446			dispatch[CLOSE][ANYOFM] = compare_left_tail;
5447			dispatch[IFMATCH][ANYOFM] = compare_after_assertion;
5448			dispatch[UNLESSM][ANYOFM] = compare_after_assertion;
5449			dispatch[MINMOD][ANYOFM] = compare_left_tail;
5450			dispatch[LNBREAK][ANYOFM] = compare_mismatch;
5451			dispatch[OPTIMIZED][ANYOFM] = compare_left_tail;
5452			#endif
5453
5454			#ifdef RC_NANYOFM
5455			dispatch[SUCCEED][NANYOFM] = compare_left_tail;
5456			dispatch[MBOL][NANYOFM] = compare_bol;
5457			dispatch[SBOL][NANYOFM] = compare_bol;
5458			dispatch[BOUND][NANYOFM] = compare_mismatch;
5459			dispatch[NBOUND][NANYOFM] = compare_mismatch;
5460			dispatch[REG_ANY][NANYOFM] = compare_mismatch;
5461			dispatch[SANY][NANYOFM] = compare_mismatch;
5462			dispatch[ANYOF][NANYOFM] = compare_anyof_nanyofm;
5463			dispatch[ANYOFD][NANYOFM] = compare_anyof_nanyofm;
5464			dispatch[ANYOFM][NANYOFM] = compare_anyofm_nanyofm;
5465			dispatch[NANYOFM][NANYOFM] = compare_nanyofm_nanyofm;
5466			dispatch[POSIXD][NANYOFM] = compare_posix_nanyofm;
5467			dispatch[POSIXU][NANYOFM] = compare_posix_nanyofm;
5468			dispatch[POSIXA][NANYOFM] = compare_posix_nanyofm;
5469			dispatch[NPOSIXD][NANYOFM] = compare_negative_posix_nanyofm;
5470			dispatch[NPOSIXU][NANYOFM] = compare_negative_posix_nanyofm;
5471			dispatch[NPOSIXA][NANYOFM] = compare_negative_posix_nanyofm;
5472			dispatch[BRANCH][NANYOFM] = compare_left_branch;
5473			dispatch[EXACT][NANYOFM] = compare_exact_nanyofm;
5474			dispatch[EXACTF][NANYOFM] = compare_exactf_nanyofm;
5475			dispatch[EXACTFU][NANYOFM] = compare_exactf_nanyofm;
5476			dispatch[NOTHING][NANYOFM] = compare_left_tail;
5477			dispatch[TAIL][NANYOFM] = compare_left_tail;
5478			dispatch[STAR][NANYOFM] = compare_mismatch;
5479			dispatch[PLUS][NANYOFM] = compare_left_plus;
5480			dispatch[CURLY][NANYOFM] = compare_left_curly;
5481			dispatch[CURLYM][NANYOFM] = compare_left_curly;
5482			dispatch[CURLYX][NANYOFM] = compare_left_curly;
5483			dispatch[OPEN][NANYOFM] = compare_left_open;
5484			dispatch[CLOSE][NANYOFM] = compare_left_tail;
5485			dispatch[IFMATCH][NANYOFM] = compare_after_assertion;
5486			dispatch[UNLESSM][NANYOFM] = compare_after_assertion;
5487			dispatch[MINMOD][NANYOFM] = compare_left_tail;
5488			dispatch[LNBREAK][NANYOFM] = compare_mismatch;
5489			dispatch[OPTIMIZED][NANYOFM] = compare_left_tail;
5490			#endif
5491
5492	1		dispatch[SUCCEED][POSIXD] = compare_left_tail;
5493	1		dispatch[MBOL][POSIXD] = compare_bol;
5494	1		dispatch[SBOL][POSIXD] = compare_bol;
5495	1		dispatch[BOUND][POSIXD] = compare_mismatch;
5496	1		dispatch[NBOUND][POSIXD] = compare_mismatch;
5497	1		dispatch[REG_ANY][POSIXD] = compare_mismatch;
5498	1		dispatch[SANY][POSIXD] = compare_mismatch;
5499	1		dispatch[ANYOF][POSIXD] = compare_anyof_posix;
5500	1		dispatch[ANYOFD][POSIXD] = compare_anyof_posix;
5501			#ifdef RC_ANYOFM
5502			dispatch[ANYOFM][POSIXD] = compare_anyofm_posix;
5503			#endif
5504			#ifdef RC_NANYOFM
5505			dispatch[NANYOFM][POSIXD] = compare_nanyofm_posix;
5506			#endif
5507	1		dispatch[POSIXD][POSIXD] = compare_posix_posix;
5508	1		dispatch[POSIXU][POSIXD] = compare_posix_posix;
5509	1		dispatch[POSIXA][POSIXD] = compare_posix_posix;
5510	1		dispatch[NPOSIXD][POSIXD] = compare_mismatch;
5511	1		dispatch[NPOSIXU][POSIXD] = compare_mismatch;
5512	1		dispatch[NPOSIXA][POSIXD] = compare_mismatch;
5513	1		dispatch[BRANCH][POSIXD] = compare_left_branch;
5514	1		dispatch[EXACT][POSIXD] = compare_exact_posix;
5515	1		dispatch[EXACTF][POSIXD] = compare_exactf_posix;
5516	1		dispatch[EXACTFU][POSIXD] = compare_exactf_posix;
5517	1		dispatch[NOTHING][POSIXD] = compare_left_tail;
5518	1		dispatch[STAR][POSIXD] = compare_mismatch;
5519	1		dispatch[PLUS][POSIXD] = compare_left_plus;
5520	1		dispatch[CURLY][POSIXD] = compare_left_curly;
5521	1		dispatch[CURLYM][POSIXD] = compare_left_curly;
5522	1		dispatch[CURLYX][POSIXD] = compare_left_curly;
5523	1		dispatch[OPEN][POSIXD] = compare_left_open;
5524	1		dispatch[CLOSE][POSIXD] = compare_left_tail;
5525	1		dispatch[IFMATCH][POSIXD] = compare_after_assertion;
5526	1		dispatch[UNLESSM][POSIXD] = compare_after_assertion;
5527	1		dispatch[MINMOD][POSIXD] = compare_left_tail;
5528	1		dispatch[LNBREAK][POSIXD] = compare_mismatch;
5529	1		dispatch[OPTIMIZED][POSIXD] = compare_left_tail;
5530
5531	1		dispatch[SUCCEED][POSIXU] = compare_left_tail;
5532	1		dispatch[MBOL][POSIXU] = compare_bol;
5533	1		dispatch[SBOL][POSIXU] = compare_bol;
5534	1		dispatch[BOUND][POSIXU] = compare_mismatch;
5535	1		dispatch[NBOUND][POSIXU] = compare_mismatch;
5536	1		dispatch[REG_ANY][POSIXU] = compare_mismatch;
5537	1		dispatch[SANY][POSIXU] = compare_mismatch;
5538	1		dispatch[ANYOF][POSIXU] = compare_anyof_posix;
5539	1		dispatch[ANYOFD][POSIXU] = compare_anyof_posix;
5540			#ifdef RC_ANYOFM
5541			dispatch[ANYOFM][POSIXU] = compare_anyofm_posix;
5542			#endif
5543			#ifdef RC_NANYOFM
5544			dispatch[NANYOFM][POSIXU] = compare_nanyofm_posix;
5545			#endif
5546	1		dispatch[POSIXD][POSIXU] = compare_posix_posix;
5547	1		dispatch[POSIXA][POSIXU] = compare_posix_posix;
5548	1		dispatch[POSIXU][POSIXU] = compare_posix_posix;
5549	1		dispatch[NPOSIXD][POSIXU] = compare_mismatch;
5550	1		dispatch[NPOSIXU][POSIXU] = compare_mismatch;
5551	1		dispatch[NPOSIXA][POSIXU] = compare_mismatch;
5552	1		dispatch[BRANCH][POSIXU] = compare_left_branch;
5553	1		dispatch[EXACT][POSIXU] = compare_exact_posix;
5554	1		dispatch[EXACTF][POSIXU] = compare_exact_posix;
5555	1		dispatch[EXACTFU][POSIXU] = compare_exact_posix;
5556	1		dispatch[NOTHING][POSIXU] = compare_left_tail;
5557	1		dispatch[TAIL][POSIXU] = compare_left_tail;
5558	1		dispatch[STAR][POSIXU] = compare_mismatch;
5559	1		dispatch[PLUS][POSIXU] = compare_left_plus;
5560	1		dispatch[CURLY][POSIXU] = compare_left_curly;
5561	1		dispatch[CURLYM][POSIXU] = compare_left_curly;
5562	1		dispatch[CURLYX][POSIXU] = compare_left_curly;
5563	1		dispatch[OPEN][POSIXU] = compare_left_open;
5564	1		dispatch[CLOSE][POSIXU] = compare_left_tail;
5565	1		dispatch[IFMATCH][POSIXU] = compare_after_assertion;
5566	1		dispatch[UNLESSM][POSIXU] = compare_after_assertion;
5567	1		dispatch[MINMOD][POSIXU] = compare_left_tail;
5568	1		dispatch[LNBREAK][POSIXU] = compare_mismatch;
5569	1		dispatch[OPTIMIZED][POSIXU] = compare_left_tail;
5570
5571	1		dispatch[SUCCEED][POSIXA] = compare_left_tail;
5572	1		dispatch[MBOL][POSIXA] = compare_bol;
5573	1		dispatch[SBOL][POSIXA] = compare_bol;
5574	1		dispatch[BOUND][POSIXA] = compare_mismatch;
5575	1		dispatch[NBOUND][POSIXA] = compare_mismatch;
5576	1		dispatch[REG_ANY][POSIXA] = compare_mismatch;
5577	1		dispatch[SANY][POSIXA] = compare_mismatch;
5578	1		dispatch[ANYOF][POSIXA] = compare_anyof_posixa;
5579	1		dispatch[ANYOFD][POSIXA] = compare_anyof_posixa;
5580			#ifdef RC_ANYOFM
5581			dispatch[ANYOFM][POSIXA] = compare_anyofm_posix;
5582			#endif
5583			#ifdef RC_NANYOFM
5584			dispatch[NANYOFM][POSIXA] = compare_nanyofm_posix;
5585			#endif
5586	1		dispatch[POSIXD][POSIXA] = compare_mismatch;
5587	1		dispatch[POSIXU][POSIXA] = compare_mismatch;
5588	1		dispatch[POSIXA][POSIXA] = compare_posix_posix;
5589	1		dispatch[NPOSIXD][POSIXA] = compare_mismatch;
5590	1		dispatch[NPOSIXU][POSIXA] = compare_mismatch;
5591	1		dispatch[NPOSIXA][POSIXA] = compare_mismatch;
5592	1		dispatch[BRANCH][POSIXA] = compare_left_branch;
5593	1		dispatch[EXACT][POSIXA] = compare_exact_posix;
5594	1		dispatch[EXACTF][POSIXA] = compare_exact_posix;
5595	1		dispatch[EXACTFU][POSIXA] = compare_exact_posix;
5596	1		dispatch[NOTHING][POSIXA] = compare_left_tail;
5597	1		dispatch[STAR][POSIXA] = compare_mismatch;
5598	1		dispatch[PLUS][POSIXA] = compare_left_plus;
5599	1		dispatch[CURLY][POSIXA] = compare_left_curly;
5600	1		dispatch[CURLYM][POSIXA] = compare_left_curly;
5601	1		dispatch[CURLYX][POSIXA] = compare_left_curly;
5602	1		dispatch[OPEN][POSIXA] = compare_left_open;
5603	1		dispatch[CLOSE][POSIXA] = compare_left_tail;
5604	1		dispatch[IFMATCH][POSIXA] = compare_after_assertion;
5605	1		dispatch[UNLESSM][POSIXA] = compare_after_assertion;
5606	1		dispatch[MINMOD][POSIXA] = compare_left_tail;
5607	1		dispatch[LNBREAK][POSIXA] = compare_mismatch;
5608	1		dispatch[OPTIMIZED][POSIXA] = compare_left_tail;
5609
5610	1		dispatch[SUCCEED][NPOSIXD] = compare_left_tail;
5611	1		dispatch[MBOL][NPOSIXD] = compare_bol;
5612	1		dispatch[SBOL][NPOSIXD] = compare_bol;
5613	1		dispatch[BOUND][NPOSIXD] = compare_mismatch;
5614	1		dispatch[NBOUND][NPOSIXD] = compare_mismatch;
5615	1		dispatch[REG_ANY][NPOSIXD] = compare_mismatch;
5616	1		dispatch[SANY][NPOSIXD] = compare_mismatch;
5617	1		dispatch[ANYOF][NPOSIXD] = compare_anyof_negative_posix;
5618	1		dispatch[ANYOFD][NPOSIXD] = compare_anyof_negative_posix;
5619			#ifdef RC_ANYOFM
5620			dispatch[ANYOFM][NPOSIXD] = compare_anyofm_negative_posix;
5621			#endif
5622			#ifdef RC_NANYOFM
5623			dispatch[NANYOFM][NPOSIXD] = compare_nanyofm_negative_posix;
5624			#endif
5625	1		dispatch[POSIXD][NPOSIXD] = compare_posix_negative_posix;
5626	1		dispatch[POSIXU][NPOSIXD] = compare_posix_negative_posix;
5627	1		dispatch[POSIXA][NPOSIXD] = compare_posix_negative_posix;
5628	1		dispatch[NPOSIXD][NPOSIXD] = compare_negative_posix_negative_posix;
5629	1		dispatch[NPOSIXU][NPOSIXD] = compare_negative_posix_negative_posix;
5630	1		dispatch[NPOSIXA][NPOSIXD] = compare_mismatch;
5631	1		dispatch[BRANCH][NPOSIXD] = compare_left_branch;
5632	1		dispatch[EXACT][NPOSIXD] = compare_exact_negative_posix;
5633	1		dispatch[EXACTF][NPOSIXD] = compare_exactf_negative_posix;
5634	1		dispatch[EXACTFU][NPOSIXD] = compare_exactf_negative_posix;
5635	1		dispatch[NOTHING][NPOSIXD] = compare_left_tail;
5636	1		dispatch[STAR][NPOSIXD] = compare_mismatch;
5637	1		dispatch[PLUS][NPOSIXD] = compare_left_plus;
5638	1		dispatch[CURLY][NPOSIXD] = compare_left_curly;
5639	1		dispatch[CURLYM][NPOSIXD] = compare_left_curly;
5640	1		dispatch[CURLYX][NPOSIXD] = compare_left_curly;
5641	1		dispatch[OPEN][NPOSIXD] = compare_left_open;
5642	1		dispatch[CLOSE][NPOSIXD] = compare_left_tail;
5643	1		dispatch[IFMATCH][NPOSIXD] = compare_after_assertion;
5644	1		dispatch[UNLESSM][NPOSIXD] = compare_after_assertion;
5645	1		dispatch[MINMOD][NPOSIXD] = compare_left_tail;
5646	1		dispatch[LNBREAK][NPOSIXD] = compare_mismatch;
5647	1		dispatch[OPTIMIZED][NPOSIXD] = compare_left_tail;
5648
5649	1		dispatch[SUCCEED][NPOSIXU] = compare_left_tail;
5650	1		dispatch[MBOL][NPOSIXU] = compare_bol;
5651	1		dispatch[SBOL][NPOSIXU] = compare_bol;
5652	1		dispatch[BOUND][NPOSIXU] = compare_mismatch;
5653	1		dispatch[NBOUND][NPOSIXU] = compare_mismatch;
5654	1		dispatch[REG_ANY][NPOSIXU] = compare_mismatch;
5655	1		dispatch[SANY][NPOSIXU] = compare_mismatch;
5656	1		dispatch[ANYOF][NPOSIXU] = compare_anyof_negative_posix;
5657	1		dispatch[ANYOFD][NPOSIXU] = compare_anyof_negative_posix;
5658			#ifdef RC_ANYOFM
5659			dispatch[ANYOFM][NPOSIXU] = compare_anyofm_negative_posix;
5660			#endif
5661			#ifdef RC_NANYOFM
5662			dispatch[NANYOFM][NPOSIXU] = compare_nanyofm_negative_posix;
5663			#endif
5664	1		dispatch[POSIXD][NPOSIXU] = compare_posix_negative_posix;
5665	1		dispatch[POSIXU][NPOSIXU] = compare_posix_negative_posix;
5666	1		dispatch[POSIXA][NPOSIXU] = compare_posix_negative_posix;
5667	1		dispatch[NPOSIXD][NPOSIXU] = compare_negative_posix_negative_posix;
5668	1		dispatch[NPOSIXU][NPOSIXU] = compare_negative_posix_negative_posix;
5669	1		dispatch[NPOSIXA][NPOSIXU] = compare_mismatch;
5670	1		dispatch[BRANCH][NPOSIXU] = compare_left_branch;
5671	1		dispatch[EXACT][NPOSIXU] = compare_exact_negative_posix;
5672	1		dispatch[EXACTF][NPOSIXU] = compare_exactf_negative_posix;
5673	1		dispatch[EXACTFU][NPOSIXU] = compare_exactf_negative_posix;
5674	1		dispatch[NOTHING][NPOSIXU] = compare_left_tail;
5675	1		dispatch[STAR][NPOSIXU] = compare_mismatch;
5676	1		dispatch[PLUS][NPOSIXU] = compare_left_plus;
5677	1		dispatch[CURLY][NPOSIXU] = compare_left_curly;
5678	1		dispatch[CURLYM][NPOSIXU] = compare_left_curly;
5679	1		dispatch[CURLYX][NPOSIXU] = compare_left_curly;
5680	1		dispatch[OPEN][NPOSIXU] = compare_left_open;
5681	1		dispatch[CLOSE][NPOSIXU] = compare_left_tail;
5682	1		dispatch[IFMATCH][NPOSIXU] = compare_after_assertion;
5683	1		dispatch[UNLESSM][NPOSIXU] = compare_after_assertion;
5684	1		dispatch[MINMOD][NPOSIXU] = compare_left_tail;
5685	1		dispatch[LNBREAK][NPOSIXU] = compare_mismatch;
5686	1		dispatch[OPTIMIZED][NPOSIXU] = compare_left_tail;
5687
5688	1		dispatch[SUCCEED][NPOSIXA] = compare_left_tail;
5689	1		dispatch[MBOL][NPOSIXA] = compare_bol;
5690	1		dispatch[SBOL][NPOSIXA] = compare_bol;
5691	1		dispatch[BOUND][NPOSIXA] = compare_mismatch;
5692	1		dispatch[NBOUND][NPOSIXA] = compare_mismatch;
5693	1		dispatch[REG_ANY][NPOSIXA] = compare_mismatch;
5694	1		dispatch[SANY][NPOSIXA] = compare_mismatch;
5695	1		dispatch[ANYOF][NPOSIXA] = compare_anyof_negative_posix;
5696	1		dispatch[ANYOFD][NPOSIXA] = compare_anyof_negative_posix;
5697			#ifdef RC_ANYOFM
5698			dispatch[ANYOFM][NPOSIXA] = compare_anyofm_negative_posix;
5699			#endif
5700			#ifdef RC_NANYOFM
5701			dispatch[NANYOFM][NPOSIXA] = compare_nanyofm_negative_posix;
5702			#endif
5703	1		dispatch[POSIXD][NPOSIXA] = compare_posix_negative_posix;
5704	1		dispatch[POSIXU][NPOSIXA] = compare_posix_negative_posix;
5705	1		dispatch[POSIXA][NPOSIXA] = compare_posix_negative_posix;
5706	1		dispatch[NPOSIXD][NPOSIXA] = compare_negative_posix_negative_posix;
5707	1		dispatch[NPOSIXU][NPOSIXA] = compare_negative_posix_negative_posix;
5708	1		dispatch[NPOSIXA][NPOSIXA] = compare_negative_posix_negative_posix;
5709	1		dispatch[BRANCH][NPOSIXA] = compare_left_branch;
5710	1		dispatch[EXACT][NPOSIXA] = compare_exact_negative_posix;
5711	1		dispatch[EXACTF][NPOSIXA] = compare_exactf_negative_posix;
5712	1		dispatch[EXACTFU][NPOSIXA] = compare_exactf_negative_posix;
5713	1		dispatch[NOTHING][NPOSIXA] = compare_left_tail;
5714	1		dispatch[STAR][NPOSIXA] = compare_mismatch;
5715	1		dispatch[PLUS][NPOSIXA] = compare_left_plus;
5716	1		dispatch[CURLY][NPOSIXA] = compare_left_curly;
5717	1		dispatch[CURLYM][NPOSIXA] = compare_left_curly;
5718	1		dispatch[CURLYX][NPOSIXA] = compare_left_curly;
5719	1		dispatch[OPEN][NPOSIXA] = compare_left_open;
5720	1		dispatch[CLOSE][NPOSIXA] = compare_left_tail;
5721	1		dispatch[IFMATCH][NPOSIXA] = compare_after_assertion;
5722	1		dispatch[UNLESSM][NPOSIXA] = compare_after_assertion;
5723	1		dispatch[MINMOD][NPOSIXA] = compare_left_tail;
5724	1		dispatch[LNBREAK][NPOSIXA] = compare_mismatch;
5725	1		dispatch[OPTIMIZED][NPOSIXA] = compare_left_tail;
5726
5727	93	100	for (i = 0; i < REGNODE_MAX; ++i)
5728			{
5729	92		dispatch[i][BRANCH] = compare_right_branch;
5730			}
5731
5732	1		dispatch[SUCCEED][BRANCH] = compare_left_tail;
5733	1		dispatch[ANYOF][BRANCH] = compare_anyof_branch;
5734	1		dispatch[ANYOFD][BRANCH] = compare_anyof_branch;
5735			#ifdef RC_ANYOFM
5736			dispatch[ANYOFM][BRANCH] = compare_anyofm_branch;
5737			#endif
5738	1		dispatch[BRANCH][BRANCH] = compare_left_branch;
5739	1		dispatch[NOTHING][BRANCH] = compare_left_tail;
5740	1		dispatch[TAIL][BRANCH] = compare_left_tail;
5741	1		dispatch[WHILEM][BRANCH] = compare_left_tail;
5742	1		dispatch[OPEN][BRANCH] = compare_left_open;
5743	1		dispatch[CLOSE][BRANCH] = compare_left_tail;
5744	1		dispatch[IFMATCH][BRANCH] = compare_after_assertion;
5745	1		dispatch[UNLESSM][BRANCH] = compare_after_assertion;
5746	1		dispatch[MINMOD][BRANCH] = compare_left_tail;
5747	1		dispatch[OPTIMIZED][BRANCH] = compare_left_tail;
5748
5749	1		dispatch[SUCCEED][EXACT] = compare_left_tail;
5750	1		dispatch[MBOL][EXACT] = compare_bol;
5751	1		dispatch[SBOL][EXACT] = compare_bol;
5752	1		dispatch[BOUND][EXACT] = compare_mismatch;
5753	1		dispatch[NBOUND][EXACT] = compare_mismatch;
5754	1		dispatch[REG_ANY][EXACT] = compare_mismatch;
5755	1		dispatch[SANY][EXACT] = compare_mismatch;
5756	1		dispatch[ANYOF][EXACT] = compare_anyof_exact;
5757	1		dispatch[ANYOFD][EXACT] = compare_anyof_exact;
5758			#ifdef RC_ANYOFM
5759			dispatch[ANYOFM][EXACT] = compare_anyofm_exact;
5760			#endif
5761			#ifdef RC_NANYOFM
5762			dispatch[NANYOFM][EXACT] = compare_mismatch;
5763			#endif
5764	1		dispatch[POSIXD][EXACT] = compare_mismatch;
5765	1		dispatch[POSIXU][EXACT] = compare_mismatch;
5766	1		dispatch[POSIXA][EXACT] = compare_mismatch;
5767	1		dispatch[NPOSIXD][EXACT] = compare_mismatch;
5768	1		dispatch[NPOSIXU][EXACT] = compare_mismatch;
5769	1		dispatch[NPOSIXA][EXACT] = compare_mismatch;
5770	1		dispatch[BRANCH][EXACT] = compare_left_branch;
5771	1		dispatch[EXACT][EXACT] = compare_exact_exact;
5772	1		dispatch[EXACTF][EXACT] = compare_exactf_exact;
5773	1		dispatch[EXACTFU][EXACT] = compare_exactf_exact;
5774	1		dispatch[NOTHING][EXACT] = compare_left_tail;
5775	1		dispatch[TAIL][EXACT] = compare_left_tail;
5776	1		dispatch[STAR][EXACT] = compare_mismatch;
5777	1		dispatch[PLUS][EXACT] = compare_left_plus;
5778	1		dispatch[CURLY][EXACT] = compare_left_curly;
5779	1		dispatch[CURLYM][EXACT] = compare_left_curly;
5780	1		dispatch[CURLYX][EXACT] = compare_left_curly;
5781	1		dispatch[WHILEM][EXACT] = compare_left_tail;
5782	1		dispatch[OPEN][EXACT] = compare_left_open;
5783	1		dispatch[CLOSE][EXACT] = compare_left_tail;
5784	1		dispatch[IFMATCH][EXACT] = compare_after_assertion;
5785	1		dispatch[UNLESSM][EXACT] = compare_after_assertion;
5786	1		dispatch[MINMOD][EXACT] = compare_left_tail;
5787	1		dispatch[LNBREAK][EXACT] = compare_mismatch;
5788	1		dispatch[OPTIMIZED][EXACT] = compare_left_tail;
5789
5790	1		dispatch[SUCCEED][EXACTF] = compare_left_tail;
5791	1		dispatch[MBOL][EXACTF] = compare_bol;
5792	1		dispatch[SBOL][EXACTF] = compare_bol;
5793	1		dispatch[BOUND][EXACTF] = compare_mismatch;
5794	1		dispatch[NBOUND][EXACTF] = compare_mismatch;
5795	1		dispatch[REG_ANY][EXACTF] = compare_mismatch;
5796	1		dispatch[SANY][EXACTF] = compare_mismatch;
5797	1		dispatch[ANYOF][EXACTF] = compare_anyof_exactf;
5798	1		dispatch[ANYOFD][EXACTF] = compare_anyof_exactf;
5799			#ifdef RC_ANYOFM
5800			dispatch[ANYOFM][EXACTF] = compare_anyofm_exactf;
5801			#endif
5802			#ifdef RC_NANYOFM
5803			dispatch[NANYOFM][EXACTF] = compare_mismatch;
5804			#endif
5805	1		dispatch[POSIXD][EXACTF] = compare_mismatch;
5806	1		dispatch[POSIXU][EXACTF] = compare_mismatch;
5807	1		dispatch[POSIXA][EXACTF] = compare_mismatch;
5808	1		dispatch[NPOSIXD][EXACTF] = compare_mismatch;
5809	1		dispatch[NPOSIXU][EXACTF] = compare_mismatch;
5810	1		dispatch[NPOSIXA][EXACTF] = compare_mismatch;
5811	1		dispatch[BRANCH][EXACTF] = compare_left_branch;
5812	1		dispatch[EXACT][EXACTF] = compare_exact_exactf;
5813	1		dispatch[EXACTF][EXACTF] = compare_exactf_exactf;
5814	1		dispatch[NOTHING][EXACTF] = compare_left_tail;
5815	1		dispatch[TAIL][EXACTF] = compare_left_tail;
5816	1		dispatch[STAR][EXACTF] = compare_mismatch;
5817	1		dispatch[PLUS][EXACTF] = compare_left_plus;
5818	1		dispatch[CURLY][EXACTF] = compare_left_curly;
5819	1		dispatch[CURLYM][EXACTF] = compare_left_curly;
5820	1		dispatch[CURLYX][EXACTF] = compare_left_curly;
5821	1		dispatch[WHILEM][EXACTF] = compare_left_tail;
5822	1		dispatch[OPEN][EXACTF] = compare_left_open;
5823	1		dispatch[CLOSE][EXACTF] = compare_left_tail;
5824	1		dispatch[IFMATCH][EXACTF] = compare_after_assertion;
5825	1		dispatch[UNLESSM][EXACTF] = compare_after_assertion;
5826	1		dispatch[MINMOD][EXACTF] = compare_left_tail;
5827	1		dispatch[LNBREAK][EXACTF] = compare_mismatch;
5828	1		dispatch[OPTIMIZED][EXACTF] = compare_left_tail;
5829
5830	1		dispatch[SUCCEED][EXACTFU] = compare_left_tail;
5831	1		dispatch[MBOL][EXACTFU] = compare_bol;
5832	1		dispatch[SBOL][EXACTFU] = compare_bol;
5833	1		dispatch[BOUND][EXACTFU] = compare_mismatch;
5834	1		dispatch[NBOUND][EXACTFU] = compare_mismatch;
5835	1		dispatch[REG_ANY][EXACTFU] = compare_mismatch;
5836	1		dispatch[SANY][EXACTFU] = compare_mismatch;
5837	1		dispatch[ANYOF][EXACTFU] = compare_anyof_exactf;
5838	1		dispatch[ANYOFD][EXACTFU] = compare_anyof_exactf;
5839			#ifdef RC_ANYOFM
5840			dispatch[ANYOFM][EXACTFU] = compare_anyofm_exactf;
5841			#endif
5842			#ifdef RC_NANYOFM
5843			dispatch[NANYOFM][EXACTFU] = compare_mismatch;
5844			#endif
5845	1		dispatch[POSIXD][EXACTFU] = compare_mismatch;
5846	1		dispatch[POSIXU][EXACTFU] = compare_mismatch;
5847	1		dispatch[POSIXA][EXACTFU] = compare_mismatch;
5848	1		dispatch[NPOSIXD][EXACTFU] = compare_mismatch;
5849	1		dispatch[NPOSIXU][EXACTFU] = compare_mismatch;
5850	1		dispatch[NPOSIXA][EXACTFU] = compare_mismatch;
5851	1		dispatch[BRANCH][EXACTFU] = compare_left_branch;
5852	1		dispatch[EXACT][EXACTFU] = compare_exact_exactf;
5853	1		dispatch[EXACTF][EXACTFU] = compare_exactf_exactf;
5854	1		dispatch[EXACTFU][EXACTFU] = compare_exactf_exactf;
5855	1		dispatch[NOTHING][EXACTFU] = compare_left_tail;
5856	1		dispatch[STAR][EXACTFU] = compare_mismatch;
5857	1		dispatch[PLUS][EXACTFU] = compare_left_plus;
5858	1		dispatch[CURLY][EXACTFU] = compare_left_curly;
5859	1		dispatch[CURLYM][EXACTFU] = compare_left_curly;
5860	1		dispatch[CURLYX][EXACTFU] = compare_left_curly;
5861	1		dispatch[OPEN][EXACTFU] = compare_left_open;
5862	1		dispatch[CLOSE][EXACTFU] = compare_left_tail;
5863	1		dispatch[IFMATCH][EXACTFU] = compare_after_assertion;
5864	1		dispatch[UNLESSM][EXACTFU] = compare_after_assertion;
5865	1		dispatch[MINMOD][EXACTFU] = compare_left_tail;
5866	1		dispatch[LNBREAK][EXACTFU] = compare_mismatch;
5867	1		dispatch[OPTIMIZED][EXACTFU] = compare_left_tail;
5868
5869			#ifdef RC_EXACT_ONLY8
5870			dispatch[EXACT_ONLY8][EXACT_ONLY8] = compare_exact_exact;
5871			#endif
5872
5873	93	100	for (i = 0; i < REGNODE_MAX; ++i)
5874			{
5875	92		dispatch[i][NOTHING] = compare_next;
5876			}
5877
5878	1		dispatch[SUCCEED][NOTHING] = compare_tails;
5879	1		dispatch[NOTHING][NOTHING] = compare_tails;
5880	1		dispatch[TAIL][NOTHING] = compare_tails;
5881	1		dispatch[WHILEM][NOTHING] = compare_tails;
5882	1		dispatch[CLOSE][NOTHING] = compare_tails;
5883	1		dispatch[MINMOD][NOTHING] = compare_tails;
5884	1		dispatch[OPTIMIZED][NOTHING] = compare_tails;
5885
5886	93	100	for (i = 0; i < REGNODE_MAX; ++i)
5887			{
5888	92		dispatch[i][TAIL] = compare_next;
5889			}
5890
5891	1		dispatch[SUCCEED][TAIL] = compare_tails;
5892	1		dispatch[NOTHING][TAIL] = compare_tails;
5893	1		dispatch[TAIL][TAIL] = compare_tails;
5894	1		dispatch[WHILEM][TAIL] = compare_tails;
5895	1		dispatch[CLOSE][TAIL] = compare_tails;
5896	1		dispatch[MINMOD][TAIL] = compare_tails;
5897	1		dispatch[OPTIMIZED][TAIL] = compare_tails;
5898
5899	93	100	for (i = 0; i < REGNODE_MAX; ++i)
5900			{
5901	92		dispatch[i][STAR] = compare_right_star;
5902			}
5903
5904	1		dispatch[SUCCEED][STAR] = compare_left_tail;
5905	1		dispatch[EOS][STAR] = compare_tails;
5906	1		dispatch[EOL][STAR] = compare_tails;
5907	1		dispatch[MEOL][STAR] = compare_tails;
5908	1		dispatch[SEOL][STAR] = compare_tails;
5909	1		dispatch[NOTHING][STAR] = compare_left_tail;
5910	1		dispatch[TAIL][STAR] = compare_left_tail;
5911	1		dispatch[STAR][STAR] = compare_repeat_star;
5912	1		dispatch[PLUS][STAR] = compare_repeat_star;
5913	1		dispatch[CURLY][STAR] = compare_curly_star;
5914	1		dispatch[CURLYM][STAR] = compare_curly_star;
5915	1		dispatch[CURLYX][STAR] = compare_curly_star;
5916	1		dispatch[WHILEM][STAR] = compare_left_tail;
5917	1		dispatch[OPEN][STAR] = compare_left_open;
5918	1		dispatch[CLOSE][STAR] = compare_left_tail;
5919	1		dispatch[IFMATCH][STAR] = compare_after_assertion;
5920	1		dispatch[UNLESSM][STAR] = compare_after_assertion;
5921	1		dispatch[MINMOD][STAR] = compare_left_tail;
5922	1		dispatch[OPTIMIZED][STAR] = compare_left_tail;
5923
5924	93	100	for (i = 0; i < REGNODE_MAX; ++i)
5925			{
5926	92		dispatch[i][PLUS] = compare_right_plus;
5927			}
5928
5929	1		dispatch[SUCCEED][PLUS] = compare_left_tail;
5930	1		dispatch[NOTHING][PLUS] = compare_left_tail;
5931	1		dispatch[TAIL][PLUS] = compare_left_tail;
5932	1		dispatch[PLUS][PLUS] = compare_plus_plus;
5933	1		dispatch[CURLY][PLUS] = compare_curly_plus;
5934	1		dispatch[CURLYM][PLUS] = compare_curly_plus;
5935	1		dispatch[CURLYX][PLUS] = compare_curly_plus;
5936	1		dispatch[WHILEM][PLUS] = compare_left_tail;
5937	1		dispatch[OPEN][PLUS] = compare_left_open;
5938	1		dispatch[CLOSE][PLUS] = compare_left_tail;
5939	1		dispatch[IFMATCH][PLUS] = compare_after_assertion;
5940	1		dispatch[UNLESSM][PLUS] = compare_after_assertion;
5941	1		dispatch[MINMOD][PLUS] = compare_left_tail;
5942	1		dispatch[OPTIMIZED][PLUS] = compare_left_tail;
5943
5944	93	100	for (i = 0; i < REGNODE_MAX; ++i)
5945			{
5946	92		dispatch[i][CURLY] = compare_right_curly;
5947			}
5948
5949	1		dispatch[SUCCEED][CURLY] = compare_left_tail;
5950	1		dispatch[NOTHING][CURLY] = compare_left_tail;
5951	1		dispatch[TAIL][CURLY] = compare_left_tail;
5952	1		dispatch[PLUS][CURLY] = compare_plus_curly;
5953	1		dispatch[CURLY][CURLY] = compare_curly_curly;
5954	1		dispatch[CURLYM][CURLY] = compare_curly_curly;
5955	1		dispatch[CURLYX][CURLY] = compare_curly_curly;
5956	1		dispatch[WHILEM][CURLY] = compare_left_tail;
5957	1		dispatch[OPEN][CURLY] = compare_left_open;
5958	1		dispatch[CLOSE][CURLY] = compare_left_tail;
5959	1		dispatch[IFMATCH][CURLY] = compare_after_assertion;
5960	1		dispatch[UNLESSM][CURLY] = compare_after_assertion;
5961	1		dispatch[SUSPEND][CURLY] = compare_suspend_curly;
5962	1		dispatch[MINMOD][CURLY] = compare_left_tail;
5963	1		dispatch[OPTIMIZED][CURLY] = compare_left_tail;
5964
5965	93	100	for (i = 0; i < REGNODE_MAX; ++i)
5966			{
5967	92		dispatch[i][CURLYM] = compare_right_curly;
5968			}
5969
5970	1		dispatch[SUCCEED][CURLYM] = compare_left_tail;
5971	1		dispatch[NOTHING][CURLYM] = compare_left_tail;
5972	1		dispatch[TAIL][CURLYM] = compare_left_tail;
5973	1		dispatch[PLUS][CURLYM] = compare_plus_curly;
5974	1		dispatch[CURLY][CURLYM] = compare_curly_curly;
5975	1		dispatch[CURLYM][CURLYM] = compare_curly_curly;
5976	1		dispatch[CURLYX][CURLYM] = compare_curly_curly;
5977	1		dispatch[WHILEM][CURLYM] = compare_left_tail;
5978	1		dispatch[OPEN][CURLYM] = compare_left_open;
5979	1		dispatch[CLOSE][CURLYM] = compare_left_tail;
5980	1		dispatch[IFMATCH][CURLYM] = compare_after_assertion;
5981	1		dispatch[UNLESSM][CURLYM] = compare_after_assertion;
5982	1		dispatch[SUSPEND][CURLYM] = compare_suspend_curly;
5983	1		dispatch[MINMOD][CURLYM] = compare_left_tail;
5984	1		dispatch[OPTIMIZED][CURLYM] = compare_left_tail;
5985
5986	93	100	for (i = 0; i < REGNODE_MAX; ++i)
5987			{
5988	92		dispatch[i][CURLYX] = compare_right_curly;
5989			}
5990
5991	1		dispatch[SUCCEED][CURLYX] = compare_left_tail;
5992	1		dispatch[NOTHING][CURLYX] = compare_left_tail;
5993	1		dispatch[TAIL][CURLYX] = compare_left_tail;
5994	1		dispatch[PLUS][CURLYX] = compare_plus_curly;
5995	1		dispatch[CURLY][CURLYX] = compare_curly_curly;
5996	1		dispatch[CURLYM][CURLYX] = compare_curly_curly;
5997	1		dispatch[CURLYX][CURLYX] = compare_curly_curly;
5998	1		dispatch[WHILEM][CURLYX] = compare_left_tail;
5999	1		dispatch[OPEN][CURLYX] = compare_left_open;
6000	1		dispatch[CLOSE][CURLYX] = compare_left_tail;
6001	1		dispatch[IFMATCH][CURLYX] = compare_after_assertion;
6002	1		dispatch[UNLESSM][CURLYX] = compare_after_assertion;
6003	1		dispatch[SUSPEND][CURLYX] = compare_suspend_curly;
6004	1		dispatch[MINMOD][CURLYX] = compare_left_tail;
6005	1		dispatch[OPTIMIZED][CURLYX] = compare_left_tail;
6006
6007	93	100	for (i = 0; i < REGNODE_MAX; ++i)
6008			{
6009	92		dispatch[i][WHILEM] = compare_next;
6010			}
6011
6012	1		dispatch[SUCCEED][WHILEM] = compare_tails;
6013	1		dispatch[NOTHING][WHILEM] = compare_tails;
6014	1		dispatch[TAIL][WHILEM] = compare_tails;
6015	1		dispatch[WHILEM][WHILEM] = compare_tails;
6016	1		dispatch[CLOSE][WHILEM] = compare_tails;
6017	1		dispatch[MINMOD][WHILEM] = compare_tails;
6018	1		dispatch[OPTIMIZED][WHILEM] = compare_tails;
6019
6020	93	100	for (i = 0; i < REGNODE_MAX; ++i)
6021			{
6022	92		dispatch[i][OPEN] = compare_right_open;
6023			}
6024
6025	1		dispatch[OPEN][OPEN] = compare_open_open;
6026
6027	93	100	for (i = 0; i < REGNODE_MAX; ++i)
6028			{
6029	92		dispatch[i][CLOSE] = compare_next;
6030			}
6031
6032	1		dispatch[SUCCEED][CLOSE] = compare_tails;
6033	1		dispatch[NOTHING][CLOSE] = compare_tails;
6034	1		dispatch[TAIL][CLOSE] = compare_tails;
6035	1		dispatch[WHILEM][CLOSE] = compare_tails;
6036	1		dispatch[CLOSE][CLOSE] = compare_tails;
6037	1		dispatch[MINMOD][CLOSE] = compare_tails;
6038	1		dispatch[OPTIMIZED][CLOSE] = compare_tails;
6039
6040	1		dispatch[SUCCEED][IFMATCH] = compare_left_tail;
6041	1		dispatch[MBOL][IFMATCH] = compare_bol;
6042	1		dispatch[SBOL][IFMATCH] = compare_bol;
6043	1		dispatch[BOUND][IFMATCH] = compare_mismatch;
6044	1		dispatch[NBOUND][IFMATCH] = compare_mismatch;
6045	1		dispatch[REG_ANY][IFMATCH] = compare_mismatch;
6046	1		dispatch[SANY][IFMATCH] = compare_mismatch;
6047	1		dispatch[ANYOF][IFMATCH] = compare_mismatch;
6048	1		dispatch[ANYOFD][IFMATCH] = compare_mismatch;
6049			#ifdef RC_ANYOFM
6050			dispatch[ANYOFM][IFMATCH] = compare_mismatch;
6051			#endif
6052			#ifdef RC_NANYOFM
6053			dispatch[NANYOFM][IFMATCH] = compare_mismatch;
6054			#endif
6055	1		dispatch[POSIXD][IFMATCH] = compare_mismatch;
6056	1		dispatch[POSIXU][IFMATCH] = compare_mismatch;
6057	1		dispatch[POSIXA][IFMATCH] = compare_mismatch;
6058	1		dispatch[NPOSIXD][IFMATCH] = compare_mismatch;
6059	1		dispatch[NPOSIXU][IFMATCH] = compare_mismatch;
6060	1		dispatch[NPOSIXA][IFMATCH] = compare_mismatch;
6061	1		dispatch[BRANCH][IFMATCH] = compare_mismatch;
6062	1		dispatch[EXACT][IFMATCH] = compare_mismatch;
6063	1		dispatch[EXACTF][IFMATCH] = compare_mismatch;
6064	1		dispatch[EXACTFU][IFMATCH] = compare_mismatch;
6065	1		dispatch[NOTHING][IFMATCH] = compare_left_tail;
6066	1		dispatch[TAIL][IFMATCH] = compare_left_tail;
6067	1		dispatch[STAR][IFMATCH] = compare_mismatch;
6068	1		dispatch[PLUS][IFMATCH] = compare_mismatch;
6069	1		dispatch[CURLY][IFMATCH] = compare_mismatch;
6070	1		dispatch[CURLYM][IFMATCH] = compare_mismatch;
6071	1		dispatch[CURLYX][IFMATCH] = compare_mismatch;
6072	1		dispatch[WHILEM][IFMATCH] = compare_left_tail;
6073	1		dispatch[OPEN][IFMATCH] = compare_left_open;
6074	1		dispatch[CLOSE][IFMATCH] = compare_left_tail;
6075	1		dispatch[IFMATCH][IFMATCH] = compare_positive_assertions;
6076	1		dispatch[UNLESSM][IFMATCH] = compare_mismatch;
6077	1		dispatch[MINMOD][IFMATCH] = compare_left_tail;
6078	1		dispatch[LNBREAK][IFMATCH] = compare_mismatch;
6079	1		dispatch[OPTIMIZED][IFMATCH] = compare_left_tail;
6080
6081	1		dispatch[SUCCEED][UNLESSM] = compare_left_tail;
6082	1		dispatch[MBOL][UNLESSM] = compare_bol;
6083	1		dispatch[SBOL][UNLESSM] = compare_bol;
6084	1		dispatch[BOUND][UNLESSM] = compare_mismatch;
6085	1		dispatch[NBOUND][UNLESSM] = compare_mismatch;
6086	1		dispatch[REG_ANY][UNLESSM] = compare_mismatch;
6087	1		dispatch[SANY][UNLESSM] = compare_mismatch;
6088	1		dispatch[ANYOF][UNLESSM] = compare_mismatch;
6089	1		dispatch[ANYOFD][UNLESSM] = compare_mismatch;
6090			#ifdef RC_ANYOFM
6091			dispatch[ANYOFM][UNLESSM] = compare_mismatch;
6092			#endif
6093			#ifdef RC_NANYOFM
6094			dispatch[NANYOFM][UNLESSM] = compare_mismatch;
6095			#endif
6096	1		dispatch[POSIXD][UNLESSM] = compare_mismatch;
6097	1		dispatch[POSIXU][UNLESSM] = compare_mismatch;
6098	1		dispatch[POSIXA][UNLESSM] = compare_mismatch;
6099	1		dispatch[NPOSIXD][UNLESSM] = compare_mismatch;
6100	1		dispatch[NPOSIXU][UNLESSM] = compare_mismatch;
6101	1		dispatch[NPOSIXA][UNLESSM] = compare_mismatch;
6102	1		dispatch[BRANCH][UNLESSM] = compare_mismatch;
6103	1		dispatch[EXACT][UNLESSM] = compare_mismatch;
6104	1		dispatch[EXACTF][UNLESSM] = compare_mismatch;
6105	1		dispatch[EXACTFU][UNLESSM] = compare_mismatch;
6106	1		dispatch[NOTHING][UNLESSM] = compare_left_tail;
6107	1		dispatch[TAIL][UNLESSM] = compare_left_tail;
6108	1		dispatch[STAR][UNLESSM] = compare_mismatch;
6109	1		dispatch[PLUS][UNLESSM] = compare_mismatch;
6110	1		dispatch[CURLY][UNLESSM] = compare_mismatch;
6111	1		dispatch[CURLYM][UNLESSM] = compare_mismatch;
6112	1		dispatch[CURLYX][UNLESSM] = compare_mismatch;
6113	1		dispatch[WHILEM][UNLESSM] = compare_left_tail;
6114	1		dispatch[OPEN][UNLESSM] = compare_left_open;
6115	1		dispatch[CLOSE][UNLESSM] = compare_left_tail;
6116	1		dispatch[IFMATCH][UNLESSM] = compare_mismatch;
6117	1		dispatch[UNLESSM][UNLESSM] = compare_negative_assertions;
6118	1		dispatch[MINMOD][UNLESSM] = compare_left_tail;
6119	1		dispatch[LNBREAK][UNLESSM] = compare_mismatch;
6120	1		dispatch[OPTIMIZED][UNLESSM] = compare_left_tail;
6121
6122	1		dispatch[SUSPEND][SUSPEND] = compare_subexpressions;
6123
6124	93	100	for (i = 0; i < REGNODE_MAX; ++i)
6125			{
6126	92		dispatch[i][MINMOD] = compare_next;
6127			}
6128
6129	1		dispatch[SUCCEED][MINMOD] = compare_tails;
6130	1		dispatch[NOTHING][MINMOD] = compare_tails;
6131	1		dispatch[TAIL][MINMOD] = compare_tails;
6132	1		dispatch[WHILEM][MINMOD] = compare_tails;
6133	1		dispatch[CLOSE][MINMOD] = compare_tails;
6134	1		dispatch[MINMOD][MINMOD] = compare_tails;
6135	1		dispatch[OPTIMIZED][MINMOD] = compare_tails;
6136
6137	1		dispatch[SUCCEED][LNBREAK] = compare_left_tail;
6138	1		dispatch[SBOL][LNBREAK] = compare_bol;
6139	1		dispatch[MBOL][LNBREAK] = compare_bol;
6140	1		dispatch[BOUND][LNBREAK] = compare_mismatch;
6141	1		dispatch[NBOUND][LNBREAK] = compare_mismatch;
6142	1		dispatch[REG_ANY][LNBREAK] = compare_mismatch;
6143	1		dispatch[SANY][LNBREAK] = compare_mismatch;
6144	1		dispatch[ANYOF][LNBREAK] = compare_anyof_lnbreak;
6145	1		dispatch[ANYOFD][LNBREAK] = compare_anyof_lnbreak;
6146			#ifdef RC_ANYOFM
6147			dispatch[ANYOFM][LNBREAK] = compare_mismatch;
6148			#endif
6149			#ifdef RC_NANYOFM
6150			dispatch[NANYOFM][LNBREAK] = compare_mismatch;
6151			#endif
6152	1		dispatch[POSIXD][LNBREAK] = compare_posix_lnbreak;
6153	1		dispatch[POSIXU][LNBREAK] = compare_posix_lnbreak;
6154	1		dispatch[POSIXA][LNBREAK] = compare_posix_lnbreak;
6155	1		dispatch[NPOSIXD][LNBREAK] = compare_mismatch;
6156	1		dispatch[NPOSIXU][LNBREAK] = compare_mismatch;
6157	1		dispatch[NPOSIXA][LNBREAK] = compare_mismatch;
6158	1		dispatch[BRANCH][LNBREAK] = compare_left_branch;
6159	1		dispatch[EXACT][LNBREAK] = compare_exact_lnbreak;
6160	1		dispatch[EXACTFU][LNBREAK] = compare_exact_lnbreak;
6161	1		dispatch[NOTHING][LNBREAK] = compare_left_tail;
6162	1		dispatch[TAIL][LNBREAK] = compare_left_tail;
6163	1		dispatch[STAR][LNBREAK] = compare_mismatch;
6164	1		dispatch[PLUS][LNBREAK] = compare_left_plus;
6165	1		dispatch[CURLY][LNBREAK] = compare_left_curly;
6166	1		dispatch[CURLYM][LNBREAK] = compare_left_curly;
6167	1		dispatch[CURLYX][LNBREAK] = compare_left_curly;
6168	1		dispatch[WHILEM][LNBREAK] = compare_left_tail;
6169	1		dispatch[OPEN][LNBREAK] = compare_left_open;
6170	1		dispatch[CLOSE][LNBREAK] = compare_left_tail;
6171	1		dispatch[IFMATCH][LNBREAK] = compare_after_assertion;
6172	1		dispatch[UNLESSM][LNBREAK] = compare_after_assertion;
6173	1		dispatch[MINMOD][LNBREAK] = compare_left_tail;
6174	1		dispatch[LNBREAK][LNBREAK] = compare_tails;
6175
6176	93	100	for (i = 0; i < REGNODE_MAX; ++i)
6177			{
6178	92		dispatch[i][OPTIMIZED] = compare_next;
6179			}
6180
6181	1		dispatch[SUCCEED][OPTIMIZED] = compare_tails;
6182	1		dispatch[NOTHING][OPTIMIZED] = compare_tails;
6183	1		dispatch[TAIL][OPTIMIZED] = compare_tails;
6184	1		dispatch[WHILEM][OPTIMIZED] = compare_tails;
6185	1		dispatch[CLOSE][OPTIMIZED] = compare_tails;
6186	1		dispatch[MINMOD][OPTIMIZED] = compare_tails;
6187	1		dispatch[OPTIMIZED][OPTIMIZED] = compare_tails;
6188	1		}