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