pod/perlreguts.pod

   1 =head1 NAME
   2
   3 perlreguts - Description of the Perl regular expression engine.
   4
   5 =head1 DESCRIPTION
   6
   7 This document is an attempt to shine some light on the guts of the regex
   8 engine and how it works. The regex engine represents a signifigant chunk
   9 of the perl codebase, but is relatively poorly understood. This document
  10 is a meagre attempt at addressing this situation. It is derived from the
  11 authors experience, comments in the source code, other papers on the
  12 regex engine, feedback in p5p, and no doubt other places as well.
  13
  14 B<WARNING!> It should be clearly understood that this document
  15 represents the state of the regex engine as the author understands it at
  16 the time of writing. It is B<NOT> an API definition, it is purely an
  17 internals guide for those who want to hack the regex engine, or
  18 understand how the regex engine works. Readers of this document are
  19 expected to understand perls regex syntax and its usage in detail, if
  20 you are a beginner you are in the wrong the place.
  21
  22 =head1 OVERVIEW
  23
  24 =head2 A quick note on terms
  25
  26 There is some debate as to whether to say 'regexp' or 'regex'. In this
  27 document we will use the term "regex" unless there is a special reason
  28 not to, and then we will explain why.
  29
  30 When speaking about regexes we need to distinguish between their source
  31 code form and their internal form. In this document we will use the term
  32 "pattern" when we speak of their textual, source code form, the term
  33 "program" when we speak of their internal representation. These
  34 correspond to the terms C<S-regex> and C<B-regex> that Mark Jason
  35 Dominus employs in his paper on "Rx"[1].
  36
  37 =head2 What is a regular expression engine?
  38
  39 A regular expression engine is a program whose job is to efficiently
  40 find a section of a string that matches a set criteria of criteria. The
  41 criteria is expressed in text using a formal language. See perlre for a
  42 full definition of the language.
  43
  44 So the job in less grandiose terms is to some turn a pattern into
  45 something the computer can efficiently use to find the matching point in
  46 the string.
  47
  48 To do this we need to produce a program by parsing the text. We then
  49 need to execute the program to find the point in the string that
  50 matches. And we need to do the whole thing efficiently.
  51
  52 =head2 Structure of a Regexp Program
  53
  54 =head3 High Level
  55
  56 Although it is a bit confusing and some object to the terminology it
  57 is worth taking a look at a comment that has
  58 been in regexp.h for years:
  59
  60 I<This is essentially a linear encoding of a nondeterministic
  61 finite-state machine (aka syntax charts or "railroad normal form" in
  62 parsing technology).>
  63
  64 The term "railroad normal form" is a bit esoteric, with "syntax
  65 diagram/charts", or "railroad diagram/charts" being more common terms.
  66 Nevertheless it provides a useful mental image of a regex program: Each
  67 node can be thought of as a unit of track, with a single entry and in
  68 most cases a single exit point (there are pieces of track that fork, but
  69 statistically not many),  and the total forms a system of track with a
  70 single entry and single exit point. The matching process can be thought
  71 of as a car that moves on the track, with the particular route through
  72 the system being determined by the character read at each possible
  73 connector point. A car can roll off the track at any point but it may
  74 not procede unless it matches the track...
  75
  76 Thus the pattern C</foo(?:\w+|\d+|\s+)bar/> can be thought of as the
  77 following chart:
  78
  79                   [start]
  80                      |
  81                    <foo>
  82                      |
  83                  +---+---+
  84                  |   |   |
  85                <\w+> | <\s+>
  86                  | <\d+> |
  87                  |   |   |
  88                  +---+---+
  89                      |
  90                    <bar>
  91                      |
  92                    [end]
  93
  94 The truth of the matter is that perls regular expressions these days are
  95 way beyond such models, but they can help when trying to get your
  96 bearings, and they do match pretty closely with the current
  97 implementation.
  98
  99 To be more precise we will say that a regex program is an encoding
 100 of a graph.  Each node in the graph corresponds to part of
 101 the original regex pattern, such as a literal string or a branch,
 102 and has a pointer to the nodes representing the next component
 103 to be matched. Since "node" and opcode are overloaded terms in the
 104 perl source, we will call the nodes in a regex program 'regops'.
 105
 106 The program is represented by an array of regnode structures, one or
 107 more of which together represent a single regop of the program. Struct
 108 regnode is the smallest struct needed and has a field structure which is
 109 shared with all the other larger structures.
 110
 111 "Next" pointers of all regops except BRANCH implement concatenation; a
 112 "next" pointer with a BRANCH on both ends of it is connecting two
 113 alternatives.  [Here we have one of the subtle syntax dependencies:  an
 114 individual BRANCH (as opposed to a collection of them) is never
 115 concatenated with anything because of operator precedence.
 116
 117 The operand of some types of regop is a literal string; for others,
 118 it is a regop leading into a sub-program.  In particular, the operand
 119 of a BRANCH node is the first regop of the branch.
 120
 121 B<NOTE>: As the railroad metaphor suggests this is B<not> a tree
 122 structure:  the tail of the branch connects to the thing following the
 123 set of BRANCHes.  It is a like a single line of railway track that
 124 splits as it goes into a station or railway yard and rejoins as it comes
 125 out the other side.
 126
 127 =head3 Regops
 128
 129 The base structure of a regop is defined in regexp.h as follows:
 130
 131     struct regnode {
 132         U8  flags;    /* Various purposes, sometimes overriden */
 133         U8  type;     /* Opcode value as specified by regnodes.h */
 134         U16 next_off; /* Offset in size regnode */
 135     };
 136
 137 Other larger regnode-like structures are defined in regcomp.h. They
 138 are almost like subclasses in that they have the same fields as
 139 regnode, with possibly additional fields following in
 140 the structure, and in some cases the specific meaning (and name)
 141 of some of base fields are overriden. The following is a more
 142 complete description.
 143
 144 =over 4
 145
 146 =item regnode_1
 147
 148 =item regnode_2
 149
 150 regnode_1 structures have the same header, followed by a single
 151 four-byte argument; regnode_2 structures contain two two-byte
 152 arguments instead:
 153
 154     regnode_1                U32 arg1;
 155     regnode_2                U16 arg1;  U16 arg2;
 156
 157 =item regnode_string
 158
 159 regnode_string structures, used for literal strings, follow the header
 160 with a one-byte length and then the string data. Strings are padded on
 161 the end with zero bytes so that the total length of the node is a
 162 multiple of four bytes:
 163
 164     regnode_string           char string[1];
 165                              U8 str_len; (overides flags)
 166
 167 =item regnode_charclass
 168
 169 character classes are represented by regnode_charclass structures,
 170 which have a four-byte argument and then a 32-byte (256-bit) bitmap
 171 indicating which characters are included in the class.
 172
 173     regnode_charclass        U32 arg1;
 174                              char bitmap[ANYOF_BITMAP_SIZE];
 175
 176 =item regnode_charclass_class
 177
 178 There is also a larger form of a char class structure used to represent
 179 POSIX char classes called regnode_charclass_class which contains the
 180 same fields plus an additional 4-byte (32-bit) bitmap indicating which
 181 POSIX char class have been included.
 182
 183     regnode_charclass_class  U32 arg1;
 184                              char bitmap[ANYOF_BITMAP_SIZE];
 185                              char classflags[ANYOF_CLASSBITMAP_SIZE];
 186
 187 =back
 188
 189 regnodes.h defines an array called regarglen[] which gives the size
 190 of each opcode in units of size regnode (4-byte). A macro is used
 191 to calculate the size of an EXACT node based on its C<str_len> field.
 192
 193 The opcodes are defined in regnodes.h which is generated from
 194 regcomp.sym by regcomp.pl. Currently the maximum possible number
 195 of distinct opcodes is restricted to 256, with about 1/4 already
 196 used.
 197
 198 There's a set of macros provided to make accessing the fields
 199 easier and more consistent. These include C<OP()> which is used to tell
 200 the type of a regnode-like structure, NEXT_OFF() which is the offset to
 201 the next node (more on this later), ARG(), ARG1(), ARG2(), ARG_SET(),
 202 and equivelents for reading and setting the arguments, STR_LEN(),
 203 STRING(), and OPERAND() for manipulating strings and regop bearing
 204 types.
 205
 206 =head3 What opcode is next?
 207
 208 There are three distinct concepts of "next" in the regex engine, and
 209 it is important to keep them clear.
 210
 211 =over 4
 212
 213 =item *
 214
 215 There is the "next regnode" from a given regnode, a value which is
 216 rarely useful except that sometimes it matches up in terms of value
 217 with one of the others, and that sometimes the code assumes this to
 218 always be so.
 219
 220 =item *
 221
 222 There is the "next opcode" from a given opcode/regnode. This is the
 223 opcode physically located after the the current one, as determined by
 224 the size of the current opcode. This is often useful, such as when
 225 dumping the structure we use this order to traverse. Sometimes the code
 226 assumes that the "next regnode" is the same as the "next opcode", or in
 227 other words assumes that the sizeof a given opcode type is always going
 228 to be 1 regnode large.
 229
 230 =item *
 231
 232 There is the "regnext" from a given opcode. This is the opcode which
 233 is reached by jumping forward by the value of NEXT_OFF(),
 234 or in a few cases for longer jumps by the arg1 field of the regnode_1
 235 structure. The subroutine regnext() handles this transparently.
 236 This is the logical successor of the node, which in some cases, like
 237 that of the BRANCH opcode, has special meaning.
 238
 239 =back
 240
 241 =head1 PROCESS OVERVIEW
 242
 243 Broadly speaking performing a match of a string against a pattern
 244 involves the following steps
 245
 246     A. Compilation
 247         1. Parsing for size
 248         2. Parsing for construction
 249         3. Peep-hole Optimisation and Analysis
 250     B. Execution
 251         4. Start position and no-match optimisations
 252         5. Program execution
 253
 254 Where these steps occur in the actual execution of a perl program is
 255 determined by whether the pattern involves interpolating any string
 256 variables. If it does then compilation happens at run time. If it
 257 doesn't then it happens at compile time. (The C</o> modifier changes this,
 258 as does C<qr//> to a certain extent.) The engine doesn't really care that
 259 much.
 260
 261 =head2 Compilation
 262
 263 This code exists primarily in regcomp.c, along with the header files
 264 regcomp.h, regexp.h, regnodes.h.
 265
 266 Compilation starts with C<pregcomp()>, which is mostly an initialization
 267 wrapper which farms out two other routines for the heavy lifting. The
 268 first being C<reg()> which is the start point for parsing, and
 269 C<study_chunk()> which is responsible for optimisation.
 270
 271 Initialization in C<pregcomp()> mostly involves the creation and data
 272 filling of a special structure RExC_state_t, (defined in regcomp.c).
 273 Almost all internally used routines in regcomp.h take a pointer to one
 274 of these structures as their first argument, with the name *pRExC_state.
 275 This structure is used to store the compilation state and contains many
 276 fields. Likewise their are many macros defined which operate on this
 277 variable. Anything that looks like RExC_xxxx is a macro that operates on
 278 this pointer/structure.
 279
 280 =head3 Parsing for size
 281
 282 In this pass the input pattern is parsed in order to calculate how much
 283 space is needed for each opcode we would need to emit. The size is also
 284 used to determine whether long jumps will be required in the program.
 285
 286 This stage is controlled by the macro SIZE_ONLY being set.
 287
 288 The parse procedes pretty much exactly as it does during the
 289 construction phase except that most routines are shortcircuited to
 290 change the size field RExC_size and not actually do anything.
 291
 292 =head3 Parsing for construcution
 293
 294 Once the size of the program has been determine the pattern is parsed
 295 again, but this time for real. Now SIZE_ONLY will be false, and the
 296 actual construction can occur.
 297
 298 C<reg()> is the start of the parse process. It is responsible for
 299 parsing an arbitrary chunk of pattern up to either the end of the
 300 string, or the first closing parenthesis it encounters in the pattern.
 301 This means it can be used to parse the toplevel regex, or any section
 302 inside of a grouping parenthesis. It also handles the "special parens"
 303 that perls regexes have. For instance when parsing C</x(?:foo)y/> C<reg()>
 304 will at one point be called to parse from the '?' symbol up to and
 305 including the ')'.
 306
 307 Additionally C<reg()> is responsible for parsing the one or more
 308 branches from the pattern, and for "finishing them off" by correctly
 309 setting their next pointers. In order to do the parsing it repeatedly
 310 calls out to C<regbranch()> which is responsible for handling up to the
 311 first C<|> symbol it sees.
 312
 313 C<regbranch()> in turn calls C<regpiece()> which is responsible for
 314 handling "things" followed by a quantifier. In order to parse the
 315 "things" C<regatom()> is called. This is the lowest level routine which
 316 is responsible for parsing out constant strings, char classes, and the
 317 various special symbols like C<$>. If C<regatom()> encounters a '('
 318 character it in turn calls C<reg()>.
 319
 320 The routine C<regtail()> is called by both C<reg()>, C<regbranch()>
 321 in order to "set the tail pointer" correctly. When executing and
 322 we get to the end of a branch we need to go to node following the
 323 grouping parens. When parsing however we don't know where the end will
 324 be until we get there, so when we do we must go back and update the
 325 offsets as appropriate. C<regtail> is used to make this easier.
 326
 327 A subtlety of the parse process means that a regex like C</foo/> is
 328 originally parsed into an alternation with a single branch. It is only
 329 afterwards that the optimizer converts single branch alternations into the
 330 simpler form.
 331
 332 =head3 Parse Call Graph and a Grammar
 333
 334 The call graph looks like this:
 335
 336     reg()                        # parse a top level regex, or inside of parens
 337         regbranch()              # parse a single branch of an alternation
 338             regpiece()           # parse a pattern followed by a quantifier
 339                 regatom()        # parse a simple pattern
 340                     regclass()   #   used to handle a class
 341                     reg()        #   used to handle a parenthesized subpattern
 342                     ....
 343             ...
 344             regtail()            # finish off the branch
 345         ...
 346         regtail()                # finish off the branch sequence. Tie each
 347                                  # branches tail to the tail of the sequence
 348                                  # (NEW) In Debug mode this is
 349                                  # regtail_study().
 350
 351 A grammar form might be something like this:
 352
 353     atom  : constant | class
 354     quant : '*' | '+' | '?' | '{min,max}'
 355     _branch: piece
 356            | piece _branch
 357            | nothing
 358     branch: _branch
 359           | _branch '|' branch
 360     group : '(' branch ')'
 361     _piece: atom | group
 362     piece : _piece
 363           | _piece quant
 364
 365 =head3 Debug Output
 366
 367 In bleadperl you can C<< use re Debug => 'PARSE'; >> to see some trace
 368 information about the parse process. We will start with some simple
 369 patterns and build up to more complex patterns.
 370
 371 So when we parse C</foo/> we see something like the following table. The
 372 left shows whats being parsed, the number indicates where the next regop
 373 would go. The stuff on the right is the trace output of the graph. The
 374 names are chosen to be short to make it less dense on the screen. 'tsdy'
 375 is a special form of C<regtail()> which does some extra analysis.
 376
 377  >foo<             1            reg
 378                                   brnc
 379                                     piec
 380                                       atom
 381  ><                4              tsdy~ EXACT <foo> (EXACT) (1)
 382                                       ~ attach to END (3) offset to 2
 383
 384 The resulting program then looks like:
 385
 386    1: EXACT <foo>(3)
 387    3: END(0)
 388
 389 As you can see, even though we parsed out a branch and a piece, it was ultimately
 390 only an atom. The final program shows us how things work. We have an EXACT regop,
 391 followed by an END regop. The number in parens indicates where the 'regnext' of
 392 the node goes. The 'regnext' of an END regop is unused, as END regops mean
 393 we have successfully matched. The number on the left indicates the position of
 394 the regop in the regnode array.
 395
 396 Now lets try a harder pattern. We will add a quantifier so we have the pattern
 397 C</foo+/>. We will see that C<regbranch()> calls C<regpiece()> regpiece twice.
 398
 399  >foo+<            1            reg
 400                                   brnc
 401                                     piec
 402                                       atom
 403  >o+<              3                piec
 404                                       atom
 405  ><                6                tail~ EXACT <fo> (1)
 406                    7              tsdy~ EXACT <fo> (EXACT) (1)
 407                                       ~ PLUS (END) (3)
 408                                       ~ attach to END (6) offset to 3
 409
 410 And we end up with the program:
 411
 412    1: EXACT <fo>(3)
 413    3: PLUS(6)
 414    4:   EXACT <o>(0)
 415    6: END(0)
 416
 417 Now we have a special case. The EXACT regop has a regnext of 0. This is
 418 because if it matches it should try to match itself again. The PLUS regop
 419 handles the actual failure of the EXACT regop and acts appropriately (going
 420 to regnode 6 if the EXACT matched at least once, or failing if it didn't.)
 421
 422 Now for something much more complex: C</x(?:foo*|b[a][rR])(foo|bar)$/>
 423
 424  >x(?:foo*|b...    1            reg
 425                                   brnc
 426                                     piec
 427                                       atom
 428  >(?:foo*|b[...    3                piec
 429                                       atom
 430  >?:foo*|b[a...                         reg
 431  >foo*|b[a][...                           brnc
 432                                             piec
 433                                               atom
 434  >o*|b[a][rR...    5                        piec
 435                                               atom
 436  >|b[a][rR])...    8                        tail~ EXACT <fo> (3)
 437  >b[a][rR])(...    9                      brnc
 438                   10                        piec
 439                                               atom
 440  >[a][rR])(f...   12                        piec
 441                                               atom
 442  >a][rR])(fo...                                 clas
 443  >[rR])(foo|...   14                        tail~ EXACT <b> (10)
 444                                             piec
 445                                               atom
 446  >rR])(foo|b...                                 clas
 447  >)(foo|bar)...   25                        tail~ EXACT <a> (12)
 448                                           tail~ BRANCH (3)
 449                   26                      tsdy~ BRANCH (END) (9)
 450                                               ~ attach to TAIL (25) offset to 16
 451                                           tsdy~ EXACT <fo> (EXACT) (4)
 452                                               ~ STAR (END) (6)
 453                                               ~ attach to TAIL (25) offset to 19
 454                                           tsdy~ EXACT <b> (EXACT) (10)
 455                                               ~ EXACT <a> (EXACT) (12)
 456                                               ~ ANYOF[Rr] (END) (14)
 457                                               ~ attach to TAIL (25) offset to 11
 458  >(foo|bar)$<                       tail~ EXACT <x> (1)
 459                                     piec
 460                                       atom
 461  >foo|bar)$<                            reg
 462                   28                      brnc
 463                                             piec
 464                                               atom
 465  >|bar)$<         31                      tail~ OPEN1 (26)
 466  >bar)$<                                  brnc
 467                   32                        piec
 468                                               atom
 469  >)$<             34                      tail~ BRANCH (28)
 470                   36                      tsdy~ BRANCH (END) (31)
 471                                               ~ attach to CLOSE1 (34) offset to 3
 472                                           tsdy~ EXACT <foo> (EXACT) (29)
 473                                               ~ attach to CLOSE1 (34) offset to 5
 474                                           tsdy~ EXACT <bar> (EXACT) (32)
 475                                               ~ attach to CLOSE1 (34) offset to 2
 476  >$<                                tail~ BRANCH (3)
 477                                         ~ BRANCH (9)
 478                                         ~ TAIL (25)
 479                                     piec
 480                                       atom
 481  ><               37                tail~ OPEN1 (26)
 482                                         ~ BRANCH (28)
 483                                         ~ BRANCH (31)
 484                                         ~ CLOSE1 (34)
 485                   38              tsdy~ EXACT <x> (EXACT) (1)
 486                                       ~ BRANCH (END) (3)
 487                                       ~ BRANCH (END) (9)
 488                                       ~ TAIL (END) (25)
 489                                       ~ OPEN1 (END) (26)
 490                                       ~ BRANCH (END) (28)
 491                                       ~ BRANCH (END) (31)
 492                                       ~ CLOSE1 (END) (34)
 493                                       ~ EOL (END) (36)
 494                                       ~ attach to END (37) offset to 1<div></div>
 495
 496 Resulting in the program
 497
 498    1: EXACT <x>(3)
 499    3: BRANCH(9)
 500    4:   EXACT <fo>(6)
 501    6:   STAR(26)
 502    7:     EXACT <o>(0)
 503    9: BRANCH(25)
 504   10:   EXACT <ba>(14)
 505   12:   OPTIMIZED (2 nodes)
 506   14:   ANYOF[Rr](26)
 507   25: TAIL(26)
 508   26: OPEN1(28)
 509   28:   TRIE-EXACT(34)
 510         [StS:1 Wds:2 Cs:6 Uq:5 #Sts:7 Mn:3 Mx:3 Stcls:bf]
 511           <foo>
 512           <bar>
 513   30:   OPTIMIZED (4 nodes)
 514   34: CLOSE1(36)
 515   36: EOL(37)
 516   37: END(0)
 517
 518 Here we can see a much more complex program, with various optimisations in
 519 play. At regnode 10 we can see an example where a char class with only
 520 one character in it was turned into an EXACT node. We can also see where
 521 an entire alternation was turned into a TRIE-EXACT node. As a consequence
 522 some of the regnodes have been marked as optimised away. We can see that
 523 the C<$> symbol has been converted into an EOL regop, a special piece of
 524 code that looks for \n or the end of a string.
 525
 526 The next pointer for BRANCHes is interesting in that it points at where
 527 execution should go if the branch fails. When executing if the engine
 528 tries to traverse from a branch to a regnext that isnt a branch then
 529 the engine will know the overall series of branches have failed.
 530
 531 =head3 Peep-hole Optimisation and Analysis
 532
 533 The regular expression engine can be a weighty tool to wield. On long
 534 strings and complex patterns it can end up having to do a lot of work
 535 to find a match, and even more to decide that no match is possible.
 536 Consider a situation like the following pattern.
 537
 538    'ababababababababababab' =~ /(a|b)*z/
 539
 540 The C<(a|b)*> part can match at every char in the string, and then fail
 541 every time because there is no C<z> in the string. So obviously we can
 542 not bother to use the regex engine unless there is a 'z' in the string.
 543 Likewise in a pattern like:
 544
 545    /foo(\w+)bar/
 546
 547 In this case we know that the string must contain a C<foo> which must be
 548 followed by C<bar>. We can use Fast Boyer-More matching as implemented
 549 in fbm_instr() to find the location of these strings. If they dont exist
 550 then we dont need to resort to the much more expensive regex engine.
 551 Even better if they do exist then we can use their positions to
 552 reduce the search space that the regex engine needs to cover to determine
 553 if the entire pattern does match.
 554
 555 There are various aspects of the pattern that can be used to facilitate
 556 optimisations along these lines:
 557
 558     * anchored fixed strings
 559     * floating fixed strings
 560     * minimum and maximum length requirements
 561     * start class
 562     * Beginning/End of line positions
 563
 564 Another form of optimisation that can occur is post-parse "peep-hole"
 565 optimisations, where inefficient constructs are modified so that they
 566 are more efficient. An example of this is TAIL regops which are used
 567 during parsing to mark the end of branches and the end of groups. These
 568 regops are used as place holders during construction and "always match"
 569 so they can be "optimised away" by making the things that point to the
 570 TAIL point to thing the TAIL points to, in essence "skipping" the node.
 571
 572 Another optimisation that can occur is that of "EXACT merging" which is
 573 where two consecutive EXACT nodes are merged into a single more efficient
 574 to execute regop. An even more agressive form of this is that a branch
 575 sequence of the form EXACT BRANCH ... EXACT can be converted into a TRIE
 576 regop.
 577
 578 All of this occurs in the routine study_chunk() which uses a special
 579 structure scan_data_t to store the analysis that it has performed, and
 580 as it goes does the "peep-hole" optimisations.
 581
 582 The code involved in study_chunk() is extremely cryptic. Be careful. :-)
 583
 584 =head2 Execution
 585
 586 Execution of a regex generally involves two phases, the first being
 587 finding the start point in the string where we should match from,
 588 and the second being running the regop interpreter.
 589
 590 If we can tell that there is no valid start point we don't bother running
 591 interpreter at all. Likewise if we know from the analysis phase that we
 592 can not optimise detection of the start position we go straight to the
 593 interpreter.
 594
 595 The two entry points are re_intuit_start() and pregexec(). These routines
 596 have a somewhat incestuous relationship with overlap between their functions,
 597 and pregexec() may even call re_intuit_start() on its own. Nevertheless
 598 the perl source code may call into either, or both.
 599
 600 Execution of the interpreter itself used to be recursive. Due to the
 601 efforts of Dave Mitchel in blead perl it no longer is. Instead an
 602 internal stack is maintained on the heap and the routine is fully
 603 iterative. This can make it tricky as the code is quite conservative
 604 about what state it stores which means that two consecutive lines in the
 605 code can actually be running in totally different contexts due to the
 606 simulated recursion.
 607
 608 =head3 Start position and no-match optimisations
 609
 610 re_intuit_start() is responsible for handling start point and no match
 611 optimisations as determined by the results of the analysis done by
 612 study_chunk() (and described in L<Peep-hole Optimisation and Analysis>).
 613
 614 The basic structure of this routine is to try to find the start and/or
 615 end points of where the pattern could match, and to ensure that the string
 616 is long enough to match the pattern. It tries to use more efficent
 617 methods over less efficient methods and may involve considerable cross
 618 checking of constraints to find the place in the string that matches.
 619 For instance it may try to determine that a given fixed string must be
 620 not only present but a certain number of chars before the end of the
 621 string, or whatever.
 622
 623 It calls out into several other routines, like fbm_instr() which does
 624 "Fast Boyer More" matching and find_byclass() which is responsible for
 625 finding the start using the first mandatory regop in the program.
 626
 627 When the optimisation criteria have been satisfied reg_try() is called
 628 to perform the match.
 629
 630 =head3 Program execution
 631
 632 C<pregexec()> is the main entry point for running a regex. It contains
 633 support for initializing the regex interpreters state, running
 634 re_intuit_start() if needed, and running the intepreter on the string
 635 from various start positions as needed. When its necessary to use
 636 the regex interpreter C<pregexec()> calls C<regtry()>.
 637
 638 C<regtry()> is the entry point into the regex interpreter. It expects
 639 as arguments a pointer to a regmatch_info structure and a pointer to
 640 a string.  It returns an integer 1 for success and a 0 for failure.
 641 It is basically a setup wrapper around C<regmatch()>.
 642
 643 C<regmatch> is the main "recursive loop" of the interpreter. It is
 644 basically a giant switch statement that executes the regops based on
 645 their type. A few of the regops are implemented as subroutines but
 646 the bulk are inline code.
 647
 648 =head1 MISCELLANEOUS
 649
 650 =head2 UNICODE and Localization Support
 651
 652 No matter how you look at it unicode support is going to be a pain in a
 653 regex engine. Tricks that might be fine when you have 256 possible
 654 characters often won't scale to handle the size of the 'utf8' character
 655 set.  Things you can take for granted with ASCII may not be true with
 656 unicode. For instance in ASCII its safe to assume that
 657 C<sizeof(char1) == sizeof(char2)>, in utf8 it isn't. Unicode case folding is
 658 vastly more complex than the simple rules of English, and even when not
 659 using unicode but only localized single byte encodings things can get
 660 tricky (technically GERMAN-SHARP-ESS should match 'ss' in localized case
 661 insensitive matching.)
 662
 663 Making things worse is that C<utf8> support was a later addition to the
 664 regex engine (as it was to perl) and necessarily this made things a lot
 665 more complicated. Obviously its easier to design a regex engine with
 666 unicode support from the beginning than it is to retrofit one that
 667 wasn't designed with it in mind.
 668
 669 Pretty well every regop that involves looking at the input string has
 670 two cases, one for 'utf8' and one not. In fact its often more complex
 671 than that, as the pattern may be 'utf8' as well.
 672
 673 Care must be taken when making changes to make sure that you handle
 674 utf8 properly both at compile time and at execution time, including
 675 when the string and pattern are mismatched.
 676
 677 The following comment in regcomp.h gives an example of exactly how
 678 tricky this can be:
 679
 680     Two problematic code points in Unicode casefolding of EXACT nodes:
 681
 682     U+0390 - GREEK SMALL LETTER IOTA WITH DIALYTIKA AND TONOS
 683     U+03B0 - GREEK SMALL LETTER UPSILON WITH DIALYTIKA AND TONOS
 684
 685     which casefold to
 686
 687     Unicode                      UTF-8
 688
 689     U+03B9 U+0308 U+0301         0xCE 0xB9 0xCC 0x88 0xCC 0x81
 690     U+03C5 U+0308 U+0301         0xCF 0x85 0xCC 0x88 0xCC 0x81
 691
 692     This means that in case-insensitive matching (or "loose matching",
 693     as Unicode calls it), an EXACTF of length six (the UTF-8 encoded
 694     byte length of the above casefolded versions) can match a target
 695     string of length two (the byte length of UTF-8 encoded U+0390 or
 696     U+03B0). This would rather mess up the minimum length computation.
 697
 698     What we'll do is to look for the tail four bytes, and then peek
 699     at the preceding two bytes to see whether we need to decrease
 700     the minimum length by four (six minus two).
 701
 702     Thanks to the design of UTF-8, there cannot be false matches:
 703     A sequence of valid UTF-8 bytes cannot be a subsequence of
 704     another valid sequence of UTF-8 bytes.
 705
 706 =head1 AUTHOR
 707
 708 by Yves Orton, 2006.
 709
 710 With excerpts from Perl, and contributions and suggestions from
 711 Ronald J. Kimball, Dave Mitchell, Dominic Dunlop, Mark Jason Dominus,
 712 and Stephen McCamant.
 713
 714 =head1 LICENSE
 715
 716 Same terms as Perl.
 717
 718 =head1 REFERENCES
 719
 720 [1] http://perl.plover.com/Rx/paper/
 721
 722 =cut