1=head1 NAME 2 3perlreguts - Description of the Perl regular expression engine. 4 5=head1 DESCRIPTION 6 7This document is an attempt to shine some light on the guts of the regex 8engine and how it works. The regex engine represents a significant chunk 9of the perl codebase, but is relatively poorly understood. This document 10is a meagre attempt at addressing this situation. It is derived from the 11author's experience, comments in the source code, other papers on the 12regex engine, feedback on the perl5-porters mail list, and no doubt other 13places as well. 14 15B<NOTICE!> It should be clearly understood that the behavior and 16structures discussed in this represents the state of the engine as the 17author understood it at the time of writing. It is B<NOT> an API 18definition, it is purely an internals guide for those who want to hack 19the regex engine, or understand how the regex engine works. Readers of 20this document are expected to understand perl's regex syntax and its 21usage in detail. If you want to learn about the basics of Perl's 22regular expressions, see L<perlre>. And if you want to replace the 23regex engine with your own, see L<perlreapi>. 24 25=head1 OVERVIEW 26 27=head2 A quick note on terms 28 29There is some debate as to whether to say "regexp" or "regex". In this 30document we will use the term "regex" unless there is a special reason 31not to, in which case we will explain why. 32 33When speaking about regexes we need to distinguish between their source 34code form and their internal form. In this document we will use the term 35"pattern" when we speak of their textual, source code form, and the term 36"program" when we speak of their internal representation. These 37correspond to the terms I<S-regex> and I<B-regex> that Mark Jason 38Dominus employs in his paper on "Rx" ([1] in L</REFERENCES>). 39 40=head2 What is a regular expression engine? 41 42A regular expression engine is a program that takes a set of constraints 43specified in a mini-language, and then applies those constraints to a 44target string, and determines whether or not the string satisfies the 45constraints. See L<perlre> for a full definition of the language. 46 47In less grandiose terms, the first part of the job is to turn a pattern into 48something the computer can efficiently use to find the matching point in 49the string, and the second part is performing the search itself. 50 51To do this we need to produce a program by parsing the text. We then 52need to execute the program to find the point in the string that 53matches. And we need to do the whole thing efficiently. 54 55=head2 Structure of a Regexp Program 56 57=head3 High Level 58 59Although it is a bit confusing and some people object to the terminology, it 60is worth taking a look at a comment that has 61been in F<regexp.h> for years: 62 63I<This is essentially a linear encoding of a nondeterministic 64finite-state machine (aka syntax charts or "railroad normal form" in 65parsing technology).> 66 67The term "railroad normal form" is a bit esoteric, with "syntax 68diagram/charts", or "railroad diagram/charts" being more common terms. 69Nevertheless it provides a useful mental image of a regex program: each 70node can be thought of as a unit of track, with a single entry and in 71most cases a single exit point (there are pieces of track that fork, but 72statistically not many), and the whole forms a layout with a 73single entry and single exit point. The matching process can be thought 74of as a car that moves along the track, with the particular route through 75the system being determined by the character read at each possible 76connector point. A car can fall off the track at any point but it may 77only proceed as long as it matches the track. 78 79Thus the pattern C</foo(?:\w+|\d+|\s+)bar/> can be thought of as the 80following chart: 81 82 [start] 83 | 84 <foo> 85 | 86 +-----+-----+ 87 | | | 88 <\w+> <\d+> <\s+> 89 | | | 90 +-----+-----+ 91 | 92 <bar> 93 | 94 [end] 95 96The truth of the matter is that perl's regular expressions these days are 97much more complex than this kind of structure, but visualising it this way 98can help when trying to get your bearings, and it matches the 99current implementation pretty closely. 100 101To be more precise, we will say that a regex program is an encoding 102of a graph. Each node in the graph corresponds to part of 103the original regex pattern, such as a literal string or a branch, 104and has a pointer to the nodes representing the next component 105to be matched. Since "node" and "opcode" already have other meanings in the 106perl source, we will call the nodes in a regex program "regops". 107 108The program is represented by an array of C<regnode> structures, one or 109more of which represent a single regop of the program. Struct 110C<regnode> is the smallest struct needed, and has a field structure which is 111shared with all the other larger structures. (Outside this document, the term 112"regnode" is sometimes used to mean "regop", which could be confusing.) 113 114The "next" pointers of all regops except C<BRANCH> implement concatenation; 115a "next" pointer with a C<BRANCH> on both ends of it is connecting two 116alternatives. [Here we have one of the subtle syntax dependencies: an 117individual C<BRANCH> (as opposed to a collection of them) is never 118concatenated with anything because of operator precedence.] 119 120The operand of some types of regop is a literal string; for others, 121it is a regop leading into a sub-program. In particular, the operand 122of a C<BRANCH> node is the first regop of the branch. 123 124B<NOTE>: As the railroad metaphor suggests, this is B<not> a tree 125structure: the tail of the branch connects to the thing following the 126set of C<BRANCH>es. It is a like a single line of railway track that 127splits as it goes into a station or railway yard and rejoins as it comes 128out the other side. 129 130=head3 Regops 131 132The base structure of a regop is defined in F<regexp.h> as follows: 133 134 struct regnode { 135 U8 flags; /* Various purposes, sometimes overridden */ 136 U8 type; /* Opcode value as specified by regnodes.h */ 137 U16 next_off; /* Offset in size regnode */ 138 }; 139 140Other larger C<regnode>-like structures are defined in F<regcomp.h>. They 141are almost like subclasses in that they have the same fields as 142C<regnode>, with possibly additional fields following in 143the structure, and in some cases the specific meaning (and name) 144of some of base fields are overridden. The following is a more 145complete description. 146 147=over 4 148 149=item C<regnode_1> 150 151=item C<regnode_2> 152 153C<regnode_1> structures have the same header, followed by a single 154four-byte argument; C<regnode_2> structures contain two two-byte 155arguments instead: 156 157 regnode_1 U32 arg1; 158 regnode_2 U16 arg1; U16 arg2; 159 160=item C<regnode_string> 161 162C<regnode_string> structures, used for literal strings, follow the header 163with a one-byte length and then the string data. Strings are padded on 164the tail end with zero bytes so that the total length of the node is a 165multiple of four bytes: 166 167 regnode_string char string[1]; 168 U8 str_len; /* overrides flags */ 169 170=item C<regnode_charclass> 171 172Bracketed character classes are represented by C<regnode_charclass> 173structures, which have a four-byte argument and then a 32-byte (256-bit) 174bitmap indicating which characters in the Latin1 range are included in 175the class. 176 177 regnode_charclass U32 arg1; 178 char bitmap[ANYOF_BITMAP_SIZE]; 179 180Various flags whose names begin with C<ANYOF_> are used for special 181situations. Above Latin1 matches and things not known until run-time 182are stored in L</Perl's pprivate structure>. 183 184=item C<regnode_charclass_posixl> 185 186There is also a larger form of a char class structure used to represent 187POSIX char classes under C</l> matching, 188called C<regnode_charclass_posixl> which has an 189additional 32-bit bitmap indicating which POSIX char classes 190have been included. 191 192 regnode_charclass_posixl U32 arg1; 193 char bitmap[ANYOF_BITMAP_SIZE]; 194 U32 classflags; 195 196=back 197 198F<regnodes.h> defines an array called C<regarglen[]> which gives the size 199of each opcode in units of C<size regnode> (4-byte). A macro is used 200to calculate the size of an C<EXACT> node based on its C<str_len> field. 201 202The regops are defined in F<regnodes.h> which is generated from 203F<regcomp.sym> by F<regcomp.pl>. Currently the maximum possible number 204of distinct regops is restricted to 256, with about a quarter already 205used. 206 207A set of macros makes accessing the fields 208easier and more consistent. These include C<OP()>, which is used to determine 209the type of a C<regnode>-like structure; C<NEXT_OFF()>, which is the offset to 210the next node (more on this later); C<ARG()>, C<ARG1()>, C<ARG2()>, C<ARG_SET()>, 211and equivalents for reading and setting the arguments; and C<STR_LEN()>, 212C<STRING()> and C<OPERAND()> for manipulating strings and regop bearing 213types. 214 215=head3 What regop is next? 216 217There are three distinct concepts of "next" in the regex engine, and 218it is important to keep them clear. 219 220=over 4 221 222=item * 223 224There is the "next regnode" from a given regnode, a value which is 225rarely useful except that sometimes it matches up in terms of value 226with one of the others, and that sometimes the code assumes this to 227always be so. 228 229=item * 230 231There is the "next regop" from a given regop/regnode. This is the 232regop physically located after the current one, as determined by 233the size of the current regop. This is often useful, such as when 234dumping the structure we use this order to traverse. Sometimes the code 235assumes that the "next regnode" is the same as the "next regop", or in 236other words assumes that the sizeof a given regop type is always going 237to be one regnode large. 238 239=item * 240 241There is the "regnext" from a given regop. This is the regop which 242is reached by jumping forward by the value of C<NEXT_OFF()>, 243or in a few cases for longer jumps by the C<arg1> field of the C<regnode_1> 244structure. The subroutine C<regnext()> handles this transparently. 245This is the logical successor of the node, which in some cases, like 246that of the C<BRANCH> regop, has special meaning. 247 248=back 249 250=head1 Process Overview 251 252Broadly speaking, performing a match of a string against a pattern 253involves the following steps: 254 255=over 5 256 257=item A. Compilation 258 259=over 5 260 261=item 1. Parsing 262 263=item 2. Peep-hole optimisation and analysis 264 265=back 266 267=item B. Execution 268 269=over 5 270 271=item 3. Start position and no-match optimisations 272 273=item 4. Program execution 274 275=back 276 277=back 278 279 280Where these steps occur in the actual execution of a perl program is 281determined by whether the pattern involves interpolating any string 282variables. If interpolation occurs, then compilation happens at run time. If it 283does not, then compilation is performed at compile time. (The C</o> modifier changes this, 284as does C<qr//> to a certain extent.) The engine doesn't really care that 285much. 286 287=head2 Compilation 288 289This code resides primarily in F<regcomp.c>, along with the header files 290F<regcomp.h>, F<regexp.h> and F<regnodes.h>. 291 292Compilation starts with C<pregcomp()>, which is mostly an initialisation 293wrapper which farms work out to two other routines for the heavy lifting: the 294first is C<reg()>, which is the start point for parsing; the second, 295C<study_chunk()>, is responsible for optimisation. 296 297Initialisation in C<pregcomp()> mostly involves the creation and data-filling 298of a special structure, C<RExC_state_t> (defined in F<regcomp.c>). 299Almost all internally-used routines in F<regcomp.h> take a pointer to one 300of these structures as their first argument, with the name C<pRExC_state>. 301This structure is used to store the compilation state and contains many 302fields. Likewise there are many macros which operate on this 303variable: anything that looks like C<RExC_xxxx> is a macro that operates on 304this pointer/structure. 305 306C<reg()> is the start of the parse process. It is responsible for 307parsing an arbitrary chunk of pattern up to either the end of the 308string, or the first closing parenthesis it encounters in the pattern. 309This means it can be used to parse the top-level regex, or any section 310inside of a grouping parenthesis. It also handles the "special parens" 311that perl's regexes have. For instance when parsing C</x(?:foo)y/>, 312C<reg()> will at one point be called to parse from the "?" symbol up to 313and including the ")". 314 315Additionally, C<reg()> is responsible for parsing the one or more 316branches from the pattern, and for "finishing them off" by correctly 317setting their next pointers. In order to do the parsing, it repeatedly 318calls out to C<regbranch()>, which is responsible for handling up to the 319first C<|> symbol it sees. 320 321C<regbranch()> in turn calls C<regpiece()> which 322handles "things" followed by a quantifier. In order to parse the 323"things", C<regatom()> is called. This is the lowest level routine, which 324parses out constant strings, character classes, and the 325various special symbols like C<$>. If C<regatom()> encounters a "(" 326character it in turn calls C<reg()>. 327 328There used to be two main passes involved in parsing, the first to 329calculate the size of the compiled program, and the second to actually 330compile it. But now there is only one main pass, with an initial crude 331guess based on the length of the input pattern, which is increased if 332necessary as parsing proceeds, and afterwards, trimmed to the actual 333amount used. 334 335However, it may happen that parsing must be restarted at the beginning 336when various circumstances occur along the way. An example is if the 337program turns out to be so large that there are jumps in it that won't 338fit in the normal 16 bits available. There are two special regops that 339can hold bigger jump destinations, BRANCHJ and LONGBRANCH. The parse is 340restarted, and these are used instead of the normal shorter ones. 341Whenever restarting the parse is required, the function returns failure 342and sets a flag as to what needs to be done. This is passed up to the 343top level routine which takes the appropriate action and restarts from 344scratch. In the case of needing longer jumps, the C<RExC_use_BRANCHJ> 345flag is set in the C<RExC_state_t> structure, which the functions know 346to inspect before deciding how to do branches. 347 348In most instances, the function that discovers the issue sets the causal 349flag and returns failure immediately. L</Parsing complications> 350contains an explicit example of how this works. In other cases, such as 351a forward reference to a numbered parenthetical grouping, we need to 352finish the parse to know if that numbered grouping actually appears in 353the pattern. In those cases, the parse is just redone at the end, with 354the knowledge of how many groupings occur in it. 355 356The routine C<regtail()> is called by both C<reg()> and C<regbranch()> 357in order to "set the tail pointer" correctly. When executing and 358we get to the end of a branch, we need to go to the node following the 359grouping parens. When parsing, however, we don't know where the end will 360be until we get there, so when we do we must go back and update the 361offsets as appropriate. C<regtail> is used to make this easier. 362 363A subtlety of the parsing process means that a regex like C</foo/> is 364originally parsed into an alternation with a single branch. It is only 365afterwards that the optimiser converts single branch alternations into the 366simpler form. 367 368=head3 Parse Call Graph and a Grammar 369 370The call graph looks like this: 371 372 reg() # parse a top level regex, or inside of 373 # parens 374 regbranch() # parse a single branch of an alternation 375 regpiece() # parse a pattern followed by a quantifier 376 regatom() # parse a simple pattern 377 regclass() # used to handle a class 378 reg() # used to handle a parenthesised 379 # subpattern 380 .... 381 ... 382 regtail() # finish off the branch 383 ... 384 regtail() # finish off the branch sequence. Tie each 385 # branch's tail to the tail of the 386 # sequence 387 # (NEW) In Debug mode this is 388 # regtail_study(). 389 390A grammar form might be something like this: 391 392 atom : constant | class 393 quant : '*' | '+' | '?' | '{min,max}' 394 _branch: piece 395 | piece _branch 396 | nothing 397 branch: _branch 398 | _branch '|' branch 399 group : '(' branch ')' 400 _piece: atom | group 401 piece : _piece 402 | _piece quant 403 404=head3 Parsing complications 405 406The implication of the above description is that a pattern containing nested 407parentheses will result in a call graph which cycles through C<reg()>, 408C<regbranch()>, C<regpiece()>, C<regatom()>, C<reg()>, C<regbranch()> I<etc> 409multiple times, until the deepest level of nesting is reached. All the above 410routines return a pointer to a C<regnode>, which is usually the last regnode 411added to the program. However, one complication is that reg() returns NULL 412for parsing C<(?:)> syntax for embedded modifiers, setting the flag 413C<TRYAGAIN>. The C<TRYAGAIN> propagates upwards until it is captured, in 414some cases by C<regatom()>, but otherwise unconditionally by 415C<regbranch()>. Hence it will never be returned by C<regbranch()> to 416C<reg()>. This flag permits patterns such as C<(?i)+> to be detected as 417errors (I<Quantifier follows nothing in regex; marked by <-- HERE in m/(?i)+ 418<-- HERE />). 419 420Another complication is that the representation used for the program differs 421if it needs to store Unicode, but it's not always possible to know for sure 422whether it does until midway through parsing. The Unicode representation for 423the program is larger, and cannot be matched as efficiently. (See L</Unicode 424and Localisation Support> below for more details as to why.) If the pattern 425contains literal Unicode, it's obvious that the program needs to store 426Unicode. Otherwise, the parser optimistically assumes that the more 427efficient representation can be used, and starts sizing on this basis. 428However, if it then encounters something in the pattern which must be stored 429as Unicode, such as an C<\x{...}> escape sequence representing a character 430literal, then this means that all previously calculated sizes need to be 431redone, using values appropriate for the Unicode representation. This 432is another instance where the parsing needs to be restarted, and it can 433and is done immediately. The function returns failure, and sets the 434flag C<RESTART_UTF8> (encapsulated by using the macro C<REQUIRE_UTF8>). 435This restart request is propagated up the call chain in a similar 436fashion, until it is "caught" in C<Perl_re_op_compile()>, which marks 437the pattern as containing Unicode, and restarts the sizing pass. It is 438also possible for constructions within run-time code blocks to turn out 439to need Unicode representation., which is signalled by 440C<S_compile_runtime_code()> returning false to C<Perl_re_op_compile()>. 441 442The restart was previously implemented using a C<longjmp> in C<regatom()> 443back to a C<setjmp> in C<Perl_re_op_compile()>, but this proved to be 444problematic as the latter is a large function containing many automatic 445variables, which interact badly with the emergent control flow of C<setjmp>. 446 447=head3 Debug Output 448 449Starting in the 5.9.x development version of perl you can C<< use re 450Debug => 'PARSE' >> to see some trace information about the parse 451process. We will start with some simple patterns and build up to more 452complex patterns. 453 454So when we parse C</foo/> we see something like the following table. The 455left shows what is being parsed, and the number indicates where the next regop 456would go. The stuff on the right is the trace output of the graph. The 457names are chosen to be short to make it less dense on the screen. 'tsdy' 458is a special form of C<regtail()> which does some extra analysis. 459 460 >foo< 1 reg 461 brnc 462 piec 463 atom 464 >< 4 tsdy~ EXACT <foo> (EXACT) (1) 465 ~ attach to END (3) offset to 2 466 467The resulting program then looks like: 468 469 1: EXACT <foo>(3) 470 3: END(0) 471 472As you can see, even though we parsed out a branch and a piece, it was ultimately 473only an atom. The final program shows us how things work. We have an C<EXACT> regop, 474followed by an C<END> regop. The number in parens indicates where the C<regnext> of 475the node goes. The C<regnext> of an C<END> regop is unused, as C<END> regops mean 476we have successfully matched. The number on the left indicates the position of 477the regop in the regnode array. 478 479Now let's try a harder pattern. We will add a quantifier, so now we have the pattern 480C</foo+/>. We will see that C<regbranch()> calls C<regpiece()> twice. 481 482 >foo+< 1 reg 483 brnc 484 piec 485 atom 486 >o+< 3 piec 487 atom 488 >< 6 tail~ EXACT <fo> (1) 489 7 tsdy~ EXACT <fo> (EXACT) (1) 490 ~ PLUS (END) (3) 491 ~ attach to END (6) offset to 3 492 493And we end up with the program: 494 495 1: EXACT <fo>(3) 496 3: PLUS(6) 497 4: EXACT <o>(0) 498 6: END(0) 499 500Now we have a special case. The C<EXACT> regop has a C<regnext> of 0. This is 501because if it matches it should try to match itself again. The C<PLUS> regop 502handles the actual failure of the C<EXACT> regop and acts appropriately (going 503to regnode 6 if the C<EXACT> matched at least once, or failing if it didn't). 504 505Now for something much more complex: C</x(?:foo*|b[a][rR])(foo|bar)$/> 506 507 >x(?:foo*|b... 1 reg 508 brnc 509 piec 510 atom 511 >(?:foo*|b[... 3 piec 512 atom 513 >?:foo*|b[a... reg 514 >foo*|b[a][... brnc 515 piec 516 atom 517 >o*|b[a][rR... 5 piec 518 atom 519 >|b[a][rR])... 8 tail~ EXACT <fo> (3) 520 >b[a][rR])(... 9 brnc 521 10 piec 522 atom 523 >[a][rR])(f... 12 piec 524 atom 525 >a][rR])(fo... clas 526 >[rR])(foo|... 14 tail~ EXACT <b> (10) 527 piec 528 atom 529 >rR])(foo|b... clas 530 >)(foo|bar)... 25 tail~ EXACT <a> (12) 531 tail~ BRANCH (3) 532 26 tsdy~ BRANCH (END) (9) 533 ~ attach to TAIL (25) offset to 16 534 tsdy~ EXACT <fo> (EXACT) (4) 535 ~ STAR (END) (6) 536 ~ attach to TAIL (25) offset to 19 537 tsdy~ EXACT <b> (EXACT) (10) 538 ~ EXACT <a> (EXACT) (12) 539 ~ ANYOF[Rr] (END) (14) 540 ~ attach to TAIL (25) offset to 11 541 >(foo|bar)$< tail~ EXACT <x> (1) 542 piec 543 atom 544 >foo|bar)$< reg 545 28 brnc 546 piec 547 atom 548 >|bar)$< 31 tail~ OPEN1 (26) 549 >bar)$< brnc 550 32 piec 551 atom 552 >)$< 34 tail~ BRANCH (28) 553 36 tsdy~ BRANCH (END) (31) 554 ~ attach to CLOSE1 (34) offset to 3 555 tsdy~ EXACT <foo> (EXACT) (29) 556 ~ attach to CLOSE1 (34) offset to 5 557 tsdy~ EXACT <bar> (EXACT) (32) 558 ~ attach to CLOSE1 (34) offset to 2 559 >$< tail~ BRANCH (3) 560 ~ BRANCH (9) 561 ~ TAIL (25) 562 piec 563 atom 564 >< 37 tail~ OPEN1 (26) 565 ~ BRANCH (28) 566 ~ BRANCH (31) 567 ~ CLOSE1 (34) 568 38 tsdy~ EXACT <x> (EXACT) (1) 569 ~ BRANCH (END) (3) 570 ~ BRANCH (END) (9) 571 ~ TAIL (END) (25) 572 ~ OPEN1 (END) (26) 573 ~ BRANCH (END) (28) 574 ~ BRANCH (END) (31) 575 ~ CLOSE1 (END) (34) 576 ~ EOL (END) (36) 577 ~ attach to END (37) offset to 1 578 579Resulting in the program 580 581 1: EXACT <x>(3) 582 3: BRANCH(9) 583 4: EXACT <fo>(6) 584 6: STAR(26) 585 7: EXACT <o>(0) 586 9: BRANCH(25) 587 10: EXACT <ba>(14) 588 12: OPTIMIZED (2 nodes) 589 14: ANYOF[Rr](26) 590 25: TAIL(26) 591 26: OPEN1(28) 592 28: TRIE-EXACT(34) 593 [StS:1 Wds:2 Cs:6 Uq:5 #Sts:7 Mn:3 Mx:3 Stcls:bf] 594 <foo> 595 <bar> 596 30: OPTIMIZED (4 nodes) 597 34: CLOSE1(36) 598 36: EOL(37) 599 37: END(0) 600 601Here we can see a much more complex program, with various optimisations in 602play. At regnode 10 we see an example where a character class with only 603one character in it was turned into an C<EXACT> node. We can also see where 604an entire alternation was turned into a C<TRIE-EXACT> node. As a consequence, 605some of the regnodes have been marked as optimised away. We can see that 606the C<$> symbol has been converted into an C<EOL> regop, a special piece of 607code that looks for C<\n> or the end of the string. 608 609The next pointer for C<BRANCH>es is interesting in that it points at where 610execution should go if the branch fails. When executing, if the engine 611tries to traverse from a branch to a C<regnext> that isn't a branch then 612the engine will know that the entire set of branches has failed. 613 614=head3 Peep-hole Optimisation and Analysis 615 616The regular expression engine can be a weighty tool to wield. On long 617strings and complex patterns it can end up having to do a lot of work 618to find a match, and even more to decide that no match is possible. 619Consider a situation like the following pattern. 620 621 'ababababababababababab' =~ /(a|b)*z/ 622 623The C<(a|b)*> part can match at every char in the string, and then fail 624every time because there is no C<z> in the string. So obviously we can 625avoid using the regex engine unless there is a C<z> in the string. 626Likewise in a pattern like: 627 628 /foo(\w+)bar/ 629 630In this case we know that the string must contain a C<foo> which must be 631followed by C<bar>. We can use Fast Boyer-Moore matching as implemented 632in C<fbm_instr()> to find the location of these strings. If they don't exist 633then we don't need to resort to the much more expensive regex engine. 634Even better, if they do exist then we can use their positions to 635reduce the search space that the regex engine needs to cover to determine 636if the entire pattern matches. 637 638There are various aspects of the pattern that can be used to facilitate 639optimisations along these lines: 640 641=over 5 642 643=item * anchored fixed strings 644 645=item * floating fixed strings 646 647=item * minimum and maximum length requirements 648 649=item * start class 650 651=item * Beginning/End of line positions 652 653=back 654 655Another form of optimisation that can occur is the post-parse "peep-hole" 656optimisation, where inefficient constructs are replaced by more efficient 657constructs. The C<TAIL> regops which are used during parsing to mark the end 658of branches and the end of groups are examples of this. These regops are used 659as place-holders during construction and "always match" so they can be 660"optimised away" by making the things that point to the C<TAIL> point to the 661thing that C<TAIL> points to, thus "skipping" the node. 662 663Another optimisation that can occur is that of "C<EXACT> merging" which is 664where two consecutive C<EXACT> nodes are merged into a single 665regop. An even more aggressive form of this is that a branch 666sequence of the form C<EXACT BRANCH ... EXACT> can be converted into a 667C<TRIE-EXACT> regop. 668 669All of this occurs in the routine C<study_chunk()> which uses a special 670structure C<scan_data_t> to store the analysis that it has performed, and 671does the "peep-hole" optimisations as it goes. 672 673The code involved in C<study_chunk()> is extremely cryptic. Be careful. :-) 674 675=head2 Execution 676 677Execution of a regex generally involves two phases, the first being 678finding the start point in the string where we should match from, 679and the second being running the regop interpreter. 680 681If we can tell that there is no valid start point then we don't bother running 682the interpreter at all. Likewise, if we know from the analysis phase that we 683cannot detect a short-cut to the start position, we go straight to the 684interpreter. 685 686The two entry points are C<re_intuit_start()> and C<pregexec()>. These routines 687have a somewhat incestuous relationship with overlap between their functions, 688and C<pregexec()> may even call C<re_intuit_start()> on its own. Nevertheless 689other parts of the perl source code may call into either, or both. 690 691Execution of the interpreter itself used to be recursive, but thanks to the 692efforts of Dave Mitchell in the 5.9.x development track, that has changed: now an 693internal stack is maintained on the heap and the routine is fully 694iterative. This can make it tricky as the code is quite conservative 695about what state it stores, with the result that two consecutive lines in the 696code can actually be running in totally different contexts due to the 697simulated recursion. 698 699=head3 Start position and no-match optimisations 700 701C<re_intuit_start()> is responsible for handling start points and no-match 702optimisations as determined by the results of the analysis done by 703C<study_chunk()> (and described in L</Peep-hole Optimisation and Analysis>). 704 705The basic structure of this routine is to try to find the start- and/or 706end-points of where the pattern could match, and to ensure that the string 707is long enough to match the pattern. It tries to use more efficient 708methods over less efficient methods and may involve considerable 709cross-checking of constraints to find the place in the string that matches. 710For instance it may try to determine that a given fixed string must be 711not only present but a certain number of chars before the end of the 712string, or whatever. 713 714It calls several other routines, such as C<fbm_instr()> which does 715Fast Boyer Moore matching and C<find_byclass()> which is responsible for 716finding the start using the first mandatory regop in the program. 717 718When the optimisation criteria have been satisfied, C<reg_try()> is called 719to perform the match. 720 721=head3 Program execution 722 723C<pregexec()> is the main entry point for running a regex. It contains 724support for initialising the regex interpreter's state, running 725C<re_intuit_start()> if needed, and running the interpreter on the string 726from various start positions as needed. When it is necessary to use 727the regex interpreter C<pregexec()> calls C<regtry()>. 728 729C<regtry()> is the entry point into the regex interpreter. It expects 730as arguments a pointer to a C<regmatch_info> structure and a pointer to 731a string. It returns an integer 1 for success and a 0 for failure. 732It is basically a set-up wrapper around C<regmatch()>. 733 734C<regmatch> is the main "recursive loop" of the interpreter. It is 735basically a giant switch statement that implements a state machine, where 736the possible states are the regops themselves, plus a number of additional 737intermediate and failure states. A few of the states are implemented as 738subroutines but the bulk are inline code. 739 740=head1 MISCELLANEOUS 741 742=head2 Unicode and Localisation Support 743 744When dealing with strings containing characters that cannot be represented 745using an eight-bit character set, perl uses an internal representation 746that is a permissive version of Unicode's UTF-8 encoding[2]. This uses single 747bytes to represent characters from the ASCII character set, and sequences 748of two or more bytes for all other characters. (See L<perlunitut> 749for more information about the relationship between UTF-8 and perl's 750encoding, utf8. The difference isn't important for this discussion.) 751 752No matter how you look at it, Unicode support is going to be a pain in a 753regex engine. Tricks that might be fine when you have 256 possible 754characters often won't scale to handle the size of the UTF-8 character 755set. Things you can take for granted with ASCII may not be true with 756Unicode. For instance, in ASCII, it is safe to assume that 757C<sizeof(char1) == sizeof(char2)>, but in UTF-8 it isn't. Unicode case folding is 758vastly more complex than the simple rules of ASCII, and even when not 759using Unicode but only localised single byte encodings, things can get 760tricky (for example, B<LATIN SMALL LETTER SHARP S> (U+00DF, E<szlig>) 761should match 'SS' in localised case-insensitive matching). 762 763Making things worse is that UTF-8 support was a later addition to the 764regex engine (as it was to perl) and this necessarily made things a lot 765more complicated. Obviously it is easier to design a regex engine with 766Unicode support in mind from the beginning than it is to retrofit it to 767one that wasn't. 768 769Nearly all regops that involve looking at the input string have 770two cases, one for UTF-8, and one not. In fact, it's often more complex 771than that, as the pattern may be UTF-8 as well. 772 773Care must be taken when making changes to make sure that you handle 774UTF-8 properly, both at compile time and at execution time, including 775when the string and pattern are mismatched. 776 777=head2 Base Structures 778 779The C<regexp> structure described in L<perlreapi> is common to all 780regex engines. Two of its fields are intended for the private use 781of the regex engine that compiled the pattern. These are the 782C<intflags> and pprivate members. The C<pprivate> is a void pointer to 783an arbitrary structure whose use and management is the responsibility 784of the compiling engine. perl will never modify either of these 785values. In the case of the stock engine the structure pointed to by 786C<pprivate> is called C<regexp_internal>. 787 788Its C<pprivate> and C<intflags> fields contain data 789specific to each engine. 790 791There are two structures used to store a compiled regular expression. 792One, the C<regexp> structure described in L<perlreapi> is populated by 793the engine currently being. used and some of its fields read by perl to 794implement things such as the stringification of C<qr//>. 795 796 797The other structure is pointed to by the C<regexp> struct's 798C<pprivate> and is in addition to C<intflags> in the same struct 799considered to be the property of the regex engine which compiled the 800regular expression; 801 802The regexp structure contains all the data that perl needs to be aware of 803to properly work with the regular expression. It includes data about 804optimisations that perl can use to determine if the regex engine should 805really be used, and various other control info that is needed to properly 806execute patterns in various contexts such as is the pattern anchored in 807some way, or what flags were used during the compile, or whether the 808program contains special constructs that perl needs to be aware of. 809 810In addition it contains two fields that are intended for the private use 811of the regex engine that compiled the pattern. These are the C<intflags> 812and pprivate members. The C<pprivate> is a void pointer to an arbitrary 813structure whose use and management is the responsibility of the compiling 814engine. perl will never modify either of these values. 815 816As mentioned earlier, in the case of the default engines, the C<pprivate> 817will be a pointer to a regexp_internal structure which holds the compiled 818program and any additional data that is private to the regex engine 819implementation. 820 821=head3 Perl's C<pprivate> structure 822 823The following structure is used as the C<pprivate> struct by perl's 824regex engine. Since it is specific to perl it is only of curiosity 825value to other engine implementations. 826 827 typedef struct regexp_internal { 828 U32 *offsets; /* offset annotations 20001228 MJD 829 * data about mapping the program to 830 * the string*/ 831 regnode *regstclass; /* Optional startclass as identified or 832 * constructed by the optimiser */ 833 struct reg_data *data; /* Additional miscellaneous data used 834 * by the program. Used to make it 835 * easier to clone and free arbitrary 836 * data that the regops need. Often the 837 * ARG field of a regop is an index 838 * into this structure */ 839 regnode program[1]; /* Unwarranted chumminess with 840 * compiler. */ 841 } regexp_internal; 842 843=over 5 844 845=item C<offsets> 846 847Offsets holds a mapping of offset in the C<program> 848to offset in the C<precomp> string. This is only used by ActiveState's 849visual regex debugger. 850 851=item C<regstclass> 852 853Special regop that is used by C<re_intuit_start()> to check if a pattern 854can match at a certain position. For instance if the regex engine knows 855that the pattern must start with a 'Z' then it can scan the string until 856it finds one and then launch the regex engine from there. The routine 857that handles this is called C<find_by_class()>. Sometimes this field 858points at a regop embedded in the program, and sometimes it points at 859an independent synthetic regop that has been constructed by the optimiser. 860 861=item C<data> 862 863This field points at a C<reg_data> structure, which is defined as follows 864 865 struct reg_data { 866 U32 count; 867 U8 *what; 868 void* data[1]; 869 }; 870 871This structure is used for handling data structures that the regex engine 872needs to handle specially during a clone or free operation on the compiled 873product. Each element in the data array has a corresponding element in the 874what array. During compilation regops that need special structures stored 875will add an element to each array using the add_data() routine and then store 876the index in the regop. 877 878=item C<program> 879 880Compiled program. Inlined into the structure so the entire struct can be 881treated as a single blob. 882 883=back 884 885=head1 SEE ALSO 886 887L<perlreapi> 888 889L<perlre> 890 891L<perlunitut> 892 893=head1 AUTHOR 894 895by Yves Orton, 2006. 896 897With excerpts from Perl, and contributions and suggestions from 898Ronald J. Kimball, Dave Mitchell, Dominic Dunlop, Mark Jason Dominus, 899Stephen McCamant, and David Landgren. 900 901Now maintained by Perl 5 Porters. 902 903=head1 LICENCE 904 905Same terms as Perl. 906 907=head1 REFERENCES 908 909[1] L<https://perl.plover.com/Rx/paper/> 910 911[2] L<https://www.unicode.org/> 912 913=cut 914