This is a live mirror of the Perl 5 development currently hosted at https://github.com/perl/perl5
Re: [PATCH] fix re debug segvs in global destruction, and a tweak to Benchmark to...
[perl5.git] / regcomp.c
1 /*    regcomp.c
2  */
3
4 /*
5  * "A fair jaw-cracker dwarf-language must be."  --Samwise Gamgee
6  */
7
8 /* This file contains functions for compiling a regular expression.  See
9  * also regexec.c which funnily enough, contains functions for executing
10  * a regular expression.
11  *
12  * This file is also copied at build time to ext/re/re_comp.c, where
13  * it's built with -DPERL_EXT_RE_BUILD -DPERL_EXT_RE_DEBUG -DPERL_EXT.
14  * This causes the main functions to be compiled under new names and with
15  * debugging support added, which makes "use re 'debug'" work.
16  */
17
18 /* NOTE: this is derived from Henry Spencer's regexp code, and should not
19  * confused with the original package (see point 3 below).  Thanks, Henry!
20  */
21
22 /* Additional note: this code is very heavily munged from Henry's version
23  * in places.  In some spots I've traded clarity for efficiency, so don't
24  * blame Henry for some of the lack of readability.
25  */
26
27 /* The names of the functions have been changed from regcomp and
28  * regexec to  pregcomp and pregexec in order to avoid conflicts
29  * with the POSIX routines of the same names.
30 */
31
32 #ifdef PERL_EXT_RE_BUILD
33 #include "re_top.h"
34 #endif
35
36 /*
37  * pregcomp and pregexec -- regsub and regerror are not used in perl
38  *
39  *      Copyright (c) 1986 by University of Toronto.
40  *      Written by Henry Spencer.  Not derived from licensed software.
41  *
42  *      Permission is granted to anyone to use this software for any
43  *      purpose on any computer system, and to redistribute it freely,
44  *      subject to the following restrictions:
45  *
46  *      1. The author is not responsible for the consequences of use of
47  *              this software, no matter how awful, even if they arise
48  *              from defects in it.
49  *
50  *      2. The origin of this software must not be misrepresented, either
51  *              by explicit claim or by omission.
52  *
53  *      3. Altered versions must be plainly marked as such, and must not
54  *              be misrepresented as being the original software.
55  *
56  *
57  ****    Alterations to Henry's code are...
58  ****
59  ****    Copyright (C) 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
60  ****    2000, 2001, 2002, 2003, 2004, 2005, 2006, by Larry Wall and others
61  ****
62  ****    You may distribute under the terms of either the GNU General Public
63  ****    License or the Artistic License, as specified in the README file.
64
65  *
66  * Beware that some of this code is subtly aware of the way operator
67  * precedence is structured in regular expressions.  Serious changes in
68  * regular-expression syntax might require a total rethink.
69  */
70 #include "EXTERN.h"
71 #define PERL_IN_REGCOMP_C
72 #include "perl.h"
73
74 #ifndef PERL_IN_XSUB_RE
75 #  include "INTERN.h"
76 #endif
77
78 #define REG_COMP_C
79 #ifdef PERL_IN_XSUB_RE
80 #  include "re_comp.h"
81 #else
82 #  include "regcomp.h"
83 #endif
84
85 #ifdef op
86 #undef op
87 #endif /* op */
88
89 #ifdef MSDOS
90 #  if defined(BUGGY_MSC6)
91  /* MSC 6.00A breaks on op/regexp.t test 85 unless we turn this off */
92 #    pragma optimize("a",off)
93  /* But MSC 6.00A is happy with 'w', for aliases only across function calls*/
94 #    pragma optimize("w",on )
95 #  endif /* BUGGY_MSC6 */
96 #endif /* MSDOS */
97
98 #ifndef STATIC
99 #define STATIC  static
100 #endif
101
102 typedef struct RExC_state_t {
103     U32         flags;                  /* are we folding, multilining? */
104     char        *precomp;               /* uncompiled string. */
105     regexp      *rx;
106     char        *start;                 /* Start of input for compile */
107     char        *end;                   /* End of input for compile */
108     char        *parse;                 /* Input-scan pointer. */
109     I32         whilem_seen;            /* number of WHILEM in this expr */
110     regnode     *emit_start;            /* Start of emitted-code area */
111     regnode     *emit;                  /* Code-emit pointer; &regdummy = don't = compiling */
112     I32         naughty;                /* How bad is this pattern? */
113     I32         sawback;                /* Did we see \1, ...? */
114     U32         seen;
115     I32         size;                   /* Code size. */
116     I32         npar;                   /* () count. */
117     I32         extralen;
118     I32         seen_zerolen;
119     I32         seen_evals;
120     I32         utf8;
121 #if ADD_TO_REGEXEC
122     char        *starttry;              /* -Dr: where regtry was called. */
123 #define RExC_starttry   (pRExC_state->starttry)
124 #endif
125 #ifdef DEBUGGING
126     const char  *lastparse;
127     I32         lastnum;
128 #define RExC_lastparse  (pRExC_state->lastparse)
129 #define RExC_lastnum    (pRExC_state->lastnum)
130 #endif
131 } RExC_state_t;
132
133 #define RExC_flags      (pRExC_state->flags)
134 #define RExC_precomp    (pRExC_state->precomp)
135 #define RExC_rx         (pRExC_state->rx)
136 #define RExC_start      (pRExC_state->start)
137 #define RExC_end        (pRExC_state->end)
138 #define RExC_parse      (pRExC_state->parse)
139 #define RExC_whilem_seen        (pRExC_state->whilem_seen)
140 #define RExC_offsets    (pRExC_state->rx->offsets) /* I am not like the others */
141 #define RExC_emit       (pRExC_state->emit)
142 #define RExC_emit_start (pRExC_state->emit_start)
143 #define RExC_naughty    (pRExC_state->naughty)
144 #define RExC_sawback    (pRExC_state->sawback)
145 #define RExC_seen       (pRExC_state->seen)
146 #define RExC_size       (pRExC_state->size)
147 #define RExC_npar       (pRExC_state->npar)
148 #define RExC_extralen   (pRExC_state->extralen)
149 #define RExC_seen_zerolen       (pRExC_state->seen_zerolen)
150 #define RExC_seen_evals (pRExC_state->seen_evals)
151 #define RExC_utf8       (pRExC_state->utf8)
152
153 #define ISMULT1(c)      ((c) == '*' || (c) == '+' || (c) == '?')
154 #define ISMULT2(s)      ((*s) == '*' || (*s) == '+' || (*s) == '?' || \
155         ((*s) == '{' && regcurly(s)))
156
157 #ifdef SPSTART
158 #undef SPSTART          /* dratted cpp namespace... */
159 #endif
160 /*
161  * Flags to be passed up and down.
162  */
163 #define WORST           0       /* Worst case. */
164 #define HASWIDTH        0x1     /* Known to match non-null strings. */
165 #define SIMPLE          0x2     /* Simple enough to be STAR/PLUS operand. */
166 #define SPSTART         0x4     /* Starts with * or +. */
167 #define TRYAGAIN        0x8     /* Weeded out a declaration. */
168
169 #define REG_NODE_NUM(x) ((x) ? (int)((x)-RExC_emit_start) : -1)
170
171 /* whether trie related optimizations are enabled */
172 #if PERL_ENABLE_EXTENDED_TRIE_OPTIMISATION
173 #define TRIE_STUDY_OPT
174 #define TRIE_STCLASS
175 #endif
176 /* Length of a variant. */
177
178 typedef struct scan_data_t {
179     I32 len_min;
180     I32 len_delta;
181     I32 pos_min;
182     I32 pos_delta;
183     SV *last_found;
184     I32 last_end;                       /* min value, <0 unless valid. */
185     I32 last_start_min;
186     I32 last_start_max;
187     SV **longest;                       /* Either &l_fixed, or &l_float. */
188     SV *longest_fixed;
189     I32 offset_fixed;
190     SV *longest_float;
191     I32 offset_float_min;
192     I32 offset_float_max;
193     I32 flags;
194     I32 whilem_c;
195     I32 *last_closep;
196     struct regnode_charclass_class *start_class;
197 } scan_data_t;
198
199 /*
200  * Forward declarations for pregcomp()'s friends.
201  */
202
203 static const scan_data_t zero_scan_data =
204   { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
205
206 #define SF_BEFORE_EOL           (SF_BEFORE_SEOL|SF_BEFORE_MEOL)
207 #define SF_BEFORE_SEOL          0x0001
208 #define SF_BEFORE_MEOL          0x0002
209 #define SF_FIX_BEFORE_EOL       (SF_FIX_BEFORE_SEOL|SF_FIX_BEFORE_MEOL)
210 #define SF_FL_BEFORE_EOL        (SF_FL_BEFORE_SEOL|SF_FL_BEFORE_MEOL)
211
212 #ifdef NO_UNARY_PLUS
213 #  define SF_FIX_SHIFT_EOL      (0+2)
214 #  define SF_FL_SHIFT_EOL               (0+4)
215 #else
216 #  define SF_FIX_SHIFT_EOL      (+2)
217 #  define SF_FL_SHIFT_EOL               (+4)
218 #endif
219
220 #define SF_FIX_BEFORE_SEOL      (SF_BEFORE_SEOL << SF_FIX_SHIFT_EOL)
221 #define SF_FIX_BEFORE_MEOL      (SF_BEFORE_MEOL << SF_FIX_SHIFT_EOL)
222
223 #define SF_FL_BEFORE_SEOL       (SF_BEFORE_SEOL << SF_FL_SHIFT_EOL)
224 #define SF_FL_BEFORE_MEOL       (SF_BEFORE_MEOL << SF_FL_SHIFT_EOL) /* 0x20 */
225 #define SF_IS_INF               0x0040
226 #define SF_HAS_PAR              0x0080
227 #define SF_IN_PAR               0x0100
228 #define SF_HAS_EVAL             0x0200
229 #define SCF_DO_SUBSTR           0x0400
230 #define SCF_DO_STCLASS_AND      0x0800
231 #define SCF_DO_STCLASS_OR       0x1000
232 #define SCF_DO_STCLASS          (SCF_DO_STCLASS_AND|SCF_DO_STCLASS_OR)
233 #define SCF_WHILEM_VISITED_POS  0x2000
234
235 #define SCF_EXACT_TRIE          0x4000 /* should re study once we are done? */
236
237 #define UTF (RExC_utf8 != 0)
238 #define LOC ((RExC_flags & PMf_LOCALE) != 0)
239 #define FOLD ((RExC_flags & PMf_FOLD) != 0)
240
241 #define OOB_UNICODE             12345678
242 #define OOB_NAMEDCLASS          -1
243
244 #define CHR_SVLEN(sv) (UTF ? sv_len_utf8(sv) : SvCUR(sv))
245 #define CHR_DIST(a,b) (UTF ? utf8_distance(a,b) : a - b)
246
247
248 /* length of regex to show in messages that don't mark a position within */
249 #define RegexLengthToShowInErrorMessages 127
250
251 /*
252  * If MARKER[12] are adjusted, be sure to adjust the constants at the top
253  * of t/op/regmesg.t, the tests in t/op/re_tests, and those in
254  * op/pragma/warn/regcomp.
255  */
256 #define MARKER1 "<-- HERE"    /* marker as it appears in the description */
257 #define MARKER2 " <-- HERE "  /* marker as it appears within the regex */
258
259 #define REPORT_LOCATION " in regex; marked by " MARKER1 " in m/%.*s" MARKER2 "%s/"
260
261 /*
262  * Calls SAVEDESTRUCTOR_X if needed, then calls Perl_croak with the given
263  * arg. Show regex, up to a maximum length. If it's too long, chop and add
264  * "...".
265  */
266 #define FAIL(msg) STMT_START {                                          \
267     const char *ellipses = "";                                          \
268     IV len = RExC_end - RExC_precomp;                                   \
269                                                                         \
270     if (!SIZE_ONLY)                                                     \
271         SAVEDESTRUCTOR_X(clear_re,(void*)RExC_rx);                      \
272     if (len > RegexLengthToShowInErrorMessages) {                       \
273         /* chop 10 shorter than the max, to ensure meaning of "..." */  \
274         len = RegexLengthToShowInErrorMessages - 10;                    \
275         ellipses = "...";                                               \
276     }                                                                   \
277     Perl_croak(aTHX_ "%s in regex m/%.*s%s/",                           \
278             msg, (int)len, RExC_precomp, ellipses);                     \
279 } STMT_END
280
281 /*
282  * Simple_vFAIL -- like FAIL, but marks the current location in the scan
283  */
284 #define Simple_vFAIL(m) STMT_START {                                    \
285     const IV offset = RExC_parse - RExC_precomp;                        \
286     Perl_croak(aTHX_ "%s" REPORT_LOCATION,                              \
287             m, (int)offset, RExC_precomp, RExC_precomp + offset);       \
288 } STMT_END
289
290 /*
291  * Calls SAVEDESTRUCTOR_X if needed, then Simple_vFAIL()
292  */
293 #define vFAIL(m) STMT_START {                           \
294     if (!SIZE_ONLY)                                     \
295         SAVEDESTRUCTOR_X(clear_re,(void*)RExC_rx);      \
296     Simple_vFAIL(m);                                    \
297 } STMT_END
298
299 /*
300  * Like Simple_vFAIL(), but accepts two arguments.
301  */
302 #define Simple_vFAIL2(m,a1) STMT_START {                        \
303     const IV offset = RExC_parse - RExC_precomp;                        \
304     S_re_croak2(aTHX_ m, REPORT_LOCATION, a1,                   \
305             (int)offset, RExC_precomp, RExC_precomp + offset);  \
306 } STMT_END
307
308 /*
309  * Calls SAVEDESTRUCTOR_X if needed, then Simple_vFAIL2().
310  */
311 #define vFAIL2(m,a1) STMT_START {                       \
312     if (!SIZE_ONLY)                                     \
313         SAVEDESTRUCTOR_X(clear_re,(void*)RExC_rx);      \
314     Simple_vFAIL2(m, a1);                               \
315 } STMT_END
316
317
318 /*
319  * Like Simple_vFAIL(), but accepts three arguments.
320  */
321 #define Simple_vFAIL3(m, a1, a2) STMT_START {                   \
322     const IV offset = RExC_parse - RExC_precomp;                \
323     S_re_croak2(aTHX_ m, REPORT_LOCATION, a1, a2,               \
324             (int)offset, RExC_precomp, RExC_precomp + offset);  \
325 } STMT_END
326
327 /*
328  * Calls SAVEDESTRUCTOR_X if needed, then Simple_vFAIL3().
329  */
330 #define vFAIL3(m,a1,a2) STMT_START {                    \
331     if (!SIZE_ONLY)                                     \
332         SAVEDESTRUCTOR_X(clear_re,(void*)RExC_rx);      \
333     Simple_vFAIL3(m, a1, a2);                           \
334 } STMT_END
335
336 /*
337  * Like Simple_vFAIL(), but accepts four arguments.
338  */
339 #define Simple_vFAIL4(m, a1, a2, a3) STMT_START {               \
340     const IV offset = RExC_parse - RExC_precomp;                \
341     S_re_croak2(aTHX_ m, REPORT_LOCATION, a1, a2, a3,           \
342             (int)offset, RExC_precomp, RExC_precomp + offset);  \
343 } STMT_END
344
345 #define vWARN(loc,m) STMT_START {                                       \
346     const IV offset = loc - RExC_precomp;                               \
347     Perl_warner(aTHX_ packWARN(WARN_REGEXP), "%s" REPORT_LOCATION,      \
348             m, (int)offset, RExC_precomp, RExC_precomp + offset);       \
349 } STMT_END
350
351 #define vWARNdep(loc,m) STMT_START {                                    \
352     const IV offset = loc - RExC_precomp;                               \
353     Perl_warner(aTHX_ packWARN2(WARN_DEPRECATED, WARN_REGEXP),          \
354             "%s" REPORT_LOCATION,                                       \
355             m, (int)offset, RExC_precomp, RExC_precomp + offset);       \
356 } STMT_END
357
358
359 #define vWARN2(loc, m, a1) STMT_START {                                 \
360     const IV offset = loc - RExC_precomp;                               \
361     Perl_warner(aTHX_ packWARN(WARN_REGEXP), m REPORT_LOCATION,         \
362             a1, (int)offset, RExC_precomp, RExC_precomp + offset);      \
363 } STMT_END
364
365 #define vWARN3(loc, m, a1, a2) STMT_START {                             \
366     const IV offset = loc - RExC_precomp;                               \
367     Perl_warner(aTHX_ packWARN(WARN_REGEXP), m REPORT_LOCATION,         \
368             a1, a2, (int)offset, RExC_precomp, RExC_precomp + offset);  \
369 } STMT_END
370
371 #define vWARN4(loc, m, a1, a2, a3) STMT_START {                         \
372     const IV offset = loc - RExC_precomp;                               \
373     Perl_warner(aTHX_ packWARN(WARN_REGEXP), m REPORT_LOCATION,         \
374             a1, a2, a3, (int)offset, RExC_precomp, RExC_precomp + offset); \
375 } STMT_END
376
377 #define vWARN5(loc, m, a1, a2, a3, a4) STMT_START {                     \
378     const IV offset = loc - RExC_precomp;                               \
379     Perl_warner(aTHX_ packWARN(WARN_REGEXP), m REPORT_LOCATION,         \
380             a1, a2, a3, a4, (int)offset, RExC_precomp, RExC_precomp + offset); \
381 } STMT_END
382
383
384 /* Allow for side effects in s */
385 #define REGC(c,s) STMT_START {                  \
386     if (!SIZE_ONLY) *(s) = (c); else (void)(s); \
387 } STMT_END
388
389 /* Macros for recording node offsets.   20001227 mjd@plover.com 
390  * Nodes are numbered 1, 2, 3, 4.  Node #n's position is recorded in
391  * element 2*n-1 of the array.  Element #2n holds the byte length node #n.
392  * Element 0 holds the number n.
393  * Position is 1 indexed.
394  */
395
396 #define Set_Node_Offset_To_R(node,byte) STMT_START {                    \
397     if (! SIZE_ONLY) {                                                  \
398         MJD_OFFSET_DEBUG(("** (%d) offset of node %d is %d.\n",         \
399                     __LINE__, (node), (int)(byte)));                    \
400         if((node) < 0) {                                                \
401             Perl_croak(aTHX_ "value of node is %d in Offset macro", (int)(node)); \
402         } else {                                                        \
403             RExC_offsets[2*(node)-1] = (byte);                          \
404         }                                                               \
405     }                                                                   \
406 } STMT_END
407
408 #define Set_Node_Offset(node,byte) \
409     Set_Node_Offset_To_R((node)-RExC_emit_start, (byte)-RExC_start)
410 #define Set_Cur_Node_Offset Set_Node_Offset(RExC_emit, RExC_parse)
411
412 #define Set_Node_Length_To_R(node,len) STMT_START {                     \
413     if (! SIZE_ONLY) {                                                  \
414         MJD_OFFSET_DEBUG(("** (%d) size of node %d is %d.\n",           \
415                 __LINE__, (int)(node), (int)(len)));                    \
416         if((node) < 0) {                                                \
417             Perl_croak(aTHX_ "value of node is %d in Length macro", (int)(node)); \
418         } else {                                                        \
419             RExC_offsets[2*(node)] = (len);                             \
420         }                                                               \
421     }                                                                   \
422 } STMT_END
423
424 #define Set_Node_Length(node,len) \
425     Set_Node_Length_To_R((node)-RExC_emit_start, len)
426 #define Set_Cur_Node_Length(len) Set_Node_Length(RExC_emit, len)
427 #define Set_Node_Cur_Length(node) \
428     Set_Node_Length(node, RExC_parse - parse_start)
429
430 /* Get offsets and lengths */
431 #define Node_Offset(n) (RExC_offsets[2*((n)-RExC_emit_start)-1])
432 #define Node_Length(n) (RExC_offsets[2*((n)-RExC_emit_start)])
433
434 #define Set_Node_Offset_Length(node,offset,len) STMT_START {    \
435     Set_Node_Offset_To_R((node)-RExC_emit_start, (offset));     \
436     Set_Node_Length_To_R((node)-RExC_emit_start, (len));        \
437 } STMT_END
438
439
440 #if PERL_ENABLE_EXPERIMENTAL_REGEX_OPTIMISATIONS
441 #define EXPERIMENTAL_INPLACESCAN
442 #endif
443
444 static void clear_re(pTHX_ void *r);
445
446 /* Mark that we cannot extend a found fixed substring at this point.
447    Updata the longest found anchored substring and the longest found
448    floating substrings if needed. */
449
450 STATIC void
451 S_scan_commit(pTHX_ const RExC_state_t *pRExC_state, scan_data_t *data)
452 {
453     const STRLEN l = CHR_SVLEN(data->last_found);
454     const STRLEN old_l = CHR_SVLEN(*data->longest);
455
456     if ((l >= old_l) && ((l > old_l) || (data->flags & SF_BEFORE_EOL))) {
457         SvSetMagicSV(*data->longest, data->last_found);
458         if (*data->longest == data->longest_fixed) {
459             data->offset_fixed = l ? data->last_start_min : data->pos_min;
460             if (data->flags & SF_BEFORE_EOL)
461                 data->flags
462                     |= ((data->flags & SF_BEFORE_EOL) << SF_FIX_SHIFT_EOL);
463             else
464                 data->flags &= ~SF_FIX_BEFORE_EOL;
465         }
466         else {
467             data->offset_float_min = l ? data->last_start_min : data->pos_min;
468             data->offset_float_max = (l
469                                       ? data->last_start_max
470                                       : data->pos_min + data->pos_delta);
471             if ((U32)data->offset_float_max > (U32)I32_MAX)
472                 data->offset_float_max = I32_MAX;
473             if (data->flags & SF_BEFORE_EOL)
474                 data->flags
475                     |= ((data->flags & SF_BEFORE_EOL) << SF_FL_SHIFT_EOL);
476             else
477                 data->flags &= ~SF_FL_BEFORE_EOL;
478         }
479     }
480     SvCUR_set(data->last_found, 0);
481     {
482         SV * const sv = data->last_found;
483         if (SvUTF8(sv) && SvMAGICAL(sv)) {
484             MAGIC * const mg = mg_find(sv, PERL_MAGIC_utf8);
485             if (mg)
486                 mg->mg_len = 0;
487         }
488     }
489     data->last_end = -1;
490     data->flags &= ~SF_BEFORE_EOL;
491 }
492
493 /* Can match anything (initialization) */
494 STATIC void
495 S_cl_anything(const RExC_state_t *pRExC_state, struct regnode_charclass_class *cl)
496 {
497     ANYOF_CLASS_ZERO(cl);
498     ANYOF_BITMAP_SETALL(cl);
499     cl->flags = ANYOF_EOS|ANYOF_UNICODE_ALL;
500     if (LOC)
501         cl->flags |= ANYOF_LOCALE;
502 }
503
504 /* Can match anything (initialization) */
505 STATIC int
506 S_cl_is_anything(const struct regnode_charclass_class *cl)
507 {
508     int value;
509
510     for (value = 0; value <= ANYOF_MAX; value += 2)
511         if (ANYOF_CLASS_TEST(cl, value) && ANYOF_CLASS_TEST(cl, value + 1))
512             return 1;
513     if (!(cl->flags & ANYOF_UNICODE_ALL))
514         return 0;
515     if (!ANYOF_BITMAP_TESTALLSET(cl))
516         return 0;
517     return 1;
518 }
519
520 /* Can match anything (initialization) */
521 STATIC void
522 S_cl_init(const RExC_state_t *pRExC_state, struct regnode_charclass_class *cl)
523 {
524     Zero(cl, 1, struct regnode_charclass_class);
525     cl->type = ANYOF;
526     cl_anything(pRExC_state, cl);
527 }
528
529 STATIC void
530 S_cl_init_zero(const RExC_state_t *pRExC_state, struct regnode_charclass_class *cl)
531 {
532     Zero(cl, 1, struct regnode_charclass_class);
533     cl->type = ANYOF;
534     cl_anything(pRExC_state, cl);
535     if (LOC)
536         cl->flags |= ANYOF_LOCALE;
537 }
538
539 /* 'And' a given class with another one.  Can create false positives */
540 /* We assume that cl is not inverted */
541 STATIC void
542 S_cl_and(struct regnode_charclass_class *cl,
543         const struct regnode_charclass_class *and_with)
544 {
545     if (!(and_with->flags & ANYOF_CLASS)
546         && !(cl->flags & ANYOF_CLASS)
547         && (and_with->flags & ANYOF_LOCALE) == (cl->flags & ANYOF_LOCALE)
548         && !(and_with->flags & ANYOF_FOLD)
549         && !(cl->flags & ANYOF_FOLD)) {
550         int i;
551
552         if (and_with->flags & ANYOF_INVERT)
553             for (i = 0; i < ANYOF_BITMAP_SIZE; i++)
554                 cl->bitmap[i] &= ~and_with->bitmap[i];
555         else
556             for (i = 0; i < ANYOF_BITMAP_SIZE; i++)
557                 cl->bitmap[i] &= and_with->bitmap[i];
558     } /* XXXX: logic is complicated otherwise, leave it along for a moment. */
559     if (!(and_with->flags & ANYOF_EOS))
560         cl->flags &= ~ANYOF_EOS;
561
562     if (cl->flags & ANYOF_UNICODE_ALL && and_with->flags & ANYOF_UNICODE &&
563         !(and_with->flags & ANYOF_INVERT)) {
564         cl->flags &= ~ANYOF_UNICODE_ALL;
565         cl->flags |= ANYOF_UNICODE;
566         ARG_SET(cl, ARG(and_with));
567     }
568     if (!(and_with->flags & ANYOF_UNICODE_ALL) &&
569         !(and_with->flags & ANYOF_INVERT))
570         cl->flags &= ~ANYOF_UNICODE_ALL;
571     if (!(and_with->flags & (ANYOF_UNICODE|ANYOF_UNICODE_ALL)) &&
572         !(and_with->flags & ANYOF_INVERT))
573         cl->flags &= ~ANYOF_UNICODE;
574 }
575
576 /* 'OR' a given class with another one.  Can create false positives */
577 /* We assume that cl is not inverted */
578 STATIC void
579 S_cl_or(const RExC_state_t *pRExC_state, struct regnode_charclass_class *cl, const struct regnode_charclass_class *or_with)
580 {
581     if (or_with->flags & ANYOF_INVERT) {
582         /* We do not use
583          * (B1 | CL1) | (!B2 & !CL2) = (B1 | !B2 & !CL2) | (CL1 | (!B2 & !CL2))
584          *   <= (B1 | !B2) | (CL1 | !CL2)
585          * which is wasteful if CL2 is small, but we ignore CL2:
586          *   (B1 | CL1) | (!B2 & !CL2) <= (B1 | CL1) | !B2 = (B1 | !B2) | CL1
587          * XXXX Can we handle case-fold?  Unclear:
588          *   (OK1(i) | OK1(i')) | !(OK1(i) | OK1(i')) =
589          *   (OK1(i) | OK1(i')) | (!OK1(i) & !OK1(i'))
590          */
591         if ( (or_with->flags & ANYOF_LOCALE) == (cl->flags & ANYOF_LOCALE)
592              && !(or_with->flags & ANYOF_FOLD)
593              && !(cl->flags & ANYOF_FOLD) ) {
594             int i;
595
596             for (i = 0; i < ANYOF_BITMAP_SIZE; i++)
597                 cl->bitmap[i] |= ~or_with->bitmap[i];
598         } /* XXXX: logic is complicated otherwise */
599         else {
600             cl_anything(pRExC_state, cl);
601         }
602     } else {
603         /* (B1 | CL1) | (B2 | CL2) = (B1 | B2) | (CL1 | CL2)) */
604         if ( (or_with->flags & ANYOF_LOCALE) == (cl->flags & ANYOF_LOCALE)
605              && (!(or_with->flags & ANYOF_FOLD)
606                  || (cl->flags & ANYOF_FOLD)) ) {
607             int i;
608
609             /* OR char bitmap and class bitmap separately */
610             for (i = 0; i < ANYOF_BITMAP_SIZE; i++)
611                 cl->bitmap[i] |= or_with->bitmap[i];
612             if (or_with->flags & ANYOF_CLASS) {
613                 for (i = 0; i < ANYOF_CLASSBITMAP_SIZE; i++)
614                     cl->classflags[i] |= or_with->classflags[i];
615                 cl->flags |= ANYOF_CLASS;
616             }
617         }
618         else { /* XXXX: logic is complicated, leave it along for a moment. */
619             cl_anything(pRExC_state, cl);
620         }
621     }
622     if (or_with->flags & ANYOF_EOS)
623         cl->flags |= ANYOF_EOS;
624
625     if (cl->flags & ANYOF_UNICODE && or_with->flags & ANYOF_UNICODE &&
626         ARG(cl) != ARG(or_with)) {
627         cl->flags |= ANYOF_UNICODE_ALL;
628         cl->flags &= ~ANYOF_UNICODE;
629     }
630     if (or_with->flags & ANYOF_UNICODE_ALL) {
631         cl->flags |= ANYOF_UNICODE_ALL;
632         cl->flags &= ~ANYOF_UNICODE;
633     }
634 }
635
636 /*
637
638  make_trie(startbranch,first,last,tail,flags,depth)
639   startbranch: the first branch in the whole branch sequence
640   first      : start branch of sequence of branch-exact nodes.
641                May be the same as startbranch
642   last       : Thing following the last branch.
643                May be the same as tail.
644   tail       : item following the branch sequence
645   flags      : currently the OP() type we will be building one of /EXACT(|F|Fl)/
646   depth      : indent depth
647
648 Inplace optimizes a sequence of 2 or more Branch-Exact nodes into a TRIE node.
649
650 A trie is an N'ary tree where the branches are determined by digital
651 decomposition of the key. IE, at the root node you look up the 1st character and
652 follow that branch repeat until you find the end of the branches. Nodes can be
653 marked as "accepting" meaning they represent a complete word. Eg:
654
655   /he|she|his|hers/
656
657 would convert into the following structure. Numbers represent states, letters
658 following numbers represent valid transitions on the letter from that state, if
659 the number is in square brackets it represents an accepting state, otherwise it
660 will be in parenthesis.
661
662       +-h->+-e->[3]-+-r->(8)-+-s->[9]
663       |    |
664       |   (2)
665       |    |
666      (1)   +-i->(6)-+-s->[7]
667       |
668       +-s->(3)-+-h->(4)-+-e->[5]
669
670       Accept Word Mapping: 3=>1 (he),5=>2 (she), 7=>3 (his), 9=>4 (hers)
671
672 This shows that when matching against the string 'hers' we will begin at state 1
673 read 'h' and move to state 2, read 'e' and move to state 3 which is accepting,
674 then read 'r' and go to state 8 followed by 's' which takes us to state 9 which
675 is also accepting. Thus we know that we can match both 'he' and 'hers' with a
676 single traverse. We store a mapping from accepting to state to which word was
677 matched, and then when we have multiple possibilities we try to complete the
678 rest of the regex in the order in which they occured in the alternation.
679
680 The only prior NFA like behaviour that would be changed by the TRIE support is
681 the silent ignoring of duplicate alternations which are of the form:
682
683  / (DUPE|DUPE) X? (?{ ... }) Y /x
684
685 Thus EVAL blocks follwing a trie may be called a different number of times with
686 and without the optimisation. With the optimisations dupes will be silently
687 ignored. This inconsistant behaviour of EVAL type nodes is well established as
688 the following demonstrates:
689
690  'words'=~/(word|word|word)(?{ print $1 })[xyz]/
691
692 which prints out 'word' three times, but
693
694  'words'=~/(word|word|word)(?{ print $1 })S/
695
696 which doesnt print it out at all. This is due to other optimisations kicking in.
697
698 Example of what happens on a structural level:
699
700 The regexp /(ac|ad|ab)+/ will produce the folowing debug output:
701
702    1: CURLYM[1] {1,32767}(18)
703    5:   BRANCH(8)
704    6:     EXACT <ac>(16)
705    8:   BRANCH(11)
706    9:     EXACT <ad>(16)
707   11:   BRANCH(14)
708   12:     EXACT <ab>(16)
709   16:   SUCCEED(0)
710   17:   NOTHING(18)
711   18: END(0)
712
713 This would be optimizable with startbranch=5, first=5, last=16, tail=16
714 and should turn into:
715
716    1: CURLYM[1] {1,32767}(18)
717    5:   TRIE(16)
718         [Words:3 Chars Stored:6 Unique Chars:4 States:5 NCP:1]
719           <ac>
720           <ad>
721           <ab>
722   16:   SUCCEED(0)
723   17:   NOTHING(18)
724   18: END(0)
725
726 Cases where tail != last would be like /(?foo|bar)baz/:
727
728    1: BRANCH(4)
729    2:   EXACT <foo>(8)
730    4: BRANCH(7)
731    5:   EXACT <bar>(8)
732    7: TAIL(8)
733    8: EXACT <baz>(10)
734   10: END(0)
735
736 which would be optimizable with startbranch=1, first=1, last=7, tail=8
737 and would end up looking like:
738
739     1: TRIE(8)
740       [Words:2 Chars Stored:6 Unique Chars:5 States:7 NCP:1]
741         <foo>
742         <bar>
743    7: TAIL(8)
744    8: EXACT <baz>(10)
745   10: END(0)
746
747     d = uvuni_to_utf8_flags(d, uv, 0);
748
749 is the recommended Unicode-aware way of saying
750
751     *(d++) = uv;
752 */
753
754 #define TRIE_STORE_REVCHAR                                                    \
755     STMT_START {                                                           \
756         SV *tmp = Perl_newSVpvf_nocontext( "%c", (int)uvc );               \
757         av_push( TRIE_REVCHARMAP(trie), tmp );                             \
758     } STMT_END
759
760 #define TRIE_READ_CHAR STMT_START {                                           \
761     wordlen++;                                                                \
762     if ( UTF ) {                                                              \
763         if ( folder ) {                                                       \
764             if ( foldlen > 0 ) {                                              \
765                uvc = utf8n_to_uvuni( scan, UTF8_MAXLEN, &len, uniflags );     \
766                foldlen -= len;                                                \
767                scan += len;                                                   \
768                len = 0;                                                       \
769             } else {                                                          \
770                 uvc = utf8n_to_uvuni( (const U8*)uc, UTF8_MAXLEN, &len, uniflags);\
771                 uvc = to_uni_fold( uvc, foldbuf, &foldlen );                  \
772                 foldlen -= UNISKIP( uvc );                                    \
773                 scan = foldbuf + UNISKIP( uvc );                              \
774             }                                                                 \
775         } else {                                                              \
776             uvc = utf8n_to_uvuni( (const U8*)uc, UTF8_MAXLEN, &len, uniflags);\
777         }                                                                     \
778     } else {                                                                  \
779         uvc = (U32)*uc;                                                       \
780         len = 1;                                                              \
781     }                                                                         \
782 } STMT_END
783
784
785 #define TRIE_LIST_ITEM(state,idx) (trie->states[state].trans.list)[ idx ]
786 #define TRIE_LIST_CUR(state)  ( TRIE_LIST_ITEM( state, 0 ).forid )
787 #define TRIE_LIST_LEN(state) ( TRIE_LIST_ITEM( state, 0 ).newstate )
788 #define TRIE_LIST_USED(idx)  ( trie->states[state].trans.list ? (TRIE_LIST_CUR( idx ) - 1) : 0 )
789
790 #define TRIE_LIST_PUSH(state,fid,ns) STMT_START {               \
791     if ( TRIE_LIST_CUR( state ) >=TRIE_LIST_LEN( state ) ) {    \
792         TRIE_LIST_LEN( state ) *= 2;                            \
793         Renew( trie->states[ state ].trans.list,                \
794                TRIE_LIST_LEN( state ), reg_trie_trans_le );     \
795     }                                                           \
796     TRIE_LIST_ITEM( state, TRIE_LIST_CUR( state ) ).forid = fid;     \
797     TRIE_LIST_ITEM( state, TRIE_LIST_CUR( state ) ).newstate = ns;   \
798     TRIE_LIST_CUR( state )++;                                   \
799 } STMT_END
800
801 #define TRIE_LIST_NEW(state) STMT_START {                       \
802     Newxz( trie->states[ state ].trans.list,               \
803         4, reg_trie_trans_le );                                 \
804      TRIE_LIST_CUR( state ) = 1;                                \
805      TRIE_LIST_LEN( state ) = 4;                                \
806 } STMT_END
807
808 #define TRIE_HANDLE_WORD(state) STMT_START {                            \
809             if ( !trie->states[ state ].wordnum ) {                     \
810                 /* we haven't inserted this word into the structure yet. */ \
811                 if (trie->wordlen)                                      \
812                     trie->wordlen[ curword ] = wordlen;                 \
813                 trie->states[ state ].wordnum = ++curword;              \
814                 DEBUG_r({                                               \
815                     /* store the word for dumping */                    \
816                     SV* tmp;                                            \
817                     if (OP(noper) != NOTHING)                           \
818                         tmp = newSVpvn(STRING(noper), STR_LEN(noper));  \
819                     else                                                \
820                         tmp = newSVpvn( "", 0 );                        \
821                     if ( UTF ) SvUTF8_on( tmp );                        \
822                     av_push( trie->words, tmp );                        \
823                 });                                                     \
824             } else {                                                    \
825                 NOOP;   /* It's a dupe. So ignore it. */                \
826             }                                                           \
827 } STMT_END
828
829 #ifdef DEBUGGING
830 /*
831    dump_trie(trie)
832    dump_trie_interim_list(trie,next_alloc)
833    dump_trie_interim_table(trie,next_alloc)
834
835    These routines dump out a trie in a somewhat readable format.
836    The _interim_ variants are used for debugging the interim
837    tables that are used to generate the final compressed
838    representation which is what dump_trie expects.
839
840    Part of the reason for their existance is to provide a form
841    of documentation as to how the different representations function.
842
843 */
844
845 /*
846   dump_trie(trie)
847   Dumps the final compressed table form of the trie to Perl_debug_log.
848   Used for debugging make_trie().
849 */
850  
851 STATIC void
852 S_dump_trie(pTHX_ const struct _reg_trie_data *trie,U32 depth)
853 {
854     U32 state;
855     GET_RE_DEBUG_FLAGS_DECL;
856
857     PerlIO_printf( Perl_debug_log, "%*sChar : %-6s%-6s%-4s ",
858         (int)depth * 2 + 2,"",
859         "Match","Base","Ofs" );
860
861     for( state = 0 ; state < trie->uniquecharcount ; state++ ) {
862         SV ** const tmp = av_fetch( trie->revcharmap, state, 0);
863         if ( tmp ) {
864           PerlIO_printf( Perl_debug_log, "%4.4s ", SvPV_nolen_const( *tmp ) );
865         }
866     }
867     PerlIO_printf( Perl_debug_log, "\n%*sState|-----------------------",
868         (int)depth * 2 + 2,"");
869
870     for( state = 0 ; state < trie->uniquecharcount ; state++ )
871         PerlIO_printf( Perl_debug_log, "-----");
872     PerlIO_printf( Perl_debug_log, "\n");
873
874     for( state = 1 ; state < TRIE_LASTSTATE(trie) ; state++ ) {
875         const U32 base = trie->states[ state ].trans.base;
876
877         PerlIO_printf( Perl_debug_log, "%*s#%4"UVXf"|", (int)depth * 2 + 2,"", (UV)state);
878
879         if ( trie->states[ state ].wordnum ) {
880             PerlIO_printf( Perl_debug_log, " W%4X", trie->states[ state ].wordnum );
881         } else {
882             PerlIO_printf( Perl_debug_log, "%6s", "" );
883         }
884
885         PerlIO_printf( Perl_debug_log, " @%4"UVXf" ", (UV)base );
886
887         if ( base ) {
888             U32 ofs = 0;
889
890             while( ( base + ofs  < trie->uniquecharcount ) ||
891                    ( base + ofs - trie->uniquecharcount < trie->lasttrans
892                      && trie->trans[ base + ofs - trie->uniquecharcount ].check != state))
893                     ofs++;
894
895             PerlIO_printf( Perl_debug_log, "+%2"UVXf"[ ", (UV)ofs);
896
897             for ( ofs = 0 ; ofs < trie->uniquecharcount ; ofs++ ) {
898                 if ( ( base + ofs >= trie->uniquecharcount ) &&
899                      ( base + ofs - trie->uniquecharcount < trie->lasttrans ) &&
900                      trie->trans[ base + ofs - trie->uniquecharcount ].check == state )
901                 {
902                    PerlIO_printf( Perl_debug_log, "%4"UVXf" ",
903                     (UV)trie->trans[ base + ofs - trie->uniquecharcount ].next );
904                 } else {
905                     PerlIO_printf( Perl_debug_log, "%4s ","   ." );
906                 }
907             }
908
909             PerlIO_printf( Perl_debug_log, "]");
910
911         }
912         PerlIO_printf( Perl_debug_log, "\n" );
913     }
914 }    
915 /*
916   dump_trie_interim_list(trie,next_alloc)
917   Dumps a fully constructed but uncompressed trie in list form.
918   List tries normally only are used for construction when the number of 
919   possible chars (trie->uniquecharcount) is very high.
920   Used for debugging make_trie().
921 */
922 STATIC void
923 S_dump_trie_interim_list(pTHX_ const struct _reg_trie_data *trie, U32 next_alloc,U32 depth)
924 {
925     U32 state;
926     GET_RE_DEBUG_FLAGS_DECL;
927     /* print out the table precompression.  */
928     PerlIO_printf( Perl_debug_log, "%*sState :Word | Transition Data\n%*s",
929         (int)depth * 2 + 2,"", (int)depth * 2 + 2,"");
930     PerlIO_printf( Perl_debug_log,   "------:-----+-----------------" );
931     
932     for( state=1 ; state < next_alloc ; state ++ ) {
933         U16 charid;
934     
935         PerlIO_printf( Perl_debug_log, "\n%*s %4"UVXf" :",
936             (int)depth * 2 + 2,"", (UV)state  );
937         if ( ! trie->states[ state ].wordnum ) {
938             PerlIO_printf( Perl_debug_log, "%5s| ","");
939         } else {
940             PerlIO_printf( Perl_debug_log, "W%4x| ",
941                 trie->states[ state ].wordnum
942             );
943         }
944         for( charid = 1 ; charid <= TRIE_LIST_USED( state ) ; charid++ ) {
945             SV ** const tmp = av_fetch( trie->revcharmap, TRIE_LIST_ITEM(state,charid).forid, 0);
946             PerlIO_printf( Perl_debug_log, "%s:%3X=%4"UVXf" | ",
947                 SvPV_nolen_const( *tmp ),
948                 TRIE_LIST_ITEM(state,charid).forid,
949                 (UV)TRIE_LIST_ITEM(state,charid).newstate
950             );
951         }
952     
953     }
954 }    
955
956 /*
957   dump_trie_interim_table(trie,next_alloc)
958   Dumps a fully constructed but uncompressed trie in table form.
959   This is the normal DFA style state transition table, with a few 
960   twists to facilitate compression later. 
961   Used for debugging make_trie().
962 */
963 STATIC void
964 S_dump_trie_interim_table(pTHX_ const struct _reg_trie_data *trie, U32 next_alloc, U32 depth)
965 {
966     U32 state;
967     U16 charid;
968     GET_RE_DEBUG_FLAGS_DECL;
969     
970     /*
971        print out the table precompression so that we can do a visual check
972        that they are identical.
973      */
974     
975     PerlIO_printf( Perl_debug_log, "%*sChar : ",(int)depth * 2 + 2,"" );
976
977     for( charid = 0 ; charid < trie->uniquecharcount ; charid++ ) {
978         SV ** const tmp = av_fetch( trie->revcharmap, charid, 0);
979         if ( tmp ) {
980           PerlIO_printf( Perl_debug_log, "%4.4s ", SvPV_nolen_const( *tmp ) );
981         }
982     }
983
984     PerlIO_printf( Perl_debug_log, "\n%*sState+-",(int)depth * 2 + 2,"" );
985
986     for( charid=0 ; charid < trie->uniquecharcount ; charid++ ) {
987         PerlIO_printf( Perl_debug_log, "%4s-", "----" );
988     }
989
990     PerlIO_printf( Perl_debug_log, "\n" );
991
992     for( state=1 ; state < next_alloc ; state += trie->uniquecharcount ) {
993
994         PerlIO_printf( Perl_debug_log, "%*s%4"UVXf" : ", 
995             (int)depth * 2 + 2,"",
996             (UV)TRIE_NODENUM( state ) );
997
998         for( charid = 0 ; charid < trie->uniquecharcount ; charid++ ) {
999             PerlIO_printf( Perl_debug_log, "%4"UVXf" ",
1000                 (UV)SAFE_TRIE_NODENUM( trie->trans[ state + charid ].next ) );
1001         }
1002         if ( ! trie->states[ TRIE_NODENUM( state ) ].wordnum ) {
1003             PerlIO_printf( Perl_debug_log, " (%4"UVXf")\n", (UV)trie->trans[ state ].check );
1004         } else {
1005             PerlIO_printf( Perl_debug_log, " (%4"UVXf") W%4X\n", (UV)trie->trans[ state ].check,
1006             trie->states[ TRIE_NODENUM( state ) ].wordnum );
1007         }
1008     }
1009 }
1010
1011 #endif
1012
1013 #define TRIE_TRANS_STATE(state,base,ucharcount,charid,special)          \
1014      ( ( base + charid >=  ucharcount                                   \
1015          && base + charid < ubound                                      \
1016          && state == trie->trans[ base - ucharcount + charid ].check    \
1017          && trie->trans[ base - ucharcount + charid ].next )            \
1018            ? trie->trans[ base - ucharcount + charid ].next             \
1019            : ( state==1 ? special : 0 )                                 \
1020       )
1021
1022 STATIC void
1023 S_make_trie_failtable(pTHX_ RExC_state_t *pRExC_state, regnode *source,  regnode *stclass, U32 depth)
1024 {
1025 /* The Trie is constructed and compressed now so we can build a fail array now if its needed
1026
1027    This is apparently the Aho-Corasick algorithm. Its from exercise 3.31 and 3.32 in the
1028    "Red Dragon" -- Compilers, principles, techniques, and tools. Aho, Sethi, Ullman 1985/88
1029    ISBN 0-201-10088-6
1030
1031    We find the fail state for each state in the trie, this state is the longest proper
1032    suffix of the current states 'word' that is also a proper prefix of another word in our
1033    trie. State 1 represents the word '' and is the thus the default fail state. This allows
1034    the DFA not to have to restart after its tried and failed a word at a given point, it
1035    simply continues as though it had been matching the other word in the first place.
1036    Consider
1037       'abcdgu'=~/abcdefg|cdgu/
1038    When we get to 'd' we are still matching the first word, we would encounter 'g' which would
1039    fail, which would bring use to the state representing 'd' in the second word where we would
1040    try 'g' and succeed, prodceding to match 'cdgu'.
1041  */
1042  /* add a fail transition */
1043     reg_trie_data *trie=(reg_trie_data *)RExC_rx->data->data[ARG(source)];
1044     U32 *q;
1045     const U32 ucharcount = trie->uniquecharcount;
1046     const U32 numstates = trie->laststate;
1047     const U32 ubound = trie->lasttrans + ucharcount;
1048     U32 q_read = 0;
1049     U32 q_write = 0;
1050     U32 charid;
1051     U32 base = trie->states[ 1 ].trans.base;
1052     U32 *fail;
1053     reg_ac_data *aho;
1054     const U32 data_slot = add_data( pRExC_state, 1, "T" );
1055     GET_RE_DEBUG_FLAGS_DECL;
1056
1057     ARG_SET( stclass, data_slot );
1058     Newxz( aho, 1, reg_ac_data );
1059     RExC_rx->data->data[ data_slot ] = (void*)aho;
1060     aho->trie=trie;
1061     aho->states=(reg_trie_state *)savepvn((const char*)trie->states, 
1062         (trie->laststate+1)*sizeof(reg_trie_state));
1063     Newxz( q, numstates, U32);
1064     Newxz( aho->fail, numstates, U32 );
1065     aho->refcount = 1;
1066     fail = aho->fail;
1067     fail[ 0 ] = fail[ 1 ] = 1;
1068
1069     for ( charid = 0; charid < ucharcount ; charid++ ) {
1070         const U32 newstate = TRIE_TRANS_STATE( 1, base, ucharcount, charid, 0 );
1071         if ( newstate ) {
1072             q[ q_write ] = newstate;
1073             /* set to point at the root */
1074             fail[ q[ q_write++ ] ]=1;
1075         }
1076     }
1077     while ( q_read < q_write) {
1078         const U32 cur = q[ q_read++ % numstates ];
1079         base = trie->states[ cur ].trans.base;
1080
1081         for ( charid = 0 ; charid < ucharcount ; charid++ ) {
1082             const U32 ch_state = TRIE_TRANS_STATE( cur, base, ucharcount, charid, 1 );
1083             if (ch_state) {
1084                 U32 fail_state = cur;
1085                 U32 fail_base;
1086                 do {
1087                     fail_state = fail[ fail_state ];
1088                     fail_base = aho->states[ fail_state ].trans.base;
1089                 } while ( !TRIE_TRANS_STATE( fail_state, fail_base, ucharcount, charid, 1 ) );
1090
1091                 fail_state = TRIE_TRANS_STATE( fail_state, fail_base, ucharcount, charid, 1 );
1092                 fail[ ch_state ] = fail_state;
1093                 if ( !aho->states[ ch_state ].wordnum && aho->states[ fail_state ].wordnum )
1094                 {
1095                         aho->states[ ch_state ].wordnum =  aho->states[ fail_state ].wordnum;
1096                 }
1097                 q[ q_write++ % numstates] = ch_state;
1098             }
1099         }
1100     }
1101
1102     DEBUG_TRIE_COMPILE_MORE_r({
1103         PerlIO_printf(Perl_debug_log, "%*sFail: 1", (int)(depth * 2), "");
1104         for( q_read=2; q_read<numstates; q_read++ ) {
1105             PerlIO_printf(Perl_debug_log, ", %"UVuf, fail[q_read]);
1106         }
1107         PerlIO_printf(Perl_debug_log, "\n");
1108     });
1109     Safefree(q);
1110     /*RExC_seen |= REG_SEEN_TRIEDFA;*/
1111 }
1112
1113
1114
1115 STATIC I32
1116 S_make_trie(pTHX_ RExC_state_t *pRExC_state, regnode *startbranch, regnode *first, regnode *last, regnode *tail, U32 flags, U32 depth)
1117 {
1118     dVAR;
1119     /* first pass, loop through and scan words */
1120     reg_trie_data *trie;
1121     regnode *cur;
1122     const U32 uniflags = UTF8_ALLOW_DEFAULT;
1123     STRLEN len = 0;
1124     UV uvc = 0;
1125     U16 curword = 0;
1126     U32 next_alloc = 0;
1127     /* we just use folder as a flag in utf8 */
1128     const U8 * const folder = ( flags == EXACTF
1129                        ? PL_fold
1130                        : ( flags == EXACTFL
1131                            ? PL_fold_locale
1132                            : NULL
1133                          )
1134                      );
1135
1136     const U32 data_slot = add_data( pRExC_state, 1, "t" );
1137     SV *re_trie_maxbuff;
1138 #ifndef DEBUGGING
1139     /* these are only used during construction but are useful during
1140      * debugging so we store them in the struct when debugging.
1141      * Wordcount is actually superfluous in debugging as we have
1142      * (AV*)trie->words to use for it, but that's not available when
1143      * not debugging... We could make the macro use the AV during
1144      * debugging though...
1145      */
1146     U16 trie_wordcount=0;
1147     STRLEN trie_charcount=0;
1148     /*U32 trie_laststate=0;*/
1149     AV *trie_revcharmap;
1150 #endif
1151     GET_RE_DEBUG_FLAGS_DECL;
1152
1153     Newxz( trie, 1, reg_trie_data );
1154     trie->refcount = 1;
1155     trie->startstate = 1;
1156     RExC_rx->data->data[ data_slot ] = (void*)trie;
1157     Newxz( trie->charmap, 256, U16 );
1158     if (!(UTF && folder))
1159         Newxz( trie->bitmap, ANYOF_BITMAP_SIZE, char );
1160     DEBUG_r({
1161         trie->words = newAV();
1162     });
1163     TRIE_REVCHARMAP(trie) = newAV();
1164
1165     re_trie_maxbuff = get_sv(RE_TRIE_MAXBUF_NAME, 1);
1166     if (!SvIOK(re_trie_maxbuff)) {
1167         sv_setiv(re_trie_maxbuff, RE_TRIE_MAXBUF_INIT);
1168     }
1169     DEBUG_OPTIMISE_r({
1170                 PerlIO_printf( Perl_debug_log,
1171                   "%*smake_trie start==%d, first==%d, last==%d, tail==%d\n", 
1172                   (int)depth * 2 + 2, "", 
1173                   REG_NODE_NUM(startbranch),REG_NODE_NUM(first), 
1174                   REG_NODE_NUM(last), REG_NODE_NUM(tail));
1175     });
1176     /*  -- First loop and Setup --
1177
1178        We first traverse the branches and scan each word to determine if it
1179        contains widechars, and how many unique chars there are, this is
1180        important as we have to build a table with at least as many columns as we
1181        have unique chars.
1182
1183        We use an array of integers to represent the character codes 0..255
1184        (trie->charmap) and we use a an HV* to store unicode characters. We use the
1185        native representation of the character value as the key and IV's for the
1186        coded index.
1187
1188        *TODO* If we keep track of how many times each character is used we can
1189        remap the columns so that the table compression later on is more
1190        efficient in terms of memory by ensuring most common value is in the
1191        middle and the least common are on the outside.  IMO this would be better
1192        than a most to least common mapping as theres a decent chance the most
1193        common letter will share a node with the least common, meaning the node
1194        will not be compressable. With a middle is most common approach the worst
1195        case is when we have the least common nodes twice.
1196
1197      */
1198
1199     for ( cur = first ; cur < last ; cur = regnext( cur ) ) {
1200         regnode * const noper = NEXTOPER( cur );
1201         const U8 *uc = (U8*)STRING( noper );
1202         const U8 * const e  = uc + STR_LEN( noper );
1203         STRLEN foldlen = 0;
1204         U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ];
1205         const U8 *scan = (U8*)NULL;
1206         U32 wordlen      = 0;         /* required init */
1207         STRLEN chars=0;
1208
1209         TRIE_WORDCOUNT(trie)++;
1210         if (OP(noper) == NOTHING) {
1211             trie->minlen= 0;
1212             continue;
1213         }
1214         if (trie->bitmap) {
1215             TRIE_BITMAP_SET(trie,*uc);
1216             if ( folder ) TRIE_BITMAP_SET(trie,folder[ *uc ]);            
1217         }
1218         for ( ; uc < e ; uc += len ) {
1219             TRIE_CHARCOUNT(trie)++;
1220             TRIE_READ_CHAR;
1221             chars++;
1222             if ( uvc < 256 ) {
1223                 if ( !trie->charmap[ uvc ] ) {
1224                     trie->charmap[ uvc ]=( ++trie->uniquecharcount );
1225                     if ( folder )
1226                         trie->charmap[ folder[ uvc ] ] = trie->charmap[ uvc ];
1227                     TRIE_STORE_REVCHAR;
1228                 }
1229             } else {
1230                 SV** svpp;
1231                 if ( !trie->widecharmap )
1232                     trie->widecharmap = newHV();
1233
1234                 svpp = hv_fetch( trie->widecharmap, (char*)&uvc, sizeof( UV ), 1 );
1235
1236                 if ( !svpp )
1237                     Perl_croak( aTHX_ "error creating/fetching widecharmap entry for 0x%"UVXf, uvc );
1238
1239                 if ( !SvTRUE( *svpp ) ) {
1240                     sv_setiv( *svpp, ++trie->uniquecharcount );
1241                     TRIE_STORE_REVCHAR;
1242                 }
1243             }
1244         }
1245         if( cur == first ) {
1246             trie->minlen=chars;
1247             trie->maxlen=chars;
1248         } else if (chars < trie->minlen) {
1249             trie->minlen=chars;
1250         } else if (chars > trie->maxlen) {
1251             trie->maxlen=chars;
1252         }
1253
1254     } /* end first pass */
1255     DEBUG_TRIE_COMPILE_r(
1256         PerlIO_printf( Perl_debug_log, "%*sTRIE(%s): W:%d C:%d Uq:%d Min:%d Max:%d\n",
1257                 (int)depth * 2 + 2,"",
1258                 ( trie->widecharmap ? "UTF8" : "NATIVE" ), TRIE_WORDCOUNT(trie),
1259                 (int)TRIE_CHARCOUNT(trie), trie->uniquecharcount,
1260                 (int)trie->minlen, (int)trie->maxlen )
1261     );
1262     Newxz( trie->wordlen, TRIE_WORDCOUNT(trie), U32 );
1263
1264     /*
1265         We now know what we are dealing with in terms of unique chars and
1266         string sizes so we can calculate how much memory a naive
1267         representation using a flat table  will take. If it's over a reasonable
1268         limit (as specified by ${^RE_TRIE_MAXBUF}) we use a more memory
1269         conservative but potentially much slower representation using an array
1270         of lists.
1271
1272         At the end we convert both representations into the same compressed
1273         form that will be used in regexec.c for matching with. The latter
1274         is a form that cannot be used to construct with but has memory
1275         properties similar to the list form and access properties similar
1276         to the table form making it both suitable for fast searches and
1277         small enough that its feasable to store for the duration of a program.
1278
1279         See the comment in the code where the compressed table is produced
1280         inplace from the flat tabe representation for an explanation of how
1281         the compression works.
1282
1283     */
1284
1285
1286     if ( (IV)( ( TRIE_CHARCOUNT(trie) + 1 ) * trie->uniquecharcount + 1) > SvIV(re_trie_maxbuff) ) {
1287         /*
1288             Second Pass -- Array Of Lists Representation
1289
1290             Each state will be represented by a list of charid:state records
1291             (reg_trie_trans_le) the first such element holds the CUR and LEN
1292             points of the allocated array. (See defines above).
1293
1294             We build the initial structure using the lists, and then convert
1295             it into the compressed table form which allows faster lookups
1296             (but cant be modified once converted).
1297         */
1298
1299         STRLEN transcount = 1;
1300
1301         Newxz( trie->states, TRIE_CHARCOUNT(trie) + 2, reg_trie_state );
1302         TRIE_LIST_NEW(1);
1303         next_alloc = 2;
1304
1305         for ( cur = first ; cur < last ; cur = regnext( cur ) ) {
1306
1307             regnode * const noper = NEXTOPER( cur );
1308             U8 *uc           = (U8*)STRING( noper );
1309             const U8 * const e = uc + STR_LEN( noper );
1310             U32 state        = 1;         /* required init */
1311             U16 charid       = 0;         /* sanity init */
1312             U8 *scan         = (U8*)NULL; /* sanity init */
1313             STRLEN foldlen   = 0;         /* required init */
1314             U32 wordlen      = 0;         /* required init */
1315             U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ];
1316
1317             if (OP(noper) != NOTHING) {
1318             for ( ; uc < e ; uc += len ) {
1319
1320                 TRIE_READ_CHAR;
1321
1322                 if ( uvc < 256 ) {
1323                     charid = trie->charmap[ uvc ];
1324                 } else {
1325                     SV** const svpp = hv_fetch( trie->widecharmap, (char*)&uvc, sizeof( UV ), 0);
1326                     if ( !svpp ) {
1327                         charid = 0;
1328                     } else {
1329                         charid=(U16)SvIV( *svpp );
1330                     }
1331                 }
1332                 if ( charid ) {
1333
1334                     U16 check;
1335                     U32 newstate = 0;
1336
1337                     charid--;
1338                     if ( !trie->states[ state ].trans.list ) {
1339                         TRIE_LIST_NEW( state );
1340                     }
1341                     for ( check = 1; check <= TRIE_LIST_USED( state ); check++ ) {
1342                         if ( TRIE_LIST_ITEM( state, check ).forid == charid ) {
1343                             newstate = TRIE_LIST_ITEM( state, check ).newstate;
1344                             break;
1345                         }
1346                     }
1347                     if ( ! newstate ) {
1348                         newstate = next_alloc++;
1349                         TRIE_LIST_PUSH( state, charid, newstate );
1350                         transcount++;
1351                     }
1352                     state = newstate;
1353                 } else {
1354                     Perl_croak( aTHX_ "panic! In trie construction, no char mapping for %"IVdf, uvc );
1355                 }
1356                 /* charid is now 0 if we dont know the char read, or nonzero if we do */
1357             }
1358             }
1359             TRIE_HANDLE_WORD(state);
1360
1361         } /* end second pass */
1362
1363         TRIE_LASTSTATE(trie) = next_alloc;
1364         Renew( trie->states, next_alloc, reg_trie_state );
1365
1366         /* and now dump it out before we compress it */
1367         DEBUG_TRIE_COMPILE_MORE_r(
1368             dump_trie_interim_list(trie,next_alloc,depth+1)
1369                     );
1370
1371         Newxz( trie->trans, transcount ,reg_trie_trans );
1372         {
1373             U32 state;
1374             U32 tp = 0;
1375             U32 zp = 0;
1376
1377
1378             for( state=1 ; state < next_alloc ; state ++ ) {
1379                 U32 base=0;
1380
1381                 /*
1382                 DEBUG_TRIE_COMPILE_MORE_r(
1383                     PerlIO_printf( Perl_debug_log, "tp: %d zp: %d ",tp,zp)
1384                 );
1385                 */
1386
1387                 if (trie->states[state].trans.list) {
1388                     U16 minid=TRIE_LIST_ITEM( state, 1).forid;
1389                     U16 maxid=minid;
1390                     U16 idx;
1391
1392                     for( idx = 2 ; idx <= TRIE_LIST_USED( state ) ; idx++ ) {
1393                         const U16 forid = TRIE_LIST_ITEM( state, idx).forid;
1394                         if ( forid < minid ) {
1395                             minid=forid;
1396                         } else if ( forid > maxid ) {
1397                             maxid=forid;
1398                         }
1399                     }
1400                     if ( transcount < tp + maxid - minid + 1) {
1401                         transcount *= 2;
1402                         Renew( trie->trans, transcount, reg_trie_trans );
1403                         Zero( trie->trans + (transcount / 2), transcount / 2 , reg_trie_trans );
1404                     }
1405                     base = trie->uniquecharcount + tp - minid;
1406                     if ( maxid == minid ) {
1407                         U32 set = 0;
1408                         for ( ; zp < tp ; zp++ ) {
1409                             if ( ! trie->trans[ zp ].next ) {
1410                                 base = trie->uniquecharcount + zp - minid;
1411                                 trie->trans[ zp ].next = TRIE_LIST_ITEM( state, 1).newstate;
1412                                 trie->trans[ zp ].check = state;
1413                                 set = 1;
1414                                 break;
1415                             }
1416                         }
1417                         if ( !set ) {
1418                             trie->trans[ tp ].next = TRIE_LIST_ITEM( state, 1).newstate;
1419                             trie->trans[ tp ].check = state;
1420                             tp++;
1421                             zp = tp;
1422                         }
1423                     } else {
1424                         for ( idx=1; idx <= TRIE_LIST_USED( state ) ; idx++ ) {
1425                             const U32 tid = base -  trie->uniquecharcount + TRIE_LIST_ITEM( state, idx ).forid;
1426                             trie->trans[ tid ].next = TRIE_LIST_ITEM( state, idx ).newstate;
1427                             trie->trans[ tid ].check = state;
1428                         }
1429                         tp += ( maxid - minid + 1 );
1430                     }
1431                     Safefree(trie->states[ state ].trans.list);
1432                 }
1433                 /*
1434                 DEBUG_TRIE_COMPILE_MORE_r(
1435                     PerlIO_printf( Perl_debug_log, " base: %d\n",base);
1436                 );
1437                 */
1438                 trie->states[ state ].trans.base=base;
1439             }
1440             trie->lasttrans = tp + 1;
1441         }
1442     } else {
1443         /*
1444            Second Pass -- Flat Table Representation.
1445
1446            we dont use the 0 slot of either trans[] or states[] so we add 1 to each.
1447            We know that we will need Charcount+1 trans at most to store the data
1448            (one row per char at worst case) So we preallocate both structures
1449            assuming worst case.
1450
1451            We then construct the trie using only the .next slots of the entry
1452            structs.
1453
1454            We use the .check field of the first entry of the node  temporarily to
1455            make compression both faster and easier by keeping track of how many non
1456            zero fields are in the node.
1457
1458            Since trans are numbered from 1 any 0 pointer in the table is a FAIL
1459            transition.
1460
1461            There are two terms at use here: state as a TRIE_NODEIDX() which is a
1462            number representing the first entry of the node, and state as a
1463            TRIE_NODENUM() which is the trans number. state 1 is TRIE_NODEIDX(1) and
1464            TRIE_NODENUM(1), state 2 is TRIE_NODEIDX(2) and TRIE_NODENUM(3) if there
1465            are 2 entrys per node. eg:
1466
1467              A B       A B
1468           1. 2 4    1. 3 7
1469           2. 0 3    3. 0 5
1470           3. 0 0    5. 0 0
1471           4. 0 0    7. 0 0
1472
1473            The table is internally in the right hand, idx form. However as we also
1474            have to deal with the states array which is indexed by nodenum we have to
1475            use TRIE_NODENUM() to convert.
1476
1477         */
1478
1479
1480         Newxz( trie->trans, ( TRIE_CHARCOUNT(trie) + 1 ) * trie->uniquecharcount + 1,
1481               reg_trie_trans );
1482         Newxz( trie->states, TRIE_CHARCOUNT(trie) + 2, reg_trie_state );
1483         next_alloc = trie->uniquecharcount + 1;
1484
1485
1486         for ( cur = first ; cur < last ; cur = regnext( cur ) ) {
1487
1488             regnode * const noper   = NEXTOPER( cur );
1489             const U8 *uc     = (U8*)STRING( noper );
1490             const U8 * const e = uc + STR_LEN( noper );
1491
1492             U32 state        = 1;         /* required init */
1493
1494             U16 charid       = 0;         /* sanity init */
1495             U32 accept_state = 0;         /* sanity init */
1496             U8 *scan         = (U8*)NULL; /* sanity init */
1497
1498             STRLEN foldlen   = 0;         /* required init */
1499             U32 wordlen      = 0;         /* required init */
1500             U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ];
1501
1502             if ( OP(noper) != NOTHING ) {
1503             for ( ; uc < e ; uc += len ) {
1504
1505                 TRIE_READ_CHAR;
1506
1507                 if ( uvc < 256 ) {
1508                     charid = trie->charmap[ uvc ];
1509                 } else {
1510                     SV* const * const svpp = hv_fetch( trie->widecharmap, (char*)&uvc, sizeof( UV ), 0);
1511                     charid = svpp ? (U16)SvIV(*svpp) : 0;
1512                 }
1513                 if ( charid ) {
1514                     charid--;
1515                     if ( !trie->trans[ state + charid ].next ) {
1516                         trie->trans[ state + charid ].next = next_alloc;
1517                         trie->trans[ state ].check++;
1518                         next_alloc += trie->uniquecharcount;
1519                     }
1520                     state = trie->trans[ state + charid ].next;
1521                 } else {
1522                     Perl_croak( aTHX_ "panic! In trie construction, no char mapping for %"IVdf, uvc );
1523                 }
1524                 /* charid is now 0 if we dont know the char read, or nonzero if we do */
1525             }
1526             }
1527             accept_state = TRIE_NODENUM( state );
1528             TRIE_HANDLE_WORD(accept_state);
1529
1530         } /* end second pass */
1531
1532         /* and now dump it out before we compress it */
1533         DEBUG_TRIE_COMPILE_MORE_r(
1534             dump_trie_interim_table(trie,next_alloc,depth+1)
1535         );
1536
1537         {
1538         /*
1539            * Inplace compress the table.*
1540
1541            For sparse data sets the table constructed by the trie algorithm will
1542            be mostly 0/FAIL transitions or to put it another way mostly empty.
1543            (Note that leaf nodes will not contain any transitions.)
1544
1545            This algorithm compresses the tables by eliminating most such
1546            transitions, at the cost of a modest bit of extra work during lookup:
1547
1548            - Each states[] entry contains a .base field which indicates the
1549            index in the state[] array wheres its transition data is stored.
1550
1551            - If .base is 0 there are no  valid transitions from that node.
1552
1553            - If .base is nonzero then charid is added to it to find an entry in
1554            the trans array.
1555
1556            -If trans[states[state].base+charid].check!=state then the
1557            transition is taken to be a 0/Fail transition. Thus if there are fail
1558            transitions at the front of the node then the .base offset will point
1559            somewhere inside the previous nodes data (or maybe even into a node
1560            even earlier), but the .check field determines if the transition is
1561            valid.
1562
1563            The following process inplace converts the table to the compressed
1564            table: We first do not compress the root node 1,and mark its all its
1565            .check pointers as 1 and set its .base pointer as 1 as well. This
1566            allows to do a DFA construction from the compressed table later, and
1567            ensures that any .base pointers we calculate later are greater than
1568            0.
1569
1570            - We set 'pos' to indicate the first entry of the second node.
1571
1572            - We then iterate over the columns of the node, finding the first and
1573            last used entry at l and m. We then copy l..m into pos..(pos+m-l),
1574            and set the .check pointers accordingly, and advance pos
1575            appropriately and repreat for the next node. Note that when we copy
1576            the next pointers we have to convert them from the original
1577            NODEIDX form to NODENUM form as the former is not valid post
1578            compression.
1579
1580            - If a node has no transitions used we mark its base as 0 and do not
1581            advance the pos pointer.
1582
1583            - If a node only has one transition we use a second pointer into the
1584            structure to fill in allocated fail transitions from other states.
1585            This pointer is independent of the main pointer and scans forward
1586            looking for null transitions that are allocated to a state. When it
1587            finds one it writes the single transition into the "hole".  If the
1588            pointer doesnt find one the single transition is appeneded as normal.
1589
1590            - Once compressed we can Renew/realloc the structures to release the
1591            excess space.
1592
1593            See "Table-Compression Methods" in sec 3.9 of the Red Dragon,
1594            specifically Fig 3.47 and the associated pseudocode.
1595
1596            demq
1597         */
1598         const U32 laststate = TRIE_NODENUM( next_alloc );
1599         U32 state, charid;
1600         U32 pos = 0, zp=0;
1601         TRIE_LASTSTATE(trie) = laststate;
1602
1603         for ( state = 1 ; state < laststate ; state++ ) {
1604             U8 flag = 0;
1605             const U32 stateidx = TRIE_NODEIDX( state );
1606             const U32 o_used = trie->trans[ stateidx ].check;
1607             U32 used = trie->trans[ stateidx ].check;
1608             trie->trans[ stateidx ].check = 0;
1609
1610             for ( charid = 0 ; used && charid < trie->uniquecharcount ; charid++ ) {
1611                 if ( flag || trie->trans[ stateidx + charid ].next ) {
1612                     if ( trie->trans[ stateidx + charid ].next ) {
1613                         if (o_used == 1) {
1614                             for ( ; zp < pos ; zp++ ) {
1615                                 if ( ! trie->trans[ zp ].next ) {
1616                                     break;
1617                                 }
1618                             }
1619                             trie->states[ state ].trans.base = zp + trie->uniquecharcount - charid ;
1620                             trie->trans[ zp ].next = SAFE_TRIE_NODENUM( trie->trans[ stateidx + charid ].next );
1621                             trie->trans[ zp ].check = state;
1622                             if ( ++zp > pos ) pos = zp;
1623                             break;
1624                         }
1625                         used--;
1626                     }
1627                     if ( !flag ) {
1628                         flag = 1;
1629                         trie->states[ state ].trans.base = pos + trie->uniquecharcount - charid ;
1630                     }
1631                     trie->trans[ pos ].next = SAFE_TRIE_NODENUM( trie->trans[ stateidx + charid ].next );
1632                     trie->trans[ pos ].check = state;
1633                     pos++;
1634                 }
1635             }
1636         }
1637         trie->lasttrans = pos + 1;
1638         Renew( trie->states, laststate + 1, reg_trie_state);
1639         DEBUG_TRIE_COMPILE_MORE_r(
1640                 PerlIO_printf( Perl_debug_log,
1641                     "%*sAlloc: %d Orig: %"IVdf" elements, Final:%"IVdf". Savings of %%%5.2f\n",
1642                     (int)depth * 2 + 2,"",
1643                     (int)( ( TRIE_CHARCOUNT(trie) + 1 ) * trie->uniquecharcount + 1 ),
1644                     (IV)next_alloc,
1645                     (IV)pos,
1646                     ( ( next_alloc - pos ) * 100 ) / (double)next_alloc );
1647             );
1648
1649         } /* end table compress */
1650     }
1651     /* resize the trans array to remove unused space */
1652     Renew( trie->trans, trie->lasttrans, reg_trie_trans);
1653
1654     /* and now dump out the compressed format */
1655     DEBUG_TRIE_COMPILE_r(
1656         dump_trie(trie,depth+1)
1657     );
1658
1659     {   /* Modify the program and insert the new TRIE node*/ 
1660         regnode *convert;
1661         U8 nodetype =(U8)(flags & 0xFF);
1662         char *str=NULL;
1663 #ifdef DEBUGGING
1664         U32 mjd_offset;
1665         U32 mjd_nodelen;
1666 #endif
1667         /*
1668            This means we convert either the first branch or the first Exact,
1669            depending on whether the thing following (in 'last') is a branch
1670            or not and whther first is the startbranch (ie is it a sub part of
1671            the alternation or is it the whole thing.)
1672            Assuming its a sub part we conver the EXACT otherwise we convert
1673            the whole branch sequence, including the first.
1674          */
1675         /* Find the node we are going to overwrite */
1676         if ( first == startbranch && OP( last ) != BRANCH ) {
1677             /* whole branch chain */
1678             convert = first;
1679             DEBUG_r({
1680                 const  regnode *nop = NEXTOPER( convert );
1681                 mjd_offset= Node_Offset((nop));
1682                 mjd_nodelen= Node_Length((nop));
1683             });
1684         } else {
1685             /* branch sub-chain */
1686             convert = NEXTOPER( first );
1687             NEXT_OFF( first ) = (U16)(last - first);
1688             DEBUG_r({
1689                 mjd_offset= Node_Offset((convert));
1690                 mjd_nodelen= Node_Length((convert));
1691             });
1692         }
1693         DEBUG_OPTIMISE_r(
1694             PerlIO_printf(Perl_debug_log, "%*sMJD offset:%"UVuf" MJD length:%"UVuf"\n",
1695                 (int)depth * 2 + 2, "",
1696                 mjd_offset,mjd_nodelen)
1697         );
1698
1699         /* But first we check to see if there is a common prefix we can 
1700            split out as an EXACT and put in front of the TRIE node.  */
1701         trie->startstate= 1;
1702         if ( trie->bitmap && !trie->widecharmap  ) {
1703             U32 state;
1704             DEBUG_OPTIMISE_r(
1705                 PerlIO_printf(Perl_debug_log, "%*sLaststate:%"UVuf"\n",
1706                     (int)depth * 2 + 2, "",
1707                     TRIE_LASTSTATE(trie))
1708             );
1709             for ( state = 1 ; state < TRIE_LASTSTATE(trie)-1 ; state++ ) {
1710                 U32 ofs = 0;
1711                 I32 idx = -1;
1712                 U32 count = 0;
1713                 const U32 base = trie->states[ state ].trans.base;
1714
1715                 if ( trie->states[state].wordnum )
1716                         count = 1;
1717
1718                 for ( ofs = 0 ; ofs < trie->uniquecharcount ; ofs++ ) {
1719                     if ( ( base + ofs >= trie->uniquecharcount ) &&
1720                          ( base + ofs - trie->uniquecharcount < trie->lasttrans ) &&
1721                          trie->trans[ base + ofs - trie->uniquecharcount ].check == state )
1722                     {
1723                         if ( ++count > 1 ) {
1724                             SV **tmp = av_fetch( TRIE_REVCHARMAP(trie), ofs, 0);
1725                             const U8 *ch = (U8*)SvPV_nolen_const( *tmp );
1726                             if ( state == 1 ) break;
1727                             if ( count == 2 ) {
1728                                 Zero(trie->bitmap, ANYOF_BITMAP_SIZE, char);
1729                                 DEBUG_OPTIMISE_r(
1730                                     PerlIO_printf(Perl_debug_log,
1731                                         "%*sNew Start State=%"UVuf" Class: [",
1732                                         (int)depth * 2 + 2, "",
1733                                         state));
1734                                 if (idx >= 0) {
1735                                     SV ** const tmp = av_fetch( TRIE_REVCHARMAP(trie), idx, 0);
1736                                     const U8 * const ch = (U8*)SvPV_nolen_const( *tmp );
1737
1738                                     TRIE_BITMAP_SET(trie,*ch);
1739                                     if ( folder )
1740                                         TRIE_BITMAP_SET(trie, folder[ *ch ]);
1741                                     DEBUG_OPTIMISE_r(
1742                                         PerlIO_printf(Perl_debug_log, (char*)ch)
1743                                     );
1744                                 }
1745                             }
1746                             TRIE_BITMAP_SET(trie,*ch);
1747                             if ( folder )
1748                                 TRIE_BITMAP_SET(trie,folder[ *ch ]);
1749                             DEBUG_OPTIMISE_r(PerlIO_printf( Perl_debug_log,"%s", ch));
1750                         }
1751                         idx = ofs;
1752                     }
1753                 }
1754                 if ( count == 1 ) {
1755                     SV **tmp = av_fetch( TRIE_REVCHARMAP(trie), idx, 0);
1756                     const char *ch = SvPV_nolen_const( *tmp );
1757                     DEBUG_OPTIMISE_r(
1758                         PerlIO_printf( Perl_debug_log,
1759                             "%*sPrefix State: %"UVuf" Idx:%"UVuf" Char='%s'\n",
1760                             (int)depth * 2 + 2, "",
1761                             state, idx, ch)
1762                     );
1763                     if ( state==1 ) {
1764                         OP( convert ) = nodetype;
1765                         str=STRING(convert);
1766                         STR_LEN(convert)=0;
1767                     }
1768                     *str++=*ch;
1769                     STR_LEN(convert)++;
1770
1771                 } else {
1772                     if (state>1)
1773                         DEBUG_OPTIMISE_r(PerlIO_printf( Perl_debug_log,"]\n"));
1774                     break;
1775                 }
1776             }
1777             if (str) {
1778                 regnode *n = convert+NODE_SZ_STR(convert);
1779                 NEXT_OFF(convert) = NODE_SZ_STR(convert);
1780                 trie->startstate = state;
1781                 trie->minlen -= (state - 1);
1782                 trie->maxlen -= (state - 1);
1783                 DEBUG_r({
1784                     regnode *fix = convert;
1785                     mjd_nodelen++;
1786                     Set_Node_Offset_Length(convert, mjd_offset, state - 1);
1787                     while( ++fix < n ) {
1788                         Set_Node_Offset_Length(fix, 0, 0);
1789                     }
1790                 });
1791                 if (trie->maxlen) {
1792                     convert = n;
1793                 } else {
1794                     NEXT_OFF(convert) = (U16)(tail - convert);
1795                 }
1796             }
1797         }
1798         if ( trie->maxlen ) {
1799             OP( convert ) = TRIE;
1800             NEXT_OFF( convert ) = (U16)(tail - convert);
1801             ARG_SET( convert, data_slot );
1802
1803             /* store the type in the flags */
1804             convert->flags = nodetype;
1805             /* XXX We really should free up the resource in trie now, as we wont use them */
1806         }
1807         /* needed for dumping*/
1808         DEBUG_r({
1809             regnode *optimize = convert + NODE_STEP_REGNODE + regarglen[ TRIE ];
1810             regnode *opt = convert;
1811             while (++opt<optimize) {
1812                 Set_Node_Offset_Length(opt,0,0);
1813             }
1814             /* We now need to mark all of the space originally used by the
1815                branches as optimized away. This keeps the dumpuntil from
1816                throwing a wobbly as it doesnt use regnext() to traverse the
1817                opcodes.
1818                We also "fix" the offsets 
1819              */
1820             while( optimize < last ) {
1821                 mjd_nodelen += Node_Length((optimize));
1822                 OP( optimize ) = OPTIMIZED;
1823                 Set_Node_Offset_Length(optimize,0,0);
1824                 optimize++;
1825             }
1826             Set_Node_Offset_Length(convert,mjd_offset,mjd_nodelen);
1827         });
1828     } /* end node insert */
1829 #ifndef DEBUGGING
1830     SvREFCNT_dec(TRIE_REVCHARMAP(trie));
1831 #endif
1832     return 1;
1833 }
1834
1835 /*
1836  * There are strange code-generation bugs caused on sparc64 by gcc-2.95.2.
1837  * These need to be revisited when a newer toolchain becomes available.
1838  */
1839 #if defined(__sparc64__) && defined(__GNUC__)
1840 #   if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 96)
1841 #       undef  SPARC64_GCC_WORKAROUND
1842 #       define SPARC64_GCC_WORKAROUND 1
1843 #   endif
1844 #endif
1845
1846 #define DEBUG_PEEP(str,scan,depth) \
1847     DEBUG_OPTIMISE_r({ \
1848        SV * const mysv=sv_newmortal(); \
1849        regnode *Next = regnext(scan); \
1850        regprop(RExC_rx, mysv, scan); \
1851        PerlIO_printf(Perl_debug_log, "%*s" str ">%3d: %s [%d]\n", \
1852        (int)depth*2, "", REG_NODE_NUM(scan), SvPV_nolen_const(mysv),\
1853        Next ? (REG_NODE_NUM(Next)) : 0 ); \
1854    });
1855
1856 #define JOIN_EXACT(scan,min,flags) \
1857     if (PL_regkind[OP(scan)] == EXACT) \
1858         join_exact(pRExC_state,(scan),(min),(flags),NULL,depth+1)
1859
1860 STATIC U32
1861 S_join_exact(pTHX_ RExC_state_t *pRExC_state, regnode *scan, I32 *min, U32 flags,regnode *val, U32 depth) {
1862     /* Merge several consecutive EXACTish nodes into one. */
1863     regnode *n = regnext(scan);
1864     U32 stringok = 1;
1865     regnode *next = scan + NODE_SZ_STR(scan);
1866     U32 merged = 0;
1867     U32 stopnow = 0;
1868 #ifdef DEBUGGING
1869     regnode *stop = scan;
1870 #endif
1871     GET_RE_DEBUG_FLAGS_DECL;
1872     DEBUG_PEEP("join",scan,depth);
1873     
1874     /* Skip NOTHING, merge EXACT*. */
1875     while (n &&
1876            ( PL_regkind[OP(n)] == NOTHING ||
1877              (stringok && (OP(n) == OP(scan))))
1878            && NEXT_OFF(n)
1879            && NEXT_OFF(scan) + NEXT_OFF(n) < I16_MAX) {
1880         
1881         if (OP(n) == TAIL || n > next)
1882             stringok = 0;
1883         if (PL_regkind[OP(n)] == NOTHING) {
1884         
1885             DEBUG_PEEP("skip:",n,depth);
1886             NEXT_OFF(scan) += NEXT_OFF(n);
1887             next = n + NODE_STEP_REGNODE;
1888 #ifdef DEBUGGING
1889             if (stringok)
1890                 stop = n;
1891 #endif
1892             n = regnext(n);
1893         }
1894         else if (stringok) {
1895             const int oldl = STR_LEN(scan);
1896             regnode * const nnext = regnext(n);
1897             
1898             DEBUG_PEEP("merg",n,depth);
1899             
1900             merged++;
1901             if (oldl + STR_LEN(n) > U8_MAX)
1902                 break;
1903             NEXT_OFF(scan) += NEXT_OFF(n);
1904             STR_LEN(scan) += STR_LEN(n);
1905             next = n + NODE_SZ_STR(n);
1906             /* Now we can overwrite *n : */
1907             Move(STRING(n), STRING(scan) + oldl, STR_LEN(n), char);
1908 #ifdef DEBUGGING
1909             stop = next - 1;
1910 #endif
1911             n = nnext;
1912             if (stopnow) break;
1913         }
1914
1915 #ifdef  EXPERIMENTAL_INPLACESCAN
1916         if (flags && !NEXT_OFF(n)) {
1917             DEBUG_PEEP("atch",val,depth);            
1918             if (reg_off_by_arg[OP(n)]) {
1919                 ARG_SET(n, val - n);
1920             }
1921             else {
1922                 NEXT_OFF(n) = val - n;
1923             }
1924             stopnow=1;
1925         }            
1926 #endif
1927     }
1928     
1929     if (UTF && ( OP(scan) == EXACTF ) && ( STR_LEN(scan) >= 6 ) ) {
1930     /*
1931     Two problematic code points in Unicode casefolding of EXACT nodes:
1932     
1933     U+0390 - GREEK SMALL LETTER IOTA WITH DIALYTIKA AND TONOS
1934     U+03B0 - GREEK SMALL LETTER UPSILON WITH DIALYTIKA AND TONOS
1935     
1936     which casefold to
1937     
1938     Unicode                      UTF-8
1939     
1940     U+03B9 U+0308 U+0301         0xCE 0xB9 0xCC 0x88 0xCC 0x81
1941     U+03C5 U+0308 U+0301         0xCF 0x85 0xCC 0x88 0xCC 0x81
1942     
1943     This means that in case-insensitive matching (or "loose matching",
1944     as Unicode calls it), an EXACTF of length six (the UTF-8 encoded byte
1945     length of the above casefolded versions) can match a target string
1946     of length two (the byte length of UTF-8 encoded U+0390 or U+03B0).
1947     This would rather mess up the minimum length computation.
1948     
1949     What we'll do is to look for the tail four bytes, and then peek
1950     at the preceding two bytes to see whether we need to decrease
1951     the minimum length by four (six minus two).
1952     
1953     Thanks to the design of UTF-8, there cannot be false matches:
1954     A sequence of valid UTF-8 bytes cannot be a subsequence of
1955     another valid sequence of UTF-8 bytes.
1956     
1957     */
1958          char * const s0 = STRING(scan), *s, *t;
1959          char * const s1 = s0 + STR_LEN(scan) - 1;
1960          char * const s2 = s1 - 4;
1961          const char t0[] = "\xcc\x88\xcc\x81";
1962          const char * const t1 = t0 + 3;
1963     
1964          for (s = s0 + 2;
1965               s < s2 && (t = ninstr(s, s1, t0, t1));
1966               s = t + 4) {
1967               if (((U8)t[-1] == 0xB9 && (U8)t[-2] == 0xCE) ||
1968                   ((U8)t[-1] == 0x85 && (U8)t[-2] == 0xCF))
1969                    *min -= 4;
1970          }
1971     }
1972     
1973 #ifdef DEBUGGING
1974     /* Allow dumping */
1975     n = scan + NODE_SZ_STR(scan);
1976     while (n <= stop) {
1977         if (PL_regkind[OP(n)] != NOTHING || OP(n) == NOTHING) {
1978             OP(n) = OPTIMIZED;
1979             NEXT_OFF(n) = 0;
1980         }
1981         n++;
1982     }
1983 #endif
1984     DEBUG_OPTIMISE_r(if (merged){DEBUG_PEEP("finl",scan,depth)});
1985     return stopnow;
1986 }
1987
1988 /* REx optimizer.  Converts nodes into quickier variants "in place".
1989    Finds fixed substrings.  */
1990
1991 /* Stops at toplevel WHILEM as well as at "last". At end *scanp is set
1992    to the position after last scanned or to NULL. */
1993
1994
1995
1996 STATIC I32
1997 S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap,
1998                         regnode *last, scan_data_t *data, U32 flags, U32 depth)
1999                         /* scanp: Start here (read-write). */
2000                         /* deltap: Write maxlen-minlen here. */
2001                         /* last: Stop before this one. */
2002 {
2003     dVAR;
2004     I32 min = 0, pars = 0, code;
2005     regnode *scan = *scanp, *next;
2006     I32 delta = 0;
2007     int is_inf = (flags & SCF_DO_SUBSTR) && (data->flags & SF_IS_INF);
2008     int is_inf_internal = 0;            /* The studied chunk is infinite */
2009     I32 is_par = OP(scan) == OPEN ? ARG(scan) : 0;
2010     scan_data_t data_fake;
2011     struct regnode_charclass_class and_with; /* Valid if flags & SCF_DO_STCLASS_OR */
2012     SV *re_trie_maxbuff = NULL;
2013
2014     GET_RE_DEBUG_FLAGS_DECL;
2015 #ifdef DEBUGGING
2016     StructCopy(&zero_scan_data, &data_fake, scan_data_t);    
2017 #endif
2018
2019     while (scan && OP(scan) != END && scan < last) {
2020         /* Peephole optimizer: */
2021         DEBUG_PEEP("Peep",scan,depth);
2022
2023         JOIN_EXACT(scan,&min,0);
2024
2025         /* Follow the next-chain of the current node and optimize
2026            away all the NOTHINGs from it.  */
2027         if (OP(scan) != CURLYX) {
2028             const int max = (reg_off_by_arg[OP(scan)]
2029                        ? I32_MAX
2030                        /* I32 may be smaller than U16 on CRAYs! */
2031                        : (I32_MAX < U16_MAX ? I32_MAX : U16_MAX));
2032             int off = (reg_off_by_arg[OP(scan)] ? ARG(scan) : NEXT_OFF(scan));
2033             int noff;
2034             regnode *n = scan;
2035         
2036             /* Skip NOTHING and LONGJMP. */
2037             while ((n = regnext(n))
2038                    && ((PL_regkind[OP(n)] == NOTHING && (noff = NEXT_OFF(n)))
2039                        || ((OP(n) == LONGJMP) && (noff = ARG(n))))
2040                    && off + noff < max)
2041                 off += noff;
2042             if (reg_off_by_arg[OP(scan)])
2043                 ARG(scan) = off;
2044             else
2045                 NEXT_OFF(scan) = off;
2046         }
2047
2048
2049
2050         /* The principal pseudo-switch.  Cannot be a switch, since we
2051            look into several different things.  */
2052         if (OP(scan) == BRANCH || OP(scan) == BRANCHJ
2053                    || OP(scan) == IFTHEN || OP(scan) == SUSPEND) {
2054             next = regnext(scan);
2055             code = OP(scan);
2056             /* demq: the op(next)==code check is to see if we have "branch-branch" AFAICT */
2057         
2058             if (OP(next) == code || code == IFTHEN || code == SUSPEND) {
2059                 I32 max1 = 0, min1 = I32_MAX, num = 0;
2060                 struct regnode_charclass_class accum;
2061                 regnode * const startbranch=scan;
2062                 
2063                 if (flags & SCF_DO_SUBSTR) /* XXXX Add !SUSPEND? */
2064                     scan_commit(pRExC_state, data); /* Cannot merge strings after this. */
2065                 if (flags & SCF_DO_STCLASS)
2066                     cl_init_zero(pRExC_state, &accum);
2067
2068                 while (OP(scan) == code) {
2069                     I32 deltanext, minnext, f = 0, fake;
2070                     struct regnode_charclass_class this_class;
2071
2072                     num++;
2073                     data_fake.flags = 0;
2074                     if (data) {         
2075                         data_fake.whilem_c = data->whilem_c;
2076                         data_fake.last_closep = data->last_closep;
2077                     }
2078                     else
2079                         data_fake.last_closep = &fake;
2080                     next = regnext(scan);
2081                     scan = NEXTOPER(scan);
2082                     if (code != BRANCH)
2083                         scan = NEXTOPER(scan);
2084                     if (flags & SCF_DO_STCLASS) {
2085                         cl_init(pRExC_state, &this_class);
2086                         data_fake.start_class = &this_class;
2087                         f = SCF_DO_STCLASS_AND;
2088                     }           
2089                     if (flags & SCF_WHILEM_VISITED_POS)
2090                         f |= SCF_WHILEM_VISITED_POS;
2091
2092                     /* we suppose the run is continuous, last=next...*/
2093                     minnext = study_chunk(pRExC_state, &scan, &deltanext,
2094                                           next, &data_fake, f,depth+1);
2095                     if (min1 > minnext)
2096                         min1 = minnext;
2097                     if (max1 < minnext + deltanext)
2098                         max1 = minnext + deltanext;
2099                     if (deltanext == I32_MAX)
2100                         is_inf = is_inf_internal = 1;
2101                     scan = next;
2102                     if (data_fake.flags & (SF_HAS_PAR|SF_IN_PAR))
2103                         pars++;
2104                     if (data) {
2105                         if (data_fake.flags & SF_HAS_EVAL)
2106                             data->flags |= SF_HAS_EVAL;
2107                         data->whilem_c = data_fake.whilem_c;
2108                     }
2109                     if (flags & SCF_DO_STCLASS)
2110                         cl_or(pRExC_state, &accum, &this_class);
2111                     if (code == SUSPEND)
2112                         break;
2113                 }
2114                 if (code == IFTHEN && num < 2) /* Empty ELSE branch */
2115                     min1 = 0;
2116                 if (flags & SCF_DO_SUBSTR) {
2117                     data->pos_min += min1;
2118                     data->pos_delta += max1 - min1;
2119                     if (max1 != min1 || is_inf)
2120                         data->longest = &(data->longest_float);
2121                 }
2122                 min += min1;
2123                 delta += max1 - min1;
2124                 if (flags & SCF_DO_STCLASS_OR) {
2125                     cl_or(pRExC_state, data->start_class, &accum);
2126                     if (min1) {
2127                         cl_and(data->start_class, &and_with);
2128                         flags &= ~SCF_DO_STCLASS;
2129                     }
2130                 }
2131                 else if (flags & SCF_DO_STCLASS_AND) {
2132                     if (min1) {
2133                         cl_and(data->start_class, &accum);
2134                         flags &= ~SCF_DO_STCLASS;
2135                     }
2136                     else {
2137                         /* Switch to OR mode: cache the old value of
2138                          * data->start_class */
2139                         StructCopy(data->start_class, &and_with,
2140                                    struct regnode_charclass_class);
2141                         flags &= ~SCF_DO_STCLASS_AND;
2142                         StructCopy(&accum, data->start_class,
2143                                    struct regnode_charclass_class);
2144                         flags |= SCF_DO_STCLASS_OR;
2145                         data->start_class->flags |= ANYOF_EOS;
2146                     }
2147                 }
2148
2149                 /* demq.
2150
2151                    Assuming this was/is a branch we are dealing with: 'scan' now
2152                    points at the item that follows the branch sequence, whatever
2153                    it is. We now start at the beginning of the sequence and look
2154                    for subsequences of
2155
2156                    BRANCH->EXACT=>X
2157                    BRANCH->EXACT=>X
2158
2159                    which would be constructed from a pattern like /A|LIST|OF|WORDS/
2160
2161                    If we can find such a subseqence we need to turn the first
2162                    element into a trie and then add the subsequent branch exact
2163                    strings to the trie.
2164
2165                    We have two cases
2166
2167                      1. patterns where the whole set of branch can be converted to a trie,
2168
2169                      2. patterns where only a subset of the alternations can be
2170                      converted to a trie.
2171
2172                    In case 1 we can replace the whole set with a single regop
2173                    for the trie. In case 2 we need to keep the start and end
2174                    branchs so
2175
2176                      'BRANCH EXACT; BRANCH EXACT; BRANCH X'
2177                      becomes BRANCH TRIE; BRANCH X;
2178
2179                    Hypthetically when we know the regex isnt anchored we can
2180                    turn a case 1 into a DFA and let it rip... Every time it finds a match
2181                    it would just call its tail, no WHILEM/CURLY needed.
2182
2183                 */
2184                 if (PERL_ENABLE_TRIE_OPTIMISATION) {
2185                     int made=0;
2186                     if (!re_trie_maxbuff) {
2187                         re_trie_maxbuff = get_sv(RE_TRIE_MAXBUF_NAME, 1);
2188                         if (!SvIOK(re_trie_maxbuff))
2189                             sv_setiv(re_trie_maxbuff, RE_TRIE_MAXBUF_INIT);
2190                     }
2191                     if ( SvIV(re_trie_maxbuff)>=0 && OP( startbranch )==BRANCH ) {
2192                         regnode *cur;
2193                         regnode *first = (regnode *)NULL;
2194                         regnode *last = (regnode *)NULL;
2195                         regnode *tail = scan;
2196                         U8 optype = 0;
2197                         U32 count=0;
2198
2199 #ifdef DEBUGGING
2200                         SV * const mysv = sv_newmortal();       /* for dumping */
2201 #endif
2202                         /* var tail is used because there may be a TAIL
2203                            regop in the way. Ie, the exacts will point to the
2204                            thing following the TAIL, but the last branch will
2205                            point at the TAIL. So we advance tail. If we
2206                            have nested (?:) we may have to move through several
2207                            tails.
2208                          */
2209
2210                         while ( OP( tail ) == TAIL ) {
2211                             /* this is the TAIL generated by (?:) */
2212                             tail = regnext( tail );
2213                         }
2214
2215                         
2216                         DEBUG_OPTIMISE_r({
2217                             regprop(RExC_rx, mysv, tail );
2218                             PerlIO_printf( Perl_debug_log, "%*s%s%s\n",
2219                                 (int)depth * 2 + 2, "", 
2220                                 "Looking for TRIE'able sequences. Tail node is: ", 
2221                                 SvPV_nolen_const( mysv )
2222                             );
2223                         });
2224                         
2225                         /*
2226
2227                            step through the branches, cur represents each
2228                            branch, noper is the first thing to be matched
2229                            as part of that branch and noper_next is the
2230                            regnext() of that node. if noper is an EXACT
2231                            and noper_next is the same as scan (our current
2232                            position in the regex) then the EXACT branch is
2233                            a possible optimization target. Once we have
2234                            two or more consequetive such branches we can
2235                            create a trie of the EXACT's contents and stich
2236                            it in place. If the sequence represents all of
2237                            the branches we eliminate the whole thing and
2238                            replace it with a single TRIE. If it is a
2239                            subsequence then we need to stitch it in. This
2240                            means the first branch has to remain, and needs
2241                            to be repointed at the item on the branch chain
2242                            following the last branch optimized. This could
2243                            be either a BRANCH, in which case the
2244                            subsequence is internal, or it could be the
2245                            item following the branch sequence in which
2246                            case the subsequence is at the end.
2247
2248                         */
2249
2250                         /* dont use tail as the end marker for this traverse */
2251                         for ( cur = startbranch ; cur != scan ; cur = regnext( cur ) ) {
2252                             regnode * const noper = NEXTOPER( cur );
2253                             regnode * const noper_next = regnext( noper );
2254
2255                             DEBUG_OPTIMISE_r({
2256                                 regprop(RExC_rx, mysv, cur);
2257                                 PerlIO_printf( Perl_debug_log, "%*s- %s (%d)",
2258                                    (int)depth * 2 + 2,"", SvPV_nolen_const( mysv ), REG_NODE_NUM(cur) );
2259
2260                                 regprop(RExC_rx, mysv, noper);
2261                                 PerlIO_printf( Perl_debug_log, " -> %s",
2262                                     SvPV_nolen_const(mysv));
2263
2264                                 if ( noper_next ) {
2265                                   regprop(RExC_rx, mysv, noper_next );
2266                                   PerlIO_printf( Perl_debug_log,"\t=> %s\t",
2267                                     SvPV_nolen_const(mysv));
2268                                 }
2269                                 PerlIO_printf( Perl_debug_log, "(First==%d,Last==%d,Cur==%d)\n",
2270                                    REG_NODE_NUM(first), REG_NODE_NUM(last), REG_NODE_NUM(cur) );
2271                             });
2272                             if ( (((first && optype!=NOTHING) ? OP( noper ) == optype
2273                                          : PL_regkind[ OP( noper ) ] == EXACT )
2274                                   || OP(noper) == NOTHING )
2275                                   && noper_next == tail && count<U16_MAX)
2276                             {
2277                                 count++;
2278                                 if ( !first || optype == NOTHING ) {
2279                                     if (!first) first = cur;
2280                                     optype = OP( noper );
2281                                 } else {
2282                                     last = cur;
2283                                 }
2284                             } else {
2285                                 if ( last ) {
2286                                     made+=make_trie( pRExC_state, startbranch, first, cur, tail, optype, depth+1 );
2287                                 }
2288                                 if ( PL_regkind[ OP( noper ) ] == EXACT
2289                                      && noper_next == tail )
2290                                 {
2291                                     count = 1;
2292                                     first = cur;
2293                                     optype = OP( noper );
2294                                 } else {
2295                                     count = 0;
2296                                     first = NULL;
2297                                     optype = 0;
2298                                 }
2299                                 last = NULL;
2300                             }
2301                         }
2302                         DEBUG_OPTIMISE_r({
2303                             regprop(RExC_rx, mysv, cur);
2304                             PerlIO_printf( Perl_debug_log,
2305                               "%*s- %s (%d) <SCAN FINISHED>\n", (int)depth * 2 + 2,
2306                               "", SvPV_nolen_const( mysv ),REG_NODE_NUM(cur));
2307
2308                         });
2309                         if ( last ) {
2310                             made+= make_trie( pRExC_state, startbranch, first, scan, tail, optype, depth+1 );
2311 #ifdef TRIE_STUDY_OPT   
2312                             if ( made && startbranch == first ) {
2313                                 if ( OP(first)!=TRIE )
2314                                     flags |= SCF_EXACT_TRIE;
2315                                 else {
2316                                     regnode *chk=*scanp;
2317                                     while ( OP( chk ) == OPEN ) 
2318                                         chk = regnext( chk );
2319                                     if (chk==first) 
2320                                         flags |= SCF_EXACT_TRIE;
2321                                 }
2322                             }                   
2323 #endif
2324                         }
2325                     }
2326                     
2327                 } /* do trie */
2328             }
2329             else if ( code == BRANCHJ ) {  /* single branch is optimized. */
2330                 scan = NEXTOPER(NEXTOPER(scan));
2331             } else                      /* single branch is optimized. */
2332                 scan = NEXTOPER(scan);
2333             continue;
2334         }
2335         else if (OP(scan) == EXACT) {
2336             I32 l = STR_LEN(scan);
2337             UV uc;
2338             if (UTF) {
2339                 const U8 * const s = (U8*)STRING(scan);
2340                 l = utf8_length(s, s + l);
2341                 uc = utf8_to_uvchr(s, NULL);
2342             } else {
2343                 uc = *((U8*)STRING(scan));
2344             }
2345             min += l;
2346             if (flags & SCF_DO_SUBSTR) { /* Update longest substr. */
2347                 /* The code below prefers earlier match for fixed
2348                    offset, later match for variable offset.  */
2349                 if (data->last_end == -1) { /* Update the start info. */
2350                     data->last_start_min = data->pos_min;
2351                     data->last_start_max = is_inf
2352                         ? I32_MAX : data->pos_min + data->pos_delta;
2353                 }
2354                 sv_catpvn(data->last_found, STRING(scan), STR_LEN(scan));
2355                 if (UTF)
2356                     SvUTF8_on(data->last_found);
2357                 {
2358                     SV * const sv = data->last_found;
2359                     MAGIC * const mg = SvUTF8(sv) && SvMAGICAL(sv) ?
2360                         mg_find(sv, PERL_MAGIC_utf8) : NULL;
2361                     if (mg && mg->mg_len >= 0)
2362                         mg->mg_len += utf8_length((U8*)STRING(scan),
2363                                                   (U8*)STRING(scan)+STR_LEN(scan));
2364                 }
2365                 data->last_end = data->pos_min + l;
2366                 data->pos_min += l; /* As in the first entry. */
2367                 data->flags &= ~SF_BEFORE_EOL;
2368             }
2369             if (flags & SCF_DO_STCLASS_AND) {
2370                 /* Check whether it is compatible with what we know already! */
2371                 int compat = 1;
2372
2373                 if (uc >= 0x100 ||
2374                     (!(data->start_class->flags & (ANYOF_CLASS | ANYOF_LOCALE))
2375                     && !ANYOF_BITMAP_TEST(data->start_class, uc)
2376                     && (!(data->start_class->flags & ANYOF_FOLD)
2377                         || !ANYOF_BITMAP_TEST(data->start_class, PL_fold[uc])))
2378                     )
2379                     compat = 0;
2380                 ANYOF_CLASS_ZERO(data->start_class);
2381                 ANYOF_BITMAP_ZERO(data->start_class);
2382                 if (compat)
2383                     ANYOF_BITMAP_SET(data->start_class, uc);
2384                 data->start_class->flags &= ~ANYOF_EOS;
2385                 if (uc < 0x100)
2386                   data->start_class->flags &= ~ANYOF_UNICODE_ALL;
2387             }
2388             else if (flags & SCF_DO_STCLASS_OR) {
2389                 /* false positive possible if the class is case-folded */
2390                 if (uc < 0x100)
2391                     ANYOF_BITMAP_SET(data->start_class, uc);
2392                 else
2393                     data->start_class->flags |= ANYOF_UNICODE_ALL;
2394                 data->start_class->flags &= ~ANYOF_EOS;
2395                 cl_and(data->start_class, &and_with);
2396             }
2397             flags &= ~SCF_DO_STCLASS;
2398         }
2399         else if (PL_regkind[OP(scan)] == EXACT) { /* But OP != EXACT! */
2400             I32 l = STR_LEN(scan);
2401             UV uc = *((U8*)STRING(scan));
2402
2403             /* Search for fixed substrings supports EXACT only. */
2404             if (flags & SCF_DO_SUBSTR) {
2405                 assert(data);
2406                 scan_commit(pRExC_state, data);
2407             }
2408             if (UTF) {
2409                 const U8 * const s = (U8 *)STRING(scan);
2410                 l = utf8_length(s, s + l);
2411                 uc = utf8_to_uvchr(s, NULL);
2412             }
2413             min += l;
2414             if (flags & SCF_DO_SUBSTR)
2415                 data->pos_min += l;
2416             if (flags & SCF_DO_STCLASS_AND) {
2417                 /* Check whether it is compatible with what we know already! */
2418                 int compat = 1;
2419
2420                 if (uc >= 0x100 ||
2421                     (!(data->start_class->flags & (ANYOF_CLASS | ANYOF_LOCALE))
2422                     && !ANYOF_BITMAP_TEST(data->start_class, uc)
2423                      && !ANYOF_BITMAP_TEST(data->start_class, PL_fold[uc])))
2424                     compat = 0;
2425                 ANYOF_CLASS_ZERO(data->start_class);
2426                 ANYOF_BITMAP_ZERO(data->start_class);
2427                 if (compat) {
2428                     ANYOF_BITMAP_SET(data->start_class, uc);
2429                     data->start_class->flags &= ~ANYOF_EOS;
2430                     data->start_class->flags |= ANYOF_FOLD;
2431                     if (OP(scan) == EXACTFL)
2432                         data->start_class->flags |= ANYOF_LOCALE;
2433                 }
2434             }
2435             else if (flags & SCF_DO_STCLASS_OR) {
2436                 if (data->start_class->flags & ANYOF_FOLD) {
2437                     /* false positive possible if the class is case-folded.
2438                        Assume that the locale settings are the same... */
2439                     if (uc < 0x100)
2440                         ANYOF_BITMAP_SET(data->start_class, uc);
2441                     data->start_class->flags &= ~ANYOF_EOS;
2442                 }
2443                 cl_and(data->start_class, &and_with);
2444             }
2445             flags &= ~SCF_DO_STCLASS;
2446         }
2447 #ifdef TRIE_STUDY_OPT   
2448         else if (OP(scan) == TRIE) {
2449             reg_trie_data *trie=RExC_rx->data->data[ ARG(scan) ];
2450             min += trie->minlen;
2451             delta += (trie->maxlen - trie->minlen);
2452             flags &= ~SCF_DO_STCLASS; /* xxx */
2453             if (flags & SCF_DO_SUBSTR) {
2454                 scan_commit(pRExC_state,data);  /* Cannot expect anything... */
2455                 data->pos_min += trie->minlen;
2456                 data->pos_delta += (trie->maxlen - trie->minlen);
2457                 if (trie->maxlen != trie->minlen)
2458                     data->longest = &(data->longest_float);
2459             }
2460         }
2461 #endif  
2462         else if (strchr((const char*)PL_varies,OP(scan))) {
2463             I32 mincount, maxcount, minnext, deltanext, fl = 0;
2464             I32 f = flags, pos_before = 0;
2465             regnode * const oscan = scan;
2466             struct regnode_charclass_class this_class;
2467             struct regnode_charclass_class *oclass = NULL;
2468             I32 next_is_eval = 0;
2469
2470             switch (PL_regkind[OP(scan)]) {
2471             case WHILEM:                /* End of (?:...)* . */
2472                 scan = NEXTOPER(scan);
2473                 goto finish;
2474             case PLUS:
2475                 if (flags & (SCF_DO_SUBSTR | SCF_DO_STCLASS)) {
2476                     next = NEXTOPER(scan);
2477                     if (OP(next) == EXACT || (flags & SCF_DO_STCLASS)) {
2478                         mincount = 1;
2479                         maxcount = REG_INFTY;
2480                         next = regnext(scan);
2481                         scan = NEXTOPER(scan);
2482                         goto do_curly;
2483                     }
2484                 }
2485                 if (flags & SCF_DO_SUBSTR)
2486                     data->pos_min++;
2487                 min++;
2488                 /* Fall through. */
2489             case STAR:
2490                 if (flags & SCF_DO_STCLASS) {
2491                     mincount = 0;
2492                     maxcount = REG_INFTY;
2493                     next = regnext(scan);
2494                     scan = NEXTOPER(scan);
2495                     goto do_curly;
2496                 }
2497                 is_inf = is_inf_internal = 1;
2498                 scan = regnext(scan);
2499                 if (flags & SCF_DO_SUBSTR) {
2500                     scan_commit(pRExC_state, data); /* Cannot extend fixed substrings */
2501                     data->longest = &(data->longest_float);
2502                 }
2503                 goto optimize_curly_tail;
2504             case CURLY:
2505                 mincount = ARG1(scan);
2506                 maxcount = ARG2(scan);
2507                 next = regnext(scan);
2508                 if (OP(scan) == CURLYX) {
2509                     I32 lp = (data ? *(data->last_closep) : 0);
2510                     scan->flags = ((lp <= U8_MAX) ? (U8)lp : U8_MAX);
2511                 }
2512                 scan = NEXTOPER(scan) + EXTRA_STEP_2ARGS;
2513                 next_is_eval = (OP(scan) == EVAL);
2514               do_curly:
2515                 if (flags & SCF_DO_SUBSTR) {
2516                     if (mincount == 0) scan_commit(pRExC_state,data); /* Cannot extend fixed substrings */
2517                     pos_before = data->pos_min;
2518                 }
2519                 if (data) {
2520                     fl = data->flags;
2521                     data->flags &= ~(SF_HAS_PAR|SF_IN_PAR|SF_HAS_EVAL);
2522                     if (is_inf)
2523                         data->flags |= SF_IS_INF;
2524                 }
2525                 if (flags & SCF_DO_STCLASS) {
2526                     cl_init(pRExC_state, &this_class);
2527                     oclass = data->start_class;
2528                     data->start_class = &this_class;
2529                     f |= SCF_DO_STCLASS_AND;
2530                     f &= ~SCF_DO_STCLASS_OR;
2531                 }
2532                 /* These are the cases when once a subexpression
2533                    fails at a particular position, it cannot succeed
2534                    even after backtracking at the enclosing scope.
2535                 
2536                    XXXX what if minimal match and we are at the
2537                         initial run of {n,m}? */
2538                 if ((mincount != maxcount - 1) && (maxcount != REG_INFTY))
2539                     f &= ~SCF_WHILEM_VISITED_POS;
2540
2541                 /* This will finish on WHILEM, setting scan, or on NULL: */
2542                 minnext = study_chunk(pRExC_state, &scan, &deltanext, last, data,
2543                                       (mincount == 0
2544                                         ? (f & ~SCF_DO_SUBSTR) : f),depth+1);
2545
2546                 if (flags & SCF_DO_STCLASS)
2547                     data->start_class = oclass;
2548                 if (mincount == 0 || minnext == 0) {
2549                     if (flags & SCF_DO_STCLASS_OR) {
2550                         cl_or(pRExC_state, data->start_class, &this_class);
2551                     }
2552                     else if (flags & SCF_DO_STCLASS_AND) {
2553                         /* Switch to OR mode: cache the old value of
2554                          * data->start_class */
2555                         StructCopy(data->start_class, &and_with,
2556                                    struct regnode_charclass_class);
2557                         flags &= ~SCF_DO_STCLASS_AND;
2558                         StructCopy(&this_class, data->start_class,
2559                                    struct regnode_charclass_class);
2560                         flags |= SCF_DO_STCLASS_OR;
2561                         data->start_class->flags |= ANYOF_EOS;
2562                     }
2563                 } else {                /* Non-zero len */
2564                     if (flags & SCF_DO_STCLASS_OR) {
2565                         cl_or(pRExC_state, data->start_class, &this_class);
2566                         cl_and(data->start_class, &and_with);
2567                     }
2568                     else if (flags & SCF_DO_STCLASS_AND)
2569                         cl_and(data->start_class, &this_class);
2570                     flags &= ~SCF_DO_STCLASS;
2571                 }
2572                 if (!scan)              /* It was not CURLYX, but CURLY. */
2573                     scan = next;
2574                 if ( /* ? quantifier ok, except for (?{ ... }) */
2575                     (next_is_eval || !(mincount == 0 && maxcount == 1))
2576                     && (minnext == 0) && (deltanext == 0)
2577                     && data && !(data->flags & (SF_HAS_PAR|SF_IN_PAR))
2578                     && maxcount <= REG_INFTY/3 /* Complement check for big count */
2579                     && ckWARN(WARN_REGEXP))
2580                 {
2581                     vWARN(RExC_parse,
2582                           "Quantifier unexpected on zero-length expression");
2583                 }
2584
2585                 min += minnext * mincount;
2586                 is_inf_internal |= ((maxcount == REG_INFTY
2587                                      && (minnext + deltanext) > 0)
2588                                     || deltanext == I32_MAX);
2589                 is_inf |= is_inf_internal;
2590                 delta += (minnext + deltanext) * maxcount - minnext * mincount;
2591
2592                 /* Try powerful optimization CURLYX => CURLYN. */
2593                 if (  OP(oscan) == CURLYX && data
2594                       && data->flags & SF_IN_PAR
2595                       && !(data->flags & SF_HAS_EVAL)
2596                       && !deltanext && minnext == 1 ) {
2597                     /* Try to optimize to CURLYN.  */
2598                     regnode *nxt = NEXTOPER(oscan) + EXTRA_STEP_2ARGS;
2599                     regnode * const nxt1 = nxt;
2600 #ifdef DEBUGGING
2601                     regnode *nxt2;
2602 #endif
2603
2604                     /* Skip open. */
2605                     nxt = regnext(nxt);
2606                     if (!strchr((const char*)PL_simple,OP(nxt))
2607                         && !(PL_regkind[OP(nxt)] == EXACT
2608                              && STR_LEN(nxt) == 1))
2609                         goto nogo;
2610 #ifdef DEBUGGING
2611                     nxt2 = nxt;
2612 #endif
2613                     nxt = regnext(nxt);
2614                     if (OP(nxt) != CLOSE)
2615                         goto nogo;
2616                     /* Now we know that nxt2 is the only contents: */
2617                     oscan->flags = (U8)ARG(nxt);
2618                     OP(oscan) = CURLYN;
2619                     OP(nxt1) = NOTHING; /* was OPEN. */
2620 #ifdef DEBUGGING
2621                     OP(nxt1 + 1) = OPTIMIZED; /* was count. */
2622                     NEXT_OFF(nxt1+ 1) = 0; /* just for consistancy. */
2623                     NEXT_OFF(nxt2) = 0; /* just for consistancy with CURLY. */
2624                     OP(nxt) = OPTIMIZED;        /* was CLOSE. */
2625                     OP(nxt + 1) = OPTIMIZED; /* was count. */
2626                     NEXT_OFF(nxt+ 1) = 0; /* just for consistancy. */
2627 #endif
2628                 }
2629               nogo:
2630
2631                 /* Try optimization CURLYX => CURLYM. */
2632                 if (  OP(oscan) == CURLYX && data
2633                       && !(data->flags & SF_HAS_PAR)
2634                       && !(data->flags & SF_HAS_EVAL)
2635                       && !deltanext     /* atom is fixed width */
2636                       && minnext != 0   /* CURLYM can't handle zero width */
2637                 ) {
2638                     /* XXXX How to optimize if data == 0? */
2639                     /* Optimize to a simpler form.  */
2640                     regnode *nxt = NEXTOPER(oscan) + EXTRA_STEP_2ARGS; /* OPEN */
2641                     regnode *nxt2;
2642
2643                     OP(oscan) = CURLYM;
2644                     while ( (nxt2 = regnext(nxt)) /* skip over embedded stuff*/
2645                             && (OP(nxt2) != WHILEM))
2646                         nxt = nxt2;
2647                     OP(nxt2)  = SUCCEED; /* Whas WHILEM */
2648                     /* Need to optimize away parenths. */
2649                     if (data->flags & SF_IN_PAR) {
2650                         /* Set the parenth number.  */
2651                         regnode *nxt1 = NEXTOPER(oscan) + EXTRA_STEP_2ARGS; /* OPEN*/
2652
2653                         if (OP(nxt) != CLOSE)
2654                             FAIL("Panic opt close");
2655                         oscan->flags = (U8)ARG(nxt);
2656                         OP(nxt1) = OPTIMIZED;   /* was OPEN. */
2657                         OP(nxt) = OPTIMIZED;    /* was CLOSE. */
2658 #ifdef DEBUGGING
2659                         OP(nxt1 + 1) = OPTIMIZED; /* was count. */
2660                         OP(nxt + 1) = OPTIMIZED; /* was count. */
2661                         NEXT_OFF(nxt1 + 1) = 0; /* just for consistancy. */
2662                         NEXT_OFF(nxt + 1) = 0; /* just for consistancy. */
2663 #endif
2664 #if 0
2665                         while ( nxt1 && (OP(nxt1) != WHILEM)) {
2666                             regnode *nnxt = regnext(nxt1);
2667                         
2668                             if (nnxt == nxt) {
2669                                 if (reg_off_by_arg[OP(nxt1)])
2670                                     ARG_SET(nxt1, nxt2 - nxt1);
2671                                 else if (nxt2 - nxt1 < U16_MAX)
2672                                     NEXT_OFF(nxt1) = nxt2 - nxt1;
2673                                 else
2674                                     OP(nxt) = NOTHING;  /* Cannot beautify */
2675                             }
2676                             nxt1 = nnxt;
2677                         }
2678 #endif
2679                         /* Optimize again: */
2680                         study_chunk(pRExC_state, &nxt1, &deltanext, nxt,
2681                                     NULL, 0,depth+1);
2682                     }
2683                     else
2684                         oscan->flags = 0;
2685                 }
2686                 else if ((OP(oscan) == CURLYX)
2687                          && (flags & SCF_WHILEM_VISITED_POS)
2688                          /* See the comment on a similar expression above.
2689                             However, this time it not a subexpression
2690                             we care about, but the expression itself. */
2691                          && (maxcount == REG_INFTY)
2692                          && data && ++data->whilem_c < 16) {
2693                     /* This stays as CURLYX, we can put the count/of pair. */
2694                     /* Find WHILEM (as in regexec.c) */
2695                     regnode *nxt = oscan + NEXT_OFF(oscan);
2696
2697                     if (OP(PREVOPER(nxt)) == NOTHING) /* LONGJMP */
2698                         nxt += ARG(nxt);
2699                     PREVOPER(nxt)->flags = (U8)(data->whilem_c
2700                         | (RExC_whilem_seen << 4)); /* On WHILEM */
2701                 }
2702                 if (data && fl & (SF_HAS_PAR|SF_IN_PAR))
2703                     pars++;
2704                 if (flags & SCF_DO_SUBSTR) {
2705                     SV *last_str = NULL;
2706                     int counted = mincount != 0;
2707
2708                     if (data->last_end > 0 && mincount != 0) { /* Ends with a string. */
2709 #if defined(SPARC64_GCC_WORKAROUND)
2710                         I32 b = 0;
2711                         STRLEN l = 0;
2712                         const char *s = NULL;
2713                         I32 old = 0;
2714
2715                         if (pos_before >= data->last_start_min)
2716                             b = pos_before;
2717                         else
2718                             b = data->last_start_min;
2719
2720                         l = 0;
2721                         s = SvPV_const(data->last_found, l);
2722                         old = b - data->last_start_min;
2723
2724 #else
2725                         I32 b = pos_before >= data->last_start_min
2726                             ? pos_before : data->last_start_min;
2727                         STRLEN l;
2728                         const char * const s = SvPV_const(data->last_found, l);
2729                         I32 old = b - data->last_start_min;
2730 #endif
2731
2732                         if (UTF)
2733                             old = utf8_hop((U8*)s, old) - (U8*)s;
2734                         
2735                         l -= old;
2736                         /* Get the added string: */
2737                         last_str = newSVpvn(s  + old, l);
2738                         if (UTF)
2739                             SvUTF8_on(last_str);
2740                         if (deltanext == 0 && pos_before == b) {
2741                             /* What was added is a constant string */
2742                             if (mincount > 1) {
2743                                 SvGROW(last_str, (mincount * l) + 1);
2744                                 repeatcpy(SvPVX(last_str) + l,
2745                                           SvPVX_const(last_str), l, mincount - 1);
2746                                 SvCUR_set(last_str, SvCUR(last_str) * mincount);
2747                                 /* Add additional parts. */
2748                                 SvCUR_set(data->last_found,
2749                                           SvCUR(data->last_found) - l);
2750                                 sv_catsv(data->last_found, last_str);
2751                                 {
2752                                     SV * sv = data->last_found;
2753                                     MAGIC *mg =
2754                                         SvUTF8(sv) && SvMAGICAL(sv) ?
2755                                         mg_find(sv, PERL_MAGIC_utf8) : NULL;
2756                                     if (mg && mg->mg_len >= 0)
2757                                         mg->mg_len += CHR_SVLEN(last_str);
2758                                 }
2759                                 data->last_end += l * (mincount - 1);
2760                             }
2761                         } else {
2762                             /* start offset must point into the last copy */
2763                             data->last_start_min += minnext * (mincount - 1);
2764                             data->last_start_max += is_inf ? I32_MAX
2765                                 : (maxcount - 1) * (minnext + data->pos_delta);
2766                         }
2767                     }
2768                     /* It is counted once already... */
2769                     data->pos_min += minnext * (mincount - counted);
2770                     data->pos_delta += - counted * deltanext +
2771                         (minnext + deltanext) * maxcount - minnext * mincount;
2772                     if (mincount != maxcount) {
2773                          /* Cannot extend fixed substrings found inside
2774                             the group.  */
2775                         scan_commit(pRExC_state,data);
2776                         if (mincount && last_str) {
2777                             SV * const sv = data->last_found;
2778                             MAGIC * const mg = SvUTF8(sv) && SvMAGICAL(sv) ?
2779                                 mg_find(sv, PERL_MAGIC_utf8) : NULL;
2780
2781                             if (mg)
2782                                 mg->mg_len = -1;
2783                             sv_setsv(sv, last_str);
2784                             data->last_end = data->pos_min;
2785                             data->last_start_min =
2786                                 data->pos_min - CHR_SVLEN(last_str);
2787                             data->last_start_max = is_inf
2788                                 ? I32_MAX
2789                                 : data->pos_min + data->pos_delta
2790                                 - CHR_SVLEN(last_str);
2791                         }
2792                         data->longest = &(data->longest_float);
2793                     }
2794                     SvREFCNT_dec(last_str);
2795                 }
2796                 if (data && (fl & SF_HAS_EVAL))
2797                     data->flags |= SF_HAS_EVAL;
2798               optimize_curly_tail:
2799                 if (OP(oscan) != CURLYX) {
2800                     while (PL_regkind[OP(next = regnext(oscan))] == NOTHING
2801                            && NEXT_OFF(next))
2802                         NEXT_OFF(oscan) += NEXT_OFF(next);
2803                 }
2804                 continue;
2805             default:                    /* REF and CLUMP only? */
2806                 if (flags & SCF_DO_SUBSTR) {
2807                     scan_commit(pRExC_state,data);      /* Cannot expect anything... */
2808                     data->longest = &(data->longest_float);
2809                 }
2810                 is_inf = is_inf_internal = 1;
2811                 if (flags & SCF_DO_STCLASS_OR)
2812                     cl_anything(pRExC_state, data->start_class);
2813                 flags &= ~SCF_DO_STCLASS;
2814                 break;
2815             }
2816         }
2817         else if (strchr((const char*)PL_simple,OP(scan))) {
2818             int value = 0;
2819
2820             if (flags & SCF_DO_SUBSTR) {
2821                 scan_commit(pRExC_state,data);
2822                 data->pos_min++;
2823             }
2824             min++;
2825             if (flags & SCF_DO_STCLASS) {
2826                 data->start_class->flags &= ~ANYOF_EOS; /* No match on empty */
2827
2828                 /* Some of the logic below assumes that switching
2829                    locale on will only add false positives. */
2830                 switch (PL_regkind[OP(scan)]) {
2831                 case SANY:
2832                 default:
2833                   do_default:
2834                     /* Perl_croak(aTHX_ "panic: unexpected simple REx opcode %d", OP(scan)); */
2835                     if (flags & SCF_DO_STCLASS_OR) /* Allow everything */
2836                         cl_anything(pRExC_state, data->start_class);
2837                     break;
2838                 case REG_ANY:
2839                     if (OP(scan) == SANY)
2840                         goto do_default;
2841                     if (flags & SCF_DO_STCLASS_OR) { /* Everything but \n */
2842                         value = (ANYOF_BITMAP_TEST(data->start_class,'\n')
2843                                  || (data->start_class->flags & ANYOF_CLASS));
2844                         cl_anything(pRExC_state, data->start_class);
2845                     }
2846                     if (flags & SCF_DO_STCLASS_AND || !value)
2847                         ANYOF_BITMAP_CLEAR(data->start_class,'\n');
2848                     break;
2849                 case ANYOF:
2850                     if (flags & SCF_DO_STCLASS_AND)
2851                         cl_and(data->start_class,
2852                                (struct regnode_charclass_class*)scan);
2853                     else
2854                         cl_or(pRExC_state, data->start_class,
2855                               (struct regnode_charclass_class*)scan);
2856                     break;
2857                 case ALNUM:
2858                     if (flags & SCF_DO_STCLASS_AND) {
2859                         if (!(data->start_class->flags & ANYOF_LOCALE)) {
2860                             ANYOF_CLASS_CLEAR(data->start_class,ANYOF_NALNUM);
2861                             for (value = 0; value < 256; value++)
2862                                 if (!isALNUM(value))
2863                                     ANYOF_BITMAP_CLEAR(data->start_class, value);
2864                         }
2865                     }
2866                     else {
2867                         if (data->start_class->flags & ANYOF_LOCALE)
2868                             ANYOF_CLASS_SET(data->start_class,ANYOF_ALNUM);
2869                         else {
2870                             for (value = 0; value < 256; value++)
2871                                 if (isALNUM(value))
2872                                     ANYOF_BITMAP_SET(data->start_class, value);                 
2873                         }
2874                     }
2875                     break;
2876                 case ALNUML:
2877                     if (flags & SCF_DO_STCLASS_AND) {
2878                         if (data->start_class->flags & ANYOF_LOCALE)
2879                             ANYOF_CLASS_CLEAR(data->start_class,ANYOF_NALNUM);
2880                     }
2881                     else {
2882                         ANYOF_CLASS_SET(data->start_class,ANYOF_ALNUM);
2883                         data->start_class->flags |= ANYOF_LOCALE;
2884                     }
2885                     break;
2886                 case NALNUM:
2887                     if (flags & SCF_DO_STCLASS_AND) {
2888                         if (!(data->start_class->flags & ANYOF_LOCALE)) {
2889                             ANYOF_CLASS_CLEAR(data->start_class,ANYOF_ALNUM);
2890                             for (value = 0; value < 256; value++)
2891                                 if (isALNUM(value))
2892                                     ANYOF_BITMAP_CLEAR(data->start_class, value);
2893                         }
2894                     }
2895                     else {
2896                         if (data->start_class->flags & ANYOF_LOCALE)
2897                             ANYOF_CLASS_SET(data->start_class,ANYOF_NALNUM);
2898                         else {
2899                             for (value = 0; value < 256; value++)
2900                                 if (!isALNUM(value))
2901                                     ANYOF_BITMAP_SET(data->start_class, value);                 
2902                         }
2903                     }
2904                     break;
2905                 case NALNUML:
2906                     if (flags & SCF_DO_STCLASS_AND) {
2907                         if (data->start_class->flags & ANYOF_LOCALE)
2908                             ANYOF_CLASS_CLEAR(data->start_class,ANYOF_ALNUM);
2909                     }
2910                     else {
2911                         data->start_class->flags |= ANYOF_LOCALE;
2912                         ANYOF_CLASS_SET(data->start_class,ANYOF_NALNUM);
2913                     }
2914                     break;
2915                 case SPACE:
2916                     if (flags & SCF_DO_STCLASS_AND) {
2917                         if (!(data->start_class->flags & ANYOF_LOCALE)) {
2918                             ANYOF_CLASS_CLEAR(data->start_class,ANYOF_NSPACE);
2919                             for (value = 0; value < 256; value++)
2920                                 if (!isSPACE(value))
2921                                     ANYOF_BITMAP_CLEAR(data->start_class, value);
2922                         }
2923                     }
2924                     else {
2925                         if (data->start_class->flags & ANYOF_LOCALE)
2926                             ANYOF_CLASS_SET(data->start_class,ANYOF_SPACE);
2927                         else {
2928                             for (value = 0; value < 256; value++)
2929                                 if (isSPACE(value))
2930                                     ANYOF_BITMAP_SET(data->start_class, value);                 
2931                         }
2932                     }
2933                     break;
2934                 case SPACEL:
2935                     if (flags & SCF_DO_STCLASS_AND) {
2936                         if (data->start_class->flags & ANYOF_LOCALE)
2937                             ANYOF_CLASS_CLEAR(data->start_class,ANYOF_NSPACE);
2938                     }
2939                     else {
2940                         data->start_class->flags |= ANYOF_LOCALE;
2941                         ANYOF_CLASS_SET(data->start_class,ANYOF_SPACE);
2942                     }
2943                     break;
2944                 case NSPACE:
2945                     if (flags & SCF_DO_STCLASS_AND) {
2946                         if (!(data->start_class->flags & ANYOF_LOCALE)) {
2947                             ANYOF_CLASS_CLEAR(data->start_class,ANYOF_SPACE);
2948                             for (value = 0; value < 256; value++)
2949                                 if (isSPACE(value))
2950                                     ANYOF_BITMAP_CLEAR(data->start_class, value);
2951                         }
2952                     }
2953                     else {
2954                         if (data->start_class->flags & ANYOF_LOCALE)
2955                             ANYOF_CLASS_SET(data->start_class,ANYOF_NSPACE);
2956                         else {
2957                             for (value = 0; value < 256; value++)
2958                                 if (!isSPACE(value))
2959                                     ANYOF_BITMAP_SET(data->start_class, value);                 
2960                         }
2961                     }
2962                     break;
2963                 case NSPACEL:
2964                     if (flags & SCF_DO_STCLASS_AND) {
2965                         if (data->start_class->flags & ANYOF_LOCALE) {
2966                             ANYOF_CLASS_CLEAR(data->start_class,ANYOF_SPACE);
2967                             for (value = 0; value < 256; value++)
2968                                 if (!isSPACE(value))
2969                                     ANYOF_BITMAP_CLEAR(data->start_class, value);
2970                         }
2971                     }
2972                     else {
2973                         data->start_class->flags |= ANYOF_LOCALE;
2974                         ANYOF_CLASS_SET(data->start_class,ANYOF_NSPACE);
2975                     }
2976                     break;
2977                 case DIGIT:
2978                     if (flags & SCF_DO_STCLASS_AND) {
2979                         ANYOF_CLASS_CLEAR(data->start_class,ANYOF_NDIGIT);
2980                         for (value = 0; value < 256; value++)
2981                             if (!isDIGIT(value))
2982                                 ANYOF_BITMAP_CLEAR(data->start_class, value);
2983                     }
2984                     else {
2985                         if (data->start_class->flags & ANYOF_LOCALE)
2986                             ANYOF_CLASS_SET(data->start_class,ANYOF_DIGIT);
2987                         else {
2988                             for (value = 0; value < 256; value++)
2989                                 if (isDIGIT(value))
2990                                     ANYOF_BITMAP_SET(data->start_class, value);                 
2991                         }
2992                     }
2993                     break;
2994                 case NDIGIT:
2995                     if (flags & SCF_DO_STCLASS_AND) {
2996                         ANYOF_CLASS_CLEAR(data->start_class,ANYOF_DIGIT);
2997                         for (value = 0; value < 256; value++)
2998                             if (isDIGIT(value))
2999                                 ANYOF_BITMAP_CLEAR(data->start_class, value);
3000                     }
3001                     else {
3002                         if (data->start_class->flags & ANYOF_LOCALE)
3003                             ANYOF_CLASS_SET(data->start_class,ANYOF_NDIGIT);
3004                         else {
3005                             for (value = 0; value < 256; value++)
3006                                 if (!isDIGIT(value))
3007                                     ANYOF_BITMAP_SET(data->start_class, value);                 
3008                         }
3009                     }
3010                     break;
3011                 }
3012                 if (flags & SCF_DO_STCLASS_OR)
3013                     cl_and(data->start_class, &and_with);
3014                 flags &= ~SCF_DO_STCLASS;
3015             }
3016         }
3017         else if (PL_regkind[OP(scan)] == EOL && flags & SCF_DO_SUBSTR) {
3018             data->flags |= (OP(scan) == MEOL
3019                             ? SF_BEFORE_MEOL
3020                             : SF_BEFORE_SEOL);
3021         }
3022         else if (  PL_regkind[OP(scan)] == BRANCHJ
3023                  /* Lookbehind, or need to calculate parens/evals/stclass: */
3024                    && (scan->flags || data || (flags & SCF_DO_STCLASS))
3025                    && (OP(scan) == IFMATCH || OP(scan) == UNLESSM)) {
3026             /* Lookahead/lookbehind */
3027             I32 deltanext, minnext, fake = 0;
3028             regnode *nscan;
3029             struct regnode_charclass_class intrnl;
3030             int f = 0;
3031
3032             data_fake.flags = 0;
3033             if (data) {         
3034                 data_fake.whilem_c = data->whilem_c;
3035                 data_fake.last_closep = data->last_closep;
3036             }
3037             else
3038                 data_fake.last_closep = &fake;
3039             if ( flags & SCF_DO_STCLASS && !scan->flags
3040                  && OP(scan) == IFMATCH ) { /* Lookahead */
3041                 cl_init(pRExC_state, &intrnl);
3042                 data_fake.start_class = &intrnl;
3043                 f |= SCF_DO_STCLASS_AND;
3044             }
3045             if (flags & SCF_WHILEM_VISITED_POS)
3046                 f |= SCF_WHILEM_VISITED_POS;
3047             next = regnext(scan);
3048             nscan = NEXTOPER(NEXTOPER(scan));
3049             minnext = study_chunk(pRExC_state, &nscan, &deltanext, last, &data_fake, f,depth+1);
3050             if (scan->flags) {
3051                 if (deltanext) {
3052                     vFAIL("Variable length lookbehind not implemented");
3053                 }
3054                 else if (minnext > U8_MAX) {
3055                     vFAIL2("Lookbehind longer than %"UVuf" not implemented", (UV)U8_MAX);
3056                 }
3057                 scan->flags = (U8)minnext;
3058             }
3059             if (data) {
3060                 if (data_fake.flags & (SF_HAS_PAR|SF_IN_PAR))
3061                     pars++;
3062                 if (data_fake.flags & SF_HAS_EVAL)
3063                     data->flags |= SF_HAS_EVAL;
3064                 data->whilem_c = data_fake.whilem_c;
3065             }
3066             if (f & SCF_DO_STCLASS_AND) {
3067                 const int was = (data->start_class->flags & ANYOF_EOS);
3068
3069                 cl_and(data->start_class, &intrnl);
3070                 if (was)
3071                     data->start_class->flags |= ANYOF_EOS;
3072             }
3073         }
3074         else if (OP(scan) == OPEN) {
3075             pars++;
3076         }
3077         else if (OP(scan) == CLOSE) {
3078             if ((I32)ARG(scan) == is_par) {
3079                 next = regnext(scan);
3080
3081                 if ( next && (OP(next) != WHILEM) && next < last)
3082                     is_par = 0;         /* Disable optimization */
3083             }
3084             if (data)
3085                 *(data->last_closep) = ARG(scan);
3086         }
3087         else if (OP(scan) == EVAL) {
3088                 if (data)
3089                     data->flags |= SF_HAS_EVAL;
3090         }
3091         else if (OP(scan) == LOGICAL && scan->flags == 2) { /* Embedded follows */
3092                 if (flags & SCF_DO_SUBSTR) {
3093                     scan_commit(pRExC_state,data);
3094                     data->longest = &(data->longest_float);
3095                 }
3096                 is_inf = is_inf_internal = 1;
3097                 if (flags & SCF_DO_STCLASS_OR) /* Allow everything */
3098                     cl_anything(pRExC_state, data->start_class);
3099                 flags &= ~SCF_DO_STCLASS;
3100         }
3101         /* Else: zero-length, ignore. */
3102         scan = regnext(scan);
3103     }
3104
3105   finish:
3106     *scanp = scan;
3107     *deltap = is_inf_internal ? I32_MAX : delta;
3108     if (flags & SCF_DO_SUBSTR && is_inf)
3109         data->pos_delta = I32_MAX - data->pos_min;
3110     if (is_par > U8_MAX)
3111         is_par = 0;
3112     if (is_par && pars==1 && data) {
3113         data->flags |= SF_IN_PAR;
3114         data->flags &= ~SF_HAS_PAR;
3115     }
3116     else if (pars && data) {
3117         data->flags |= SF_HAS_PAR;
3118         data->flags &= ~SF_IN_PAR;
3119     }
3120     if (flags & SCF_DO_STCLASS_OR)
3121         cl_and(data->start_class, &and_with);
3122     if (flags & SCF_EXACT_TRIE) 
3123         data->flags |=  SCF_EXACT_TRIE;
3124     return min;
3125 }
3126
3127 STATIC I32
3128 S_add_data(RExC_state_t *pRExC_state, I32 n, const char *s)
3129 {
3130     if (RExC_rx->data) {
3131         Renewc(RExC_rx->data,
3132                sizeof(*RExC_rx->data) + sizeof(void*) * (RExC_rx->data->count + n - 1),
3133                char, struct reg_data);
3134         Renew(RExC_rx->data->what, RExC_rx->data->count + n, U8);
3135         RExC_rx->data->count += n;
3136     }
3137     else {
3138         Newxc(RExC_rx->data, sizeof(*RExC_rx->data) + sizeof(void*) * (n - 1),
3139              char, struct reg_data);
3140         Newx(RExC_rx->data->what, n, U8);
3141         RExC_rx->data->count = n;
3142     }
3143     Copy(s, RExC_rx->data->what + RExC_rx->data->count - n, n, U8);
3144     return RExC_rx->data->count - n;
3145 }
3146
3147 #ifndef PERL_IN_XSUB_RE
3148 void
3149 Perl_reginitcolors(pTHX)
3150 {
3151     dVAR;
3152     const char * const s = PerlEnv_getenv("PERL_RE_COLORS");
3153     if (s) {
3154         char *t = savepv(s);
3155         int i = 0;
3156         PL_colors[0] = t;
3157         while (++i < 6) {
3158             t = strchr(t, '\t');
3159             if (t) {
3160                 *t = '\0';
3161                 PL_colors[i] = ++t;
3162             }
3163             else
3164                 PL_colors[i] = t = (char *)"";
3165         }
3166     } else {
3167         int i = 0;
3168         while (i < 6)
3169             PL_colors[i++] = (char *)"";
3170     }
3171     PL_colorset = 1;
3172 }
3173 #endif
3174
3175
3176 /*
3177  - pregcomp - compile a regular expression into internal code
3178  *
3179  * We can't allocate space until we know how big the compiled form will be,
3180  * but we can't compile it (and thus know how big it is) until we've got a
3181  * place to put the code.  So we cheat:  we compile it twice, once with code
3182  * generation turned off and size counting turned on, and once "for real".
3183  * This also means that we don't allocate space until we are sure that the
3184  * thing really will compile successfully, and we never have to move the
3185  * code and thus invalidate pointers into it.  (Note that it has to be in
3186  * one piece because free() must be able to free it all.) [NB: not true in perl]
3187  *
3188  * Beware that the optimization-preparation code in here knows about some
3189  * of the structure of the compiled regexp.  [I'll say.]
3190  */
3191 regexp *
3192 Perl_pregcomp(pTHX_ char *exp, char *xend, PMOP *pm)
3193 {
3194     dVAR;
3195     register regexp *r;
3196     regnode *scan;
3197     regnode *first;
3198     I32 flags;
3199     I32 minlen = 0;
3200     I32 sawplus = 0;
3201     I32 sawopen = 0;
3202     scan_data_t data;
3203     RExC_state_t RExC_state;
3204     RExC_state_t * const pRExC_state = &RExC_state;
3205 #ifdef TRIE_STUDY_OPT    
3206     int restudied= 0;
3207     RExC_state_t copyRExC_state;
3208 #endif    
3209
3210     GET_RE_DEBUG_FLAGS_DECL;
3211
3212     if (exp == NULL)
3213         FAIL("NULL regexp argument");
3214
3215     RExC_utf8 = pm->op_pmdynflags & PMdf_CMP_UTF8;
3216
3217     RExC_precomp = exp;
3218     DEBUG_r(if (!PL_colorset) reginitcolors());
3219     DEBUG_COMPILE_r({
3220          PerlIO_printf(Perl_debug_log, "%sCompiling REx%s \"%s%*s%s\"\n",
3221                        PL_colors[4],PL_colors[5],PL_colors[0],
3222                        (int)(xend - exp), RExC_precomp, PL_colors[1]);
3223     });
3224     RExC_flags = pm->op_pmflags;
3225     RExC_sawback = 0;
3226
3227     RExC_seen = 0;
3228     RExC_seen_zerolen = *exp == '^' ? -1 : 0;
3229     RExC_seen_evals = 0;
3230     RExC_extralen = 0;
3231
3232     /* First pass: determine size, legality. */
3233     RExC_parse = exp;
3234     RExC_start = exp;
3235     RExC_end = xend;
3236     RExC_naughty = 0;
3237     RExC_npar = 1;
3238     RExC_size = 0L;
3239     RExC_emit = &PL_regdummy;
3240     RExC_whilem_seen = 0;
3241 #if 0 /* REGC() is (currently) a NOP at the first pass.
3242        * Clever compilers notice this and complain. --jhi */
3243     REGC((U8)REG_MAGIC, (char*)RExC_emit);
3244 #endif
3245     DEBUG_PARSE_r(PerlIO_printf(Perl_debug_log, "Starting first pass (sizing)\n"));
3246     if (reg(pRExC_state, 0, &flags,1) == NULL) {
3247         RExC_precomp = NULL;
3248         return(NULL);
3249     }
3250     DEBUG_PARSE_r(PerlIO_printf(Perl_debug_log, "Required "));
3251     DEBUG_COMPILE_r(PerlIO_printf(Perl_debug_log, "size %"IVdf" nodes ", (IV)RExC_size));
3252     DEBUG_PARSE_r(PerlIO_printf(Perl_debug_log, "\nStarting second pass (creation)\n"));
3253     DEBUG_PARSE_r({
3254         RExC_lastnum=0; 
3255         RExC_lastparse=NULL; 
3256     });
3257
3258     
3259     /* Small enough for pointer-storage convention?
3260        If extralen==0, this means that we will not need long jumps. */
3261     if (RExC_size >= 0x10000L && RExC_extralen)
3262         RExC_size += RExC_extralen;
3263     else
3264         RExC_extralen = 0;
3265     if (RExC_whilem_seen > 15)
3266         RExC_whilem_seen = 15;
3267
3268     /* Allocate space and initialize. */
3269     Newxc(r, sizeof(regexp) + (unsigned)RExC_size * sizeof(regnode),
3270          char, regexp);
3271     if (r == NULL)
3272         FAIL("Regexp out of space");
3273
3274 #ifdef DEBUGGING
3275     /* avoid reading uninitialized memory in DEBUGGING code in study_chunk() */
3276     Zero(r, sizeof(regexp) + (unsigned)RExC_size * sizeof(regnode), char);
3277 #endif
3278     r->refcnt = 1;
3279     r->prelen = xend - exp;
3280     r->precomp = savepvn(RExC_precomp, r->prelen);
3281     r->subbeg = NULL;
3282 #ifdef PERL_OLD_COPY_ON_WRITE
3283     r->saved_copy = NULL;
3284 #endif
3285     r->reganch = pm->op_pmflags & PMf_COMPILETIME;
3286     r->nparens = RExC_npar - 1; /* set early to validate backrefs */
3287     r->lastparen = 0;                   /* mg.c reads this.  */
3288
3289     r->substrs = 0;                     /* Useful during FAIL. */
3290     r->startp = 0;                      /* Useful during FAIL. */
3291     r->endp = 0;                        /* Useful during FAIL. */
3292
3293     Newxz(r->offsets, 2*RExC_size+1, U32); /* MJD 20001228 */
3294     if (r->offsets) {
3295         r->offsets[0] = RExC_size;
3296     }
3297     DEBUG_OFFSETS_r(PerlIO_printf(Perl_debug_log,
3298                           "%s %"UVuf" bytes for offset annotations.\n",
3299                           r->offsets ? "Got" : "Couldn't get",
3300                           (UV)((2*RExC_size+1) * sizeof(U32))));
3301
3302     RExC_rx = r;
3303
3304     /* Second pass: emit code. */
3305     RExC_flags = pm->op_pmflags;        /* don't let top level (?i) bleed */
3306     RExC_parse = exp;
3307     RExC_end = xend;
3308     RExC_naughty = 0;
3309     RExC_npar = 1;
3310     RExC_emit_start = r->program;
3311     RExC_emit = r->program;
3312     /* Store the count of eval-groups for security checks: */
3313     RExC_emit->next_off = (U16)((RExC_seen_evals > U16_MAX) ? U16_MAX : RExC_seen_evals);
3314     REGC((U8)REG_MAGIC, (char*) RExC_emit++);
3315     r->data = 0;
3316     if (reg(pRExC_state, 0, &flags,1) == NULL)
3317         return(NULL);
3318     /* XXXX To minimize changes to RE engine we always allocate
3319        3-units-long substrs field. */
3320     Newx(r->substrs, 1, struct reg_substr_data);
3321
3322 reStudy:
3323     Zero(r->substrs, 1, struct reg_substr_data);
3324     StructCopy(&zero_scan_data, &data, scan_data_t);
3325
3326 #ifdef TRIE_STUDY_OPT
3327     if ( restudied ) {
3328         DEBUG_OPTIMISE_r(PerlIO_printf(Perl_debug_log,"Restudying\n"));
3329         RExC_state=copyRExC_state;
3330         if (data.longest_fixed)
3331             SvREFCNT_dec(data.longest_fixed);
3332         if (data.longest_float)
3333             SvREFCNT_dec(data.longest_float);
3334         if (data.last_found)
3335             SvREFCNT_dec(data.last_found);
3336     } else {
3337         copyRExC_state=RExC_state;
3338     }
3339 #endif    
3340     /* Dig out information for optimizations. */
3341     r->reganch = pm->op_pmflags & PMf_COMPILETIME; /* Again? */
3342     pm->op_pmflags = RExC_flags;
3343     if (UTF)
3344         r->reganch |= ROPT_UTF8;        /* Unicode in it? */
3345     r->regstclass = NULL;
3346     if (RExC_naughty >= 10)     /* Probably an expensive pattern. */
3347         r->reganch |= ROPT_NAUGHTY;
3348     scan = r->program + 1;              /* First BRANCH. */
3349
3350     /* XXXX Should not we check for something else?  Usually it is OPEN1... */
3351     if (OP(scan) != BRANCH) {   /* Only one top-level choice. */
3352         I32 fake;
3353         STRLEN longest_float_length, longest_fixed_length;
3354         struct regnode_charclass_class ch_class; /* pointed to by data */
3355         int stclass_flag;
3356         I32 last_close = 0; /* pointed to by data */
3357
3358         first = scan;
3359         /* Skip introductions and multiplicators >= 1. */
3360         while ((OP(first) == OPEN && (sawopen = 1)) ||
3361                /* An OR of *one* alternative - should not happen now. */
3362             (OP(first) == BRANCH && OP(regnext(first)) != BRANCH) ||
3363             /* for now we can't handle lookbehind IFMATCH*/
3364             (OP(first) == IFMATCH && !first->flags) || 
3365             (OP(first) == PLUS) ||
3366             (OP(first) == MINMOD) ||
3367                /* An {n,m} with n>0 */
3368             (PL_regkind[OP(first)] == CURLY && ARG1(first) > 0) ) 
3369         {
3370                 DEBUG_PEEP("first:",first,0);
3371                 if (OP(first) == PLUS)
3372                     sawplus = 1;
3373                 else
3374                     first += regarglen[OP(first)];
3375                 if (OP(first) == IFMATCH) {
3376                     first = NEXTOPER(first);
3377                     first += EXTRA_STEP_2ARGS;
3378                 } else  /*xxx possible optimisation for /(?=)/*/
3379                     first = NEXTOPER(first);
3380         }
3381
3382         /* Starting-point info. */
3383       again:
3384         /* Ignore EXACT as we deal with it later. */
3385         if (PL_regkind[OP(first)] == EXACT) {
3386             if (OP(first) == EXACT)
3387                 NOOP;   /* Empty, get anchored substr later. */
3388             else if ((OP(first) == EXACTF || OP(first) == EXACTFL))
3389                 r->regstclass = first;
3390         }
3391 #ifdef TRIE_STCLASS     
3392         else if (OP(first) == TRIE &&
3393                 ((reg_trie_data *)r->data->data[ ARG(first) ])->minlen>0) 
3394         {
3395             /* this can happen only on restudy */
3396             struct regnode_1 *trie_op;
3397             Newxz(trie_op,1,struct regnode_1);
3398             StructCopy(first,trie_op,struct regnode_1);
3399             make_trie_failtable(pRExC_state, (regnode *)first, (regnode *)trie_op, 0);
3400             r->regstclass = (regnode *)trie_op;
3401         }
3402 #endif  
3403         else if (strchr((const char*)PL_simple,OP(first)))
3404             r->regstclass = first;
3405         else if (PL_regkind[OP(first)] == BOUND ||
3406                  PL_regkind[OP(first)] == NBOUND)
3407             r->regstclass = first;
3408         else if (PL_regkind[OP(first)] == BOL) {
3409             r->reganch |= (OP(first) == MBOL
3410                            ? ROPT_ANCH_MBOL
3411                            : (OP(first) == SBOL
3412                               ? ROPT_ANCH_SBOL
3413                               : ROPT_ANCH_BOL));
3414             first = NEXTOPER(first);
3415             goto again;
3416         }
3417         else if (OP(first) == GPOS) {
3418             r->reganch |= ROPT_ANCH_GPOS;
3419             first = NEXTOPER(first);
3420             goto again;
3421         }
3422         else if (!sawopen && (OP(first) == STAR &&
3423             PL_regkind[OP(NEXTOPER(first))] == REG_ANY) &&
3424             !(r->reganch & ROPT_ANCH) )
3425         {
3426             /* turn .* into ^.* with an implied $*=1 */
3427             const int type =
3428                 (OP(NEXTOPER(first)) == REG_ANY)
3429                     ? ROPT_ANCH_MBOL
3430                     : ROPT_ANCH_SBOL;
3431             r->reganch |= type | ROPT_IMPLICIT;
3432             first = NEXTOPER(first);
3433             goto again;
3434         }
3435         if (sawplus && (!sawopen || !RExC_sawback)
3436             && !(RExC_seen & REG_SEEN_EVAL)) /* May examine pos and $& */
3437             /* x+ must match at the 1st pos of run of x's */
3438             r->reganch |= ROPT_SKIP;
3439
3440         /* Scan is after the zeroth branch, first is atomic matcher. */
3441 #ifdef TRIE_STUDY_OPT
3442         DEBUG_COMPILE_r(
3443             if (!restudied)
3444                 PerlIO_printf(Perl_debug_log, "first at %"IVdf"\n",
3445                               (IV)(first - scan + 1))
3446         );
3447 #else
3448         DEBUG_COMPILE_r(
3449             PerlIO_printf(Perl_debug_log, "first at %"IVdf"\n",
3450                 (IV)(first - scan + 1))
3451         );
3452 #endif
3453
3454
3455         /*
3456         * If there's something expensive in the r.e., find the
3457         * longest literal string that must appear and make it the
3458         * regmust.  Resolve ties in favor of later strings, since
3459         * the regstart check works with the beginning of the r.e.
3460         * and avoiding duplication strengthens checking.  Not a
3461         * strong reason, but sufficient in the absence of others.
3462         * [Now we resolve ties in favor of the earlier string if
3463         * it happens that c_offset_min has been invalidated, since the
3464         * earlier string may buy us something the later one won't.]
3465         */
3466         minlen = 0;
3467
3468         data.longest_fixed = newSVpvs("");
3469         data.longest_float = newSVpvs("");
3470         data.last_found = newSVpvs("");
3471         data.longest = &(data.longest_fixed);
3472         first = scan;
3473         if (!r->regstclass) {
3474             cl_init(pRExC_state, &ch_class);
3475             data.start_class = &ch_class;
3476             stclass_flag = SCF_DO_STCLASS_AND;
3477         } else                          /* XXXX Check for BOUND? */
3478             stclass_flag = 0;
3479         data.last_closep = &last_close;
3480
3481         minlen = study_chunk(pRExC_state, &first, &fake, scan + RExC_size, /* Up to end */
3482                              &data, SCF_DO_SUBSTR | SCF_WHILEM_VISITED_POS | stclass_flag,0);
3483
3484 #ifdef TRIE_STUDY_OPT           
3485         if ( (data.flags & SCF_EXACT_TRIE) && ! restudied++ ) {
3486             goto reStudy;
3487         }
3488 #endif  
3489         
3490         if ( RExC_npar == 1 && data.longest == &(data.longest_fixed)
3491              && data.last_start_min == 0 && data.last_end > 0
3492              && !RExC_seen_zerolen
3493              && (!(RExC_seen & REG_SEEN_GPOS) || (r->reganch & ROPT_ANCH_GPOS)))
3494             r->reganch |= ROPT_CHECK_ALL;
3495         scan_commit(pRExC_state, &data);
3496         SvREFCNT_dec(data.last_found);
3497
3498         longest_float_length = CHR_SVLEN(data.longest_float);
3499         if (longest_float_length
3500             || (data.flags & SF_FL_BEFORE_EOL
3501                 && (!(data.flags & SF_FL_BEFORE_MEOL)
3502                     || (RExC_flags & PMf_MULTILINE)))) {
3503             int t;
3504
3505             if (SvCUR(data.longest_fixed)                       /* ok to leave SvCUR */
3506                 && data.offset_fixed == data.offset_float_min
3507                 && SvCUR(data.longest_fixed) == SvCUR(data.longest_float))
3508                     goto remove_float;          /* As in (a)+. */
3509
3510             if (SvUTF8(data.longest_float)) {
3511                 r->float_utf8 = data.longest_float;
3512                 r->float_substr = NULL;
3513             } else {
3514                 r->float_substr = data.longest_float;
3515                 r->float_utf8 = NULL;
3516             }
3517             r->float_min_offset = data.offset_float_min;
3518             r->float_max_offset = data.offset_float_max;
3519             t = (data.flags & SF_FL_BEFORE_EOL /* Can't have SEOL and MULTI */
3520                        && (!(data.flags & SF_FL_BEFORE_MEOL)
3521                            || (RExC_flags & PMf_MULTILINE)));
3522             fbm_compile(data.longest_float, t ? FBMcf_TAIL : 0);
3523         }
3524         else {
3525           remove_float:
3526             r->float_substr = r->float_utf8 = NULL;
3527             SvREFCNT_dec(data.longest_float);
3528             longest_float_length = 0;
3529         }
3530
3531         longest_fixed_length = CHR_SVLEN(data.longest_fixed);
3532         if (longest_fixed_length
3533             || (data.flags & SF_FIX_BEFORE_EOL /* Cannot have SEOL and MULTI */
3534                 && (!(data.flags & SF_FIX_BEFORE_MEOL)
3535                     || (RExC_flags & PMf_MULTILINE)))) {
3536             int t;
3537
3538             if (SvUTF8(data.longest_fixed)) {
3539                 r->anchored_utf8 = data.longest_fixed;
3540                 r->anchored_substr = NULL;
3541             } else {
3542                 r->anchored_substr = data.longest_fixed;
3543                 r->anchored_utf8 = NULL;
3544             }
3545             r->anchored_offset = data.offset_fixed;
3546             t = (data.flags & SF_FIX_BEFORE_EOL /* Can't have SEOL and MULTI */
3547                  && (!(data.flags & SF_FIX_BEFORE_MEOL)
3548                      || (RExC_flags & PMf_MULTILINE)));
3549             fbm_compile(data.longest_fixed, t ? FBMcf_TAIL : 0);
3550         }
3551         else {
3552             r->anchored_substr = r->anchored_utf8 = NULL;
3553             SvREFCNT_dec(data.longest_fixed);
3554             longest_fixed_length = 0;
3555         }
3556         if (r->regstclass
3557             && (OP(r->regstclass) == REG_ANY || OP(r->regstclass) == SANY))
3558             r->regstclass = NULL;
3559         if ((!(r->anchored_substr || r->anchored_utf8) || r->anchored_offset)
3560             && stclass_flag
3561             && !(data.start_class->flags & ANYOF_EOS)
3562             && !cl_is_anything(data.start_class))
3563         {
3564             const I32 n = add_data(pRExC_state, 1, "f");
3565
3566             Newx(RExC_rx->data->data[n], 1,
3567                 struct regnode_charclass_class);
3568             StructCopy(data.start_class,
3569                        (struct regnode_charclass_class*)RExC_rx->data->data[n],
3570                        struct regnode_charclass_class);
3571             r->regstclass = (regnode*)RExC_rx->data->data[n];
3572             r->reganch &= ~ROPT_SKIP;   /* Used in find_byclass(). */
3573             DEBUG_COMPILE_r({ SV *sv = sv_newmortal();
3574                       regprop(r, sv, (regnode*)data.start_class);
3575                       PerlIO_printf(Perl_debug_log,
3576                                     "synthetic stclass \"%s\".\n",
3577                                     SvPVX_const(sv));});
3578         }
3579
3580         /* A temporary algorithm prefers floated substr to fixed one to dig more info. */
3581         if (longest_fixed_length > longest_float_length) {
3582             r->check_substr = r->anchored_substr;
3583             r->check_utf8 = r->anchored_utf8;
3584             r->check_offset_min = r->check_offset_max = r->anchored_offset;
3585             if (r->reganch & ROPT_ANCH_SINGLE)
3586                 r->reganch |= ROPT_NOSCAN;
3587         }
3588         else {
3589             r->check_substr = r->float_substr;
3590             r->check_utf8 = r->float_utf8;
3591             r->check_offset_min = data.offset_float_min;
3592             r->check_offset_max = data.offset_float_max;
3593         }
3594         /* XXXX Currently intuiting is not compatible with ANCH_GPOS.
3595            This should be changed ASAP!  */
3596         if ((r->check_substr || r->check_utf8) && !(r->reganch & ROPT_ANCH_GPOS)) {
3597             r->reganch |= RE_USE_INTUIT;
3598             if (SvTAIL(r->check_substr ? r->check_substr : r->check_utf8))
3599                 r->reganch |= RE_INTUIT_TAIL;
3600         }
3601     }
3602     else {
3603         /* Several toplevels. Best we can is to set minlen. */
3604         I32 fake;
3605         struct regnode_charclass_class ch_class;
3606         I32 last_close = 0;
3607         
3608         DEBUG_COMPILE_r(PerlIO_printf(Perl_debug_log, "\n"));
3609
3610         scan = r->program + 1;
3611         cl_init(pRExC_state, &ch_class);
3612         data.start_class = &ch_class;
3613         data.last_closep = &last_close;
3614
3615         minlen = study_chunk(pRExC_state, &scan, &fake, scan + RExC_size,
3616             &data, SCF_DO_STCLASS_AND|SCF_WHILEM_VISITED_POS,0);
3617
3618 #ifdef TRIE_STUDY_OPT
3619         if ( (data.flags & SCF_EXACT_TRIE) && ! restudied++ ) {
3620             goto reStudy;
3621         }
3622 #endif
3623
3624         r->check_substr = r->check_utf8 = r->anchored_substr = r->anchored_utf8
3625                 = r->float_substr = r->float_utf8 = NULL;
3626         if (!(data.start_class->flags & ANYOF_EOS)
3627             && !cl_is_anything(data.start_class))
3628         {
3629             const I32 n = add_data(pRExC_state, 1, "f");
3630
3631             Newx(RExC_rx->data->data[n], 1,
3632                 struct regnode_charclass_class);
3633             StructCopy(data.start_class,
3634                        (struct regnode_charclass_class*)RExC_rx->data->data[n],
3635                        struct regnode_charclass_class);
3636             r->regstclass = (regnode*)RExC_rx->data->data[n];
3637             r->reganch &= ~ROPT_SKIP;   /* Used in find_byclass(). */
3638             DEBUG_COMPILE_r({ SV* sv = sv_newmortal();
3639                       regprop(r, sv, (regnode*)data.start_class);
3640                       PerlIO_printf(Perl_debug_log,
3641                                     "synthetic stclass \"%s\".\n",
3642                                     SvPVX_const(sv));});
3643         }
3644     }
3645
3646     r->minlen = minlen;
3647     if (RExC_seen & REG_SEEN_GPOS)
3648         r->reganch |= ROPT_GPOS_SEEN;
3649     if (RExC_seen & REG_SEEN_LOOKBEHIND)
3650         r->reganch |= ROPT_LOOKBEHIND_SEEN;
3651     if (RExC_seen & REG_SEEN_EVAL)
3652         r->reganch |= ROPT_EVAL_SEEN;
3653     if (RExC_seen & REG_SEEN_CANY)
3654         r->reganch |= ROPT_CANY_SEEN;
3655     Newxz(r->startp, RExC_npar, I32);
3656     Newxz(r->endp, RExC_npar, I32);
3657
3658     DEBUG_r( RX_DEBUG_on(r) );
3659     DEBUG_DUMP_r({
3660         PerlIO_printf(Perl_debug_log,"Final program:\n");
3661         regdump(r);
3662     });
3663     DEBUG_OFFSETS_r(if (r->offsets) {
3664         const U32 len = r->offsets[0];
3665         U32 i;
3666         GET_RE_DEBUG_FLAGS_DECL;
3667         PerlIO_printf(Perl_debug_log, "Offsets: [%"UVuf"]\n\t", (UV)r->offsets[0]);
3668         for (i = 1; i <= len; i++) {
3669             if (r->offsets[i*2-1] || r->offsets[i*2])
3670                 PerlIO_printf(Perl_debug_log, "%"UVuf":%"UVuf"[%"UVuf"] ",
3671                 i, (UV)r->offsets[i*2-1], (UV)r->offsets[i*2]);
3672             }
3673         PerlIO_printf(Perl_debug_log, "\n");
3674     });
3675     return(r);
3676 }
3677
3678
3679 #define DEBUG_PARSE_MSG(funcname)     DEBUG_PARSE_r({           \
3680     int rem=(int)(RExC_end - RExC_parse);                       \
3681     int cut;                                                    \
3682     int num;                                                    \
3683     int iscut=0;                                                \
3684     if (rem>10) {                                               \
3685         rem=10;                                                 \
3686         iscut=1;                                                \
3687     }                                                           \
3688     cut=10-rem;                                                 \
3689     if (RExC_lastparse!=RExC_parse)                             \
3690         PerlIO_printf(Perl_debug_log," >%.*s%-*s",              \
3691             rem, RExC_parse,                                    \
3692             cut + 4,                                            \
3693             iscut ? "..." : "<"                                 \
3694         );                                                      \
3695     else                                                        \
3696         PerlIO_printf(Perl_debug_log,"%16s","");                \
3697                                                                 \
3698     if (SIZE_ONLY)                                              \
3699        num=RExC_size;                                           \
3700     else                                                        \
3701        num=REG_NODE_NUM(RExC_emit);                             \
3702     if (RExC_lastnum!=num)                                      \
3703        PerlIO_printf(Perl_debug_log,"|%4d",num);                 \
3704     else                                                        \
3705        PerlIO_printf(Perl_debug_log,"|%4s","");                  \
3706     PerlIO_printf(Perl_debug_log,"|%*s%-4s",                    \
3707         (int)((depth*2)), "",                                   \
3708         (funcname)                                              \
3709     );                                                          \
3710     RExC_lastnum=num;                                           \
3711     RExC_lastparse=RExC_parse;                                  \
3712 })
3713
3714
3715
3716 #define DEBUG_PARSE(funcname)     DEBUG_PARSE_r({           \
3717     DEBUG_PARSE_MSG((funcname));                            \
3718     PerlIO_printf(Perl_debug_log,"%4s","\n");               \
3719 })
3720 /*
3721  - reg - regular expression, i.e. main body or parenthesized thing
3722  *
3723  * Caller must absorb opening parenthesis.
3724  *
3725  * Combining parenthesis handling with the base level of regular expression
3726  * is a trifle forced, but the need to tie the tails of the branches to what
3727  * follows makes it hard to avoid.
3728  */
3729 #define REGTAIL(x,y,z) regtail((x),(y),(z),depth+1)
3730 #ifdef DEBUGGING
3731 #define REGTAIL_STUDY(x,y,z) regtail_study((x),(y),(z),depth+1)
3732 #else
3733 #define REGTAIL_STUDY(x,y,z) regtail((x),(y),(z),depth+1)
3734 #endif
3735
3736 STATIC regnode *
3737 S_reg(pTHX_ RExC_state_t *pRExC_state, I32 paren, I32 *flagp,U32 depth)
3738     /* paren: Parenthesized? 0=top, 1=(, inside: changed to letter. */
3739 {
3740     dVAR;
3741     register regnode *ret;              /* Will be the head of the group. */
3742     register regnode *br;
3743     register regnode *lastbr;
3744     register regnode *ender = NULL;
3745     register I32 parno = 0;
3746     I32 flags;
3747     const I32 oregflags = RExC_flags;
3748     bool have_branch = 0;
3749     bool is_open = 0;
3750
3751     /* for (?g), (?gc), and (?o) warnings; warning
3752        about (?c) will warn about (?g) -- japhy    */
3753
3754 #define WASTED_O  0x01
3755 #define WASTED_G  0x02
3756 #define WASTED_C  0x04
3757 #define WASTED_GC (0x02|0x04)
3758     I32 wastedflags = 0x00;
3759
3760     char * parse_start = RExC_parse; /* MJD */
3761     char * const oregcomp_parse = RExC_parse;
3762
3763     GET_RE_DEBUG_FLAGS_DECL;
3764     DEBUG_PARSE("reg ");
3765
3766
3767     *flagp = 0;                         /* Tentatively. */
3768
3769
3770     /* Make an OPEN node, if parenthesized. */
3771     if (paren) {
3772         if (*RExC_parse == '?') { /* (?...) */
3773             U32 posflags = 0, negflags = 0;
3774             U32 *flagsp = &posflags;
3775             bool is_logical = 0;
3776             const char * const seqstart = RExC_parse;
3777
3778             RExC_parse++;
3779             paren = *RExC_parse++;
3780             ret = NULL;                 /* For look-ahead/behind. */
3781             switch (paren) {
3782             case '<':           /* (?<...) */
3783                 RExC_seen |= REG_SEEN_LOOKBEHIND;
3784                 if (*RExC_parse == '!')
3785                     paren = ',';
3786                 if (*RExC_parse != '=' && *RExC_parse != '!')
3787                     goto unknown;
3788                 RExC_parse++;
3789             case '=':           /* (?=...) */
3790             case '!':           /* (?!...) */
3791                 RExC_seen_zerolen++;
3792             case ':':           /* (?:...) */
3793             case '>':           /* (?>...) */
3794                 break;
3795             case '$':           /* (?$...) */
3796             case '@':           /* (?@...) */
3797                 vFAIL2("Sequence (?%c...) not implemented", (int)paren);
3798                 break;
3799             case '#':           /* (?#...) */
3800                 while (*RExC_parse && *RExC_parse != ')')
3801                     RExC_parse++;
3802                 if (*RExC_parse != ')')
3803                     FAIL("Sequence (?#... not terminated");
3804                 nextchar(pRExC_state);
3805                 *flagp = TRYAGAIN;
3806                 return NULL;
3807             case 'p':           /* (?p...) */
3808                 if (SIZE_ONLY && ckWARN2(WARN_DEPRECATED, WARN_REGEXP))
3809                     vWARNdep(RExC_parse, "(?p{}) is deprecated - use (??{})");
3810                 /* FALL THROUGH*/
3811             case '?':           /* (??...) */
3812                 is_logical = 1;
3813                 if (*RExC_parse != '{')
3814                     goto unknown;
3815                 paren = *RExC_parse++;
3816                 /* FALL THROUGH */
3817             case '{':           /* (?{...}) */
3818             {
3819                 I32 count = 1, n = 0;
3820                 char c;
3821                 char *s = RExC_parse;
3822
3823                 RExC_seen_zerolen++;
3824                 RExC_seen |= REG_SEEN_EVAL;
3825                 while (count && (c = *RExC_parse)) {
3826                     if (c == '\\') {
3827                         if (RExC_parse[1])
3828                             RExC_parse++;
3829                     }
3830                     else if (c == '{')
3831                         count++;
3832                     else if (c == '}')
3833                         count--;
3834                     RExC_parse++;
3835                 }
3836                 if (*RExC_parse != ')') {
3837                     RExC_parse = s;             
3838                     vFAIL("Sequence (?{...}) not terminated or not {}-balanced");
3839                 }
3840                 if (!SIZE_ONLY) {
3841                     PAD *pad;
3842                     OP_4tree *sop, *rop;
3843                     SV * const sv = newSVpvn(s, RExC_parse - 1 - s);
3844
3845                     ENTER;
3846                     Perl_save_re_context(aTHX);
3847                     rop = sv_compile_2op(sv, &sop, "re", &pad);
3848                     sop->op_private |= OPpREFCOUNTED;
3849                     /* re_dup will OpREFCNT_inc */
3850                     OpREFCNT_set(sop, 1);
3851                     LEAVE;
3852
3853                     n = add_data(pRExC_state, 3, "nop");
3854                     RExC_rx->data->data[n] = (void*)rop;
3855                     RExC_rx->data->data[n+1] = (void*)sop;
3856                     RExC_rx->data->data[n+2] = (void*)pad;
3857                     SvREFCNT_dec(sv);
3858                 }
3859                 else {                                          /* First pass */
3860                     if (PL_reginterp_cnt < ++RExC_seen_evals
3861                         && IN_PERL_RUNTIME)
3862                         /* No compiled RE interpolated, has runtime
3863                            components ===> unsafe.  */
3864                         FAIL("Eval-group not allowed at runtime, use re 'eval'");
3865                     if (PL_tainting && PL_tainted)
3866                         FAIL("Eval-group in insecure regular expression");
3867 #if PERL_VERSION > 8
3868                     if (IN_PERL_COMPILETIME)
3869                         PL_cv_has_eval = 1;
3870 #endif
3871                 }
3872
3873                 nextchar(pRExC_state);
3874                 if (is_logical) {
3875                     ret = reg_node(pRExC_state, LOGICAL);
3876                     if (!SIZE_ONLY)
3877                         ret->flags = 2;
3878                     REGTAIL(pRExC_state, ret, reganode(pRExC_state, EVAL, n));
3879                     /* deal with the length of this later - MJD */
3880                     return ret;
3881                 }
3882                 ret = reganode(pRExC_state, EVAL, n);
3883                 Set_Node_Length(ret, RExC_parse - parse_start + 1);
3884                 Set_Node_Offset(ret, parse_start);
3885                 return ret;
3886             }
3887             case '(':           /* (?(?{...})...) and (?(?=...)...) */
3888             {
3889                 if (RExC_parse[0] == '?') {        /* (?(?...)) */
3890                     if (RExC_parse[1] == '=' || RExC_parse[1] == '!'
3891                         || RExC_parse[1] == '<'
3892                         || RExC_parse[1] == '{') { /* Lookahead or eval. */
3893                         I32 flag;
3894                         
3895                         ret = reg_node(pRExC_state, LOGICAL);
3896                         if (!SIZE_ONLY)
3897                             ret->flags = 1;
3898                         REGTAIL(pRExC_state, ret, reg(pRExC_state, 1, &flag,depth+1));
3899                         goto insert_if;
3900                     }
3901                 }
3902                 else if (RExC_parse[0] >= '1' && RExC_parse[0] <= '9' ) {
3903                     /* (?(1)...) */
3904                     char c;
3905                     parno = atoi(RExC_parse++);
3906
3907                     while (isDIGIT(*RExC_parse))
3908                         RExC_parse++;
3909                     ret = reganode(pRExC_state, GROUPP, parno);
3910
3911                     if ((c = *nextchar(pRExC_state)) != ')')
3912                         vFAIL("Switch condition not recognized");
3913                   insert_if:
3914                     REGTAIL(pRExC_state, ret, reganode(pRExC_state, IFTHEN, 0));
3915                     br = regbranch(pRExC_state, &flags, 1,depth+1);
3916                     if (br == NULL)
3917                         br = reganode(pRExC_state, LONGJMP, 0);
3918                     else
3919                         REGTAIL(pRExC_state, br, reganode(pRExC_state, LONGJMP, 0));
3920                     c = *nextchar(pRExC_state);
3921                  &n