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