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