1 Technical Notes about PCRE2
2 ---------------------------
4 These are very rough technical notes that record potentially useful information
5 about PCRE2 internals. PCRE2 is a library based on the original PCRE library,
6 but with a revised (and incompatible) API. To avoid confusion, the original
7 library is referred to as PCRE1 below. For information about testing PCRE2, see
8 the pcre2test documentation and the comment at the head of the RunTest file.
10 PCRE1 releases were up to 8.3x when PCRE2 was developed, and later bug fix
11 releases remain in the 8.xx series. PCRE2 releases started at 10.00 to avoid
18 Many years ago I implemented some regular expression functions to an algorithm
19 suggested by Martin Richards. The rather simple patterns were not Unix-like in
20 form, and were quite restricted in what they could do by comparison with Perl.
21 The interesting part about the algorithm was that the amount of space required
22 to hold the compiled form of an expression was known in advance. The code to
23 apply an expression did not operate by backtracking, as the original Henry
24 Spencer code and current PCRE2 and Perl code does, but instead checked all
25 possibilities simultaneously by keeping a list of current states and checking
26 all of them as it advanced through the subject string. In the terminology of
27 Jeffrey Friedl's book, it was a "DFA algorithm", though it was not a
28 traditional Finite State Machine (FSM). When the pattern was all used up, all
29 remaining states were possible matches, and the one matching the longest subset
30 of the subject string was chosen. This did not necessarily maximize the
31 individual wild portions of the pattern, as is expected in Unix and Perl-style
38 By contrast, the code originally written by Henry Spencer (which was
39 subsequently heavily modified for Perl) compiles the expression twice: once in
40 a dummy mode in order to find out how much store will be needed, and then for
41 real. (The Perl version probably doesn't do this any more; I'm talking about
42 the original library.) The execution function operates by backtracking and
43 maximizing (or, optionally, minimizing, in Perl) the amount of the subject that
44 matches individual wild portions of the pattern. This is an "NFA algorithm" in
48 OK, here's the real stuff
49 -------------------------
51 For the set of functions that formed the original PCRE1 library in 1997 (which
52 are unrelated to those mentioned above), I tried at first to invent an
53 algorithm that used an amount of store bounded by a multiple of the number of
54 characters in the pattern, to save on compiling time. However, because of the
55 greater complexity in Perl regular expressions, I couldn't do this, even though
56 the then current Perl 5.004 patterns were much simpler than those supported
57 nowadays. In any case, a first pass through the pattern is helpful for other
61 Support for 16-bit and 32-bit data strings
62 -------------------------------------------
64 The PCRE2 library can be compiled in any combination of 8-bit, 16-bit or 32-bit
65 modes, creating up to three different libraries. In the description that
66 follows, the word "short" is used for a 16-bit data quantity, and the phrase
67 "code unit" is used for a quantity that is a byte in 8-bit mode, a short in
68 16-bit mode and a 32-bit word in 32-bit mode. The names of PCRE2 functions are
69 given in generic form, without the _8, _16, or _32 suffix.
72 Computing the memory requirement: how it was
73 --------------------------------------------
75 Up to and including release 6.7, PCRE1 worked by running a very degenerate
76 first pass to calculate a maximum memory requirement, and then a second pass to
77 do the real compile - which might use a bit less than the predicted amount of
78 memory. The idea was that this would turn out faster than the Henry Spencer
79 code because the first pass is degenerate and the second pass can just store
80 stuff straight into memory, which it knows is big enough.
83 Computing the memory requirement: how it is
84 -------------------------------------------
86 By the time I was working on a potential 6.8 release, the degenerate first pass
87 had become very complicated and hard to maintain. Indeed one of the early
88 things I did for 6.8 was to fix Yet Another Bug in the memory computation. Then
89 I had a flash of inspiration as to how I could run the real compile function in
90 a "fake" mode that enables it to compute how much memory it would need, while
91 in most cases only ever using a small amount of working memory, and without too
92 many tests of the mode that might slow it down. So I refactored the compiling
93 functions to work this way. This got rid of about 600 lines of source and made
94 further maintenance and development easier. As this was such a major change, I
95 never released 6.8, instead upping the number to 7.0 (other quite major changes
96 were also present in the 7.0 release).
98 A side effect of this work was that the previous limit of 200 on the nesting
99 depth of parentheses was removed. However, there was a downside: compiling ran
100 more slowly than before (30% or more, depending on the pattern) because it now
101 did a full analysis of the pattern. My hope was that this would not be a big
102 issue, and in the event, nobody has commented on it.
104 At release 8.34, a limit on the nesting depth of parentheses was re-introduced
105 (default 250, settable at build time) so as to put a limit on the amount of
106 system stack used by the compile function, which uses recursive function calls
107 for nested parenthesized groups. This is a safety feature for environments with
108 small stacks where the patterns are provided by users.
111 Yet another pattern scan
112 ------------------------
114 History repeated itself for PCRE2 release 10.20. A number of bugs relating to
115 named subpatterns had been discovered by fuzzers. Most of these were related to
116 the handling of forward references when it was not known if the named group was
117 unique. (References to non-unique names use a different opcode and more
118 memory.) The use of duplicate group numbers (the (?| facility) also caused
121 To get around these problems I adopted a new approach by adding a third pass
122 over the pattern (really a "pre-pass"), which did nothing other than identify
123 all the named subpatterns and their corresponding group numbers. This means
124 that the actual compile (both the memory-computing dummy run and the real
125 compile) has full knowledge of group names and numbers throughout. Several
126 dozen lines of messy code were eliminated, though the new pre-pass was not
127 short. In particular, parsing and skipping over [] classes is complicated.
129 While working on 10.22 I realized that I could simplify yet again by moving
130 more of the parsing into the pre-pass, thus avoiding doing it in two places, so
131 after 10.22 was released, the code underwent yet another big refactoring. This
132 is how it is from 10.23 onwards:
134 The function called parse_regex() scans the pattern characters, parsing them
135 into literal data and meta characters. It converts escapes such as \x{123}
136 into literals, handles \Q...\E, and skips over comments and non-significant
137 white space. The result of the scanning is put into a vector of 32-bit unsigned
138 integers. Values less than 0x80000000 are literal data. Higher values represent
139 meta-characters. The top 16-bits of such values identify the meta-character,
140 and these are given names such as META_CAPTURE. The lower 16-bits are available
141 for data, for example, the capturing group number. The only situation in which
142 literal data values greater than 0x7fffffff can appear is when the 32-bit
143 library is running in non-UTF mode. This is handled by having a special
144 meta-character that is followed by the 32-bit data value.
146 The size of the parsed pattern vector, when auto-callouts are not enabled, is
147 bounded by the length of the pattern (with one exception). The code is written
148 so that each item in the pattern uses no more vector elements than the number
149 of code units in the item itself. The exception is the aforementioned large
150 32-bit number handling. For this reason, 32-bit non-UTF patterns are scanned in
151 advance to check for such values. When auto-callouts are enabled, the generous
152 assumption is made that there will be a callout for each pattern code unit
153 (which of course is only actually true if all code units are literals) plus one
154 at the end. There is a default parsed pattern vector on the system stack, but
155 if this is not big enough, heap memory is used.
157 As before, the actual compiling function is run twice, the first time to
158 determine the amount of memory needed for the final compiled pattern. It
159 now processes the parsed pattern vector, not the pattern itself, although some
160 of the parsed items refer to strings in the pattern - for example, group
161 names. As escapes and comments have already been processed, the code is a bit
164 Most errors can be diagnosed during the parsing scan. For those that cannot
165 (for example, "lookbehind assertion is not fixed length"), the parsed code
166 contains offsets into the pattern so that the actual compiling code can
167 report where errors are.
170 The elements of the parsed pattern vector
171 -----------------------------------------
173 The word "offset" below means a code unit offset into the pattern. When
174 PCRE2_SIZE (which is usually size_t) is no bigger than uint32_t, an offset is
175 stored in a single parsed pattern element. Otherwise (typically on 64-bit
176 systems) it occupies two elements. The following meta items occupy just one
177 element, with no data:
179 META_ACCEPT (*ACCEPT)
181 META_ASTERISK_PLUS *+
182 META_ASTERISK_QUERY *?
183 META_ATOMIC (?> start of atomic group
184 META_CIRCUMFLEX ^ metacharacter
185 META_CLASS [ start of non-empty class
186 META_CLASS_EMPTY [] empty class - only with PCRE2_ALLOW_EMPTY_CLASS
187 META_CLASS_EMPTY_NOT [^] negative empty class - ditto
188 META_CLASS_END ] end of non-empty class
189 META_CLASS_NOT [^ start non-empty negative class
190 META_COMMIT (*COMMIT)
191 META_COND_ASSERT (?(?assertion)
192 META_DOLLAR $ metacharacter
193 META_DOT . metacharacter
194 META_END End of pattern (this value is 0x80000000)
196 META_KET ) closing parenthesis
197 META_LOOKAHEAD (?= start of lookahead
198 META_LOOKAHEADNOT (?! start of negative lookahead
199 META_NOCAPTURE (?: no capture parens
203 META_PRUNE (*PRUNE) - no argument
207 META_RANGE_ESCAPED hyphen in class range with at least one escape
208 META_RANGE_LITERAL hyphen in class range defined literally
209 META_SKIP (*SKIP) - no argument
210 META_THEN (*THEN) - no argument
212 The two RANGE values occur only in character classes. They are positioned
213 between two literals that define the start and end of the range. In an EBCDIC
214 evironment it is necessary to know whether either of the range values was
215 specified as an escape. In an ASCII/Unicode environment the distinction is not
218 The following have data in the lower 16 bits, and may be followed by other data
221 META_ALT | alternation
222 META_BACKREF back reference
223 META_CAPTURE start of capturing group
224 META_ESCAPE non-literal escape sequence
225 META_RECURSE recursion call
227 If the data for META_ALT is non-zero, it is inside a lookbehind, and the data
228 is the length of its branch, for which OP_REVERSE must be generated.
230 META_BACKREF, META_CAPTURE, and META_RECURSE have the capture group number as
231 their data in the lower 16 bits of the element.
233 META_BACKREF is followed by an offset if the back reference group number is 10
234 or more. The offsets of the first ocurrences of references to groups whose
235 numbers are less than 10 are put in cb->small_ref_offset[] (only the first
236 occurrence is useful). On 64-bit systems this avoids using more than two parsed
237 pattern elements for items such as \3. The offset is used when an error occurs
238 because the reference is to a non-existent group.
240 META_RECURSE is always followed by an offset, for use in error messages.
242 META_ESCAPE has an ESC_xxx value as its data. For ESC_P and ESC_p, the next
243 element contains the 16-bit type and data property values, packed together.
244 ESC_g and ESC_k are used only for named references - numerical ones are turned
245 into META_RECURSE or META_BACKREF as appropriate. ESC_g and ESC_k are followed
246 by a length and an offset into the pattern to specify the name.
248 The following have one data item that follows in the next vector element:
250 META_BIGVALUE Next is a literal >= META_END
251 META_OPTIONS (?i) and friends (data is new option bits)
252 META_POSIX POSIX class item (data identifies the class)
253 META_POSIX_NEG negative POSIX class item (ditto)
255 The following are followed by a length element, then a number of character code
256 values (which should match with the length):
258 META_MARK (*MARK:xxxx)
259 META_COMMIT_ARG )*COMMIT:xxxx)
260 META_PRUNE_ARG (*PRUNE:xxx)
261 META_SKIP_ARG (*SKIP:xxxx)
262 META_THEN_ARG (*THEN:xxxx)
264 The following are followed by a length element, then an offset in the pattern
265 that identifies the name:
267 META_COND_NAME (?(<name>) or (?('name') or (?(name)
268 META_COND_RNAME (?(R&name)
269 META_COND_RNUMBER (?(Rdigits)
270 META_RECURSE_BYNAME (?&name)
271 META_BACKREF_BYNAME \k'name'
273 META_COND_RNUMBER is used for names that start with R and continue with digits,
274 because this is an ambiguous case. It could be a back reference to a group with
275 that name, or it could be a recursion test on a numbered group.
277 This one is followed by an offset, for use in error messages, then a number:
279 META_COND_NUMBER (?([+-]digits)
281 The following is followed just by an offset, for use in error messages:
283 META_COND_DEFINE (?(DEFINE)
285 The following are also followed just by an offset, but also the lower 16 bits
286 of the main word contain the length of the first branch of the lookbehind
287 group; this is used when generating OP_REVERSE for that branch.
290 META_LOOKBEHINDNOT (?<!
292 The following are followed by two elements, the minimum and maximum. Repeat
293 values are limited to 65535 (MAX_REPEAT). A maximum value of "unlimited" is
294 represented by UNLIMITED_REPEAT, which is bigger than MAX_REPEAT:
296 META_MINMAX {n,m} repeat
297 META_MINMAX_PLUS {n,m}+ repeat
298 META_MINMAX_QUERY {n,m}? repeat
300 This one is followed by three elements. The first is 0 for '>' and 1 for '>=';
301 the next two are the major and minor numbers:
303 META_COND_VERSION (?(VERSION<op>x.y)
305 Callouts are converted into one of two items:
307 META_CALLOUT_NUMBER (?C with numerical argument
308 META_CALLOUT_STRING (?C with string argument
310 In both cases, the next two elements contain the offset and length of the next
311 item in the pattern. Then there is either one callout number, or a length and
312 an offset for the string argument. The length includes both delimiters.
315 Traditional matching function
316 -----------------------------
318 The "traditional", and original, matching function is called pcre2_match(), and
319 it implements an NFA algorithm, similar to the original Henry Spencer algorithm
320 and the way that Perl works. This is not surprising, since it is intended to be
321 as compatible with Perl as possible. This is the function most users of PCRE2
322 will use most of the time. If PCRE2 is compiled with just-in-time (JIT)
323 support, and studying a compiled pattern with JIT is successful, the JIT code
324 is run instead of the normal pcre2_match() code, but the result is the same.
327 Supplementary matching function
328 -------------------------------
330 There is also a supplementary matching function called pcre2_dfa_match(). This
331 implements a DFA matching algorithm that searches simultaneously for all
332 possible matches that start at one point in the subject string. (Going back to
333 my roots: see Historical Note 1 above.) This function intreprets the same
334 compiled pattern data as pcre2_match(); however, not all the facilities are
335 available, and those that are do not always work in quite the same way. See the
336 user documentation for details.
338 The algorithm that is used for pcre2_dfa_match() is not a traditional FSM,
339 because it may have a number of states active at one time. More work would be
340 needed at compile time to produce a traditional FSM where only one state is
341 ever active at once. I believe some other regex matchers work this way. JIT
342 support is not available for this kind of matching.
348 The /i, /m, or /s options (PCRE2_CASELESS, PCRE2_MULTILINE, PCRE2_DOTALL, and
349 others) may be changed in the middle of patterns by items such as (?i). Their
350 processing is handled entirely at compile time by generating different opcodes
351 for the different settings. The runtime functions do not need to keep track of
354 PCRE2_DUPNAMES, PCRE2_EXTENDED, PCRE2_EXTENDED_MORE, and PCRE2_NO_AUTO_CAPTURE
355 are tracked and processed during the parsing pre-pass. The others are handled
356 from META_OPTIONS items during the main compile phase.
359 Format of compiled patterns
360 ---------------------------
362 The compiled form of a pattern is a vector of unsigned code units (bytes in
363 8-bit mode, shorts in 16-bit mode, 32-bit words in 32-bit mode), containing
364 items of variable length. The first code unit in an item contains an opcode,
365 and the length of the item is either implicit in the opcode or contained in the
366 data that follows it.
368 In many cases listed below, LINK_SIZE data values are specified for offsets
369 within the compiled pattern. LINK_SIZE always specifies a number of bytes. The
370 default value for LINK_SIZE is 2, except for the 32-bit library, where it can
371 only be 4. The 8-bit library can be compiled to used 3-byte or 4-byte values,
372 and the 16-bit library can be compiled to use 4-byte values, though this
373 impairs performance. Specifing a LINK_SIZE larger than 2 for these libraries is
374 necessary only when patterns whose compiled length is greater than 65535 code
375 units are going to be processed. When a LINK_SIZE value uses more than one code
376 unit, the most significant unit is first.
378 In this description, we assume the "normal" compilation options. Data values
379 that are counts (e.g. quantifiers) are always two bytes long in 8-bit mode
380 (most significant byte first), and one code unit in 16-bit and 32-bit modes.
383 Opcodes with no following data
384 ------------------------------
386 These items are all just one unit long:
388 OP_END end of pattern
389 OP_ANY match any one character other than newline
390 OP_ALLANY match any one character, including newline
391 OP_ANYBYTE match any single code unit, even in UTF-8/16 mode
392 OP_SOD match start of data: \A
393 OP_SOM, start of match (subject + offset): \G
394 OP_SET_SOM, set start of match (\K)
395 OP_CIRC ^ (start of data)
396 OP_CIRCM ^ multiline mode (start of data or after newline)
397 OP_NOT_WORD_BOUNDARY \W
409 OP_EODN match end of data or newline at end: \Z
410 OP_EOD match end of data: \z
411 OP_DOLL $ (end of data, or before final newline)
412 OP_DOLLM $ multiline mode (end of data or before newline)
413 OP_EXTUNI match an extended Unicode grapheme cluster
414 OP_ANYNL match any Unicode newline sequence
417 OP_ACCEPT ) These are Perl 5.10's "backtracking control
418 OP_COMMIT ) verbs". If OP_ACCEPT is inside capturing
419 OP_FAIL ) parentheses, it may be preceded by one or more
420 OP_PRUNE ) OP_CLOSE, each followed by a number that
421 OP_SKIP ) indicates which parentheses must be closed.
424 OP_ASSERT_ACCEPT is used when (*ACCEPT) is encountered within an assertion.
425 This ends the assertion, not the entire pattern match. The assertion (?!) is
426 always optimized to OP_FAIL.
428 OP_ALLANY is used for '.' when PCRE2_DOTALL is set. It is also used for \C in
429 non-UTF modes and in UTF-32 mode (since one code unit still equals one
430 character). Another use is for [^] when empty classes are permitted
431 (PCRE2_ALLOW_EMPTY_CLASS is set).
434 Backtracking control verbs
435 --------------------------
437 Verbs with no arguments generate opcodes with no following data (as listed
438 in the section above).
440 (*MARK:NAME) generates OP_MARK followed by the mark name, preceded by a
441 length in one code unit, and followed by a binary zero. The name length is
442 limited by the size of the code unit.
444 (*ACCEPT:NAME) and (*FAIL:NAME) are compiled as (*MARK:NAME)(*ACCEPT) and
445 (*MARK:NAME)(*FAIL) respectively.
447 For (*COMMIT:NAME), (*PRUNE:NAME), (*SKIP:NAME), and (*THEN:NAME), the opcodes
448 OP_COMMIT_ARG, OP_PRUNE_ARG, OP_SKIP_ARG, and OP_THEN_ARG are used, with the
449 name following in the same format as for OP_MARK.
452 Matching literal characters
453 ---------------------------
455 The OP_CHAR opcode is followed by a single character that is to be matched
456 casefully. For caseless matching of characters that have at most two
457 case-equivalent code points, OP_CHARI is used. In UTF-8 or UTF-16 modes, the
458 character may be more than one code unit long. In UTF-32 mode, characters are
459 always exactly one code unit long.
461 If there is only one character in a character class, OP_CHAR or OP_CHARI is
462 used for a positive class, and OP_NOT or OP_NOTI for a negative one (that is,
463 for something like [^a]).
465 Caseless matching (positive or negative) of characters that have more than two
466 case-equivalent code points (which is possible only in UTF mode) is handled by
467 compiling a Unicode property item (see below), with the pseudo-property
468 PT_CLIST. The value of this property is an offset in a vector called
469 "ucd_caseless_sets" which identifies the start of a short list of equivalent
470 characters, terminated by the value NOTACHAR (0xffffffff).
473 Repeating single characters
474 ---------------------------
476 The common repeats (*, +, ?), when applied to a single character, use the
477 following opcodes, which come in caseful and caseless versions:
481 OP_MINSTAR OP_MINSTARI
482 OP_POSSTAR OP_POSSTARI
484 OP_MINPLUS OP_MINPLUSI
485 OP_POSPLUS OP_POSPLUSI
487 OP_MINQUERY OP_MINQUERYI
488 OP_POSQUERY OP_POSQUERYI
490 Each opcode is followed by the character that is to be repeated. In ASCII or
491 UTF-32 modes, these are two-code-unit items; in UTF-8 or UTF-16 modes, the
492 length is variable. Those with "MIN" in their names are the minimizing
493 versions. Those with "POS" in their names are possessive versions. Other kinds
494 of repeat make use of these opcodes:
498 OP_MINUPTO OP_MINUPTOI
499 OP_POSUPTO OP_POSUPTOI
502 Each of these is followed by a count and then the repeated character. The count
503 is two bytes long in 8-bit mode (most significant byte first), or one code unit
504 in 16-bit and 32-bit modes.
506 OP_UPTO matches from 0 to the given number. A repeat with a non-zero minimum
507 and a fixed maximum is coded as an OP_EXACT followed by an OP_UPTO (or
508 OP_MINUPTO or OPT_POSUPTO).
510 Another set of matching repeating opcodes (called OP_NOTSTAR, OP_NOTSTARI,
511 etc.) are used for repeated, negated, single-character classes such as [^a]*.
512 The normal single-character opcodes (OP_STAR, etc.) are used for repeated
513 positive single-character classes.
516 Repeating character types
517 -------------------------
519 Repeats of things like \d are done exactly as for single characters, except
520 that instead of a character, the opcode for the type (e.g. OP_DIGIT) is stored
521 in the next code unit. The opcodes are:
538 Match by Unicode property
539 -------------------------
541 OP_PROP and OP_NOTPROP are used for positive and negative matches of a
542 character by testing its Unicode property (the \p and \P escape sequences).
543 Each is followed by two code units that encode the desired property as a type
544 and a value. The types are a set of #defines of the form PT_xxx, and the values
545 are enumerations of the form ucp_xx, defined in the pcre2_ucp.h source file.
546 The value is relevant only for PT_GC (General Category), PT_PC (Particular
547 Category), PT_SC (Script), and the pseudo-property PT_CLIST, which is used to
548 identify a list of case-equivalent characters when there are three or more.
550 Repeats of these items use the OP_TYPESTAR etc. set of opcodes, followed by
551 three code units: OP_PROP or OP_NOTPROP, and then the desired property type and
558 If there is only one character in a class, OP_CHAR or OP_CHARI is used for a
559 positive class, and OP_NOT or OP_NOTI for a negative one (that is, for
560 something like [^a]), except when caselessly matching a character that has more
561 than two case-equivalent code points (which can happen only in UTF mode). In
562 this case a Unicode property item is used, as described above in "Matching
565 A set of repeating opcodes (called OP_NOTSTAR etc.) are used for repeated,
566 negated, single-character classes. The normal single-character opcodes
567 (OP_STAR, etc.) are used for repeated positive single-character classes.
569 When there is more than one character in a class, and all the code points are
570 less than 256, OP_CLASS is used for a positive class, and OP_NCLASS for a
571 negative one. In either case, the opcode is followed by a 32-byte (16-short,
572 8-word) bit map containing a 1 bit for every character that is acceptable. The
573 bits are counted from the least significant end of each unit. In caseless mode,
574 bits for both cases are set.
576 The reason for having both OP_CLASS and OP_NCLASS is so that, in UTF-8 and
577 16-bit and 32-bit modes, subject characters with values greater than 255 can be
578 handled correctly. For OP_CLASS they do not match, whereas for OP_NCLASS they
581 For classes containing characters with values greater than 255 or that contain
582 \p or \P, OP_XCLASS is used. It optionally uses a bit map if any acceptable
583 code points are less than 256, followed by a list of pairs (for a range) and/or
584 single characters and/or properties. In caseless mode, all equivalent
585 characters are explicitly listed.
587 OP_XCLASS is followed by a LINK_SIZE value containing the total length of the
588 opcode and its data. This is followed by a code unit containing flag bits:
589 XCL_NOT indicates that this is a negative class, and XCL_MAP indicates that a
590 bit map is present. There follows the bit map, if XCL_MAP is set, and then a
591 sequence of items coded as follows:
593 XCL_END marks the end of the list
594 XCL_SINGLE one character follows
595 XCL_RANGE two characters follow
596 XCL_PROP a Unicode property (type, value) follows
597 XCL_NOTPROP a Unicode property (type, value) follows
599 If a range starts with a code point less than 256 and ends with one greater
600 than 255, it is split into two ranges, with characters less than 256 being
601 indicated in the bit map, and the rest with XCL_RANGE.
603 When XCL_NOT is set, the bit map, if present, contains bits for characters that
604 are allowed (exactly as for OP_NCLASS), but the list of items that follow it
605 specifies characters and properties that are not allowed.
611 OP_REF (caseful) or OP_REFI (caseless) is followed by a count containing the
612 reference number when the reference is to a unique capturing group (either by
613 number or by name). When named groups are used, there may be more than one
614 group with the same name. In this case, a reference to such a group by name
615 generates OP_DNREF or OP_DNREFI. These are followed by two counts: the index
616 (not the byte offset) in the group name table of the first entry for the
617 required name, followed by the number of groups with the same name. The
618 matching code can then search for the first one that is set.
621 Repeating character classes and back references
622 -----------------------------------------------
624 Single-character classes are handled specially (see above). This section
625 applies to other classes and also to back references. In both cases, the repeat
626 information follows the base item. The matching code looks at the following
627 opcode to see if it is one of these:
642 All but the last three are single-code-unit items, with no data. The range
643 opcodes are followed by the minimum and maximum repeat counts.
646 Brackets and alternation
647 ------------------------
649 A pair of non-capturing round brackets is wrapped round each expression at
650 compile time, so alternation always happens in the context of brackets.
652 [Note for North Americans: "bracket" to some English speakers, including
653 myself, can be round, square, curly, or pointy. Hence this usage rather than
656 Non-capturing brackets use the opcode OP_BRA, capturing brackets use OP_CBRA. A
657 bracket opcode is followed by a LINK_SIZE value which gives the offset to the
658 next alternative OP_ALT or, if there aren't any branches, to the terminating
659 opcode. Each OP_ALT is followed by a LINK_SIZE value giving the offset to the
660 next one, or to the final opcode. For capturing brackets, the bracket number is
661 a count that immediately follows the offset.
663 There are several opcodes that mark the end of a subpattern group. OP_KET is
664 used for subpatterns that do not repeat indefinitely, OP_KETRMIN and
665 OP_KETRMAX are used for indefinite repetitions, minimally or maximally
666 respectively, and OP_KETRPOS for possessive repetitions (see below for more
667 details). All four are followed by a LINK_SIZE value giving (as a positive
668 number) the offset back to the matching bracket opcode.
670 If a subpattern is quantified such that it is permitted to match zero times, it
671 is preceded by one of OP_BRAZERO, OP_BRAMINZERO, or OP_SKIPZERO. These are
672 single-unit opcodes that tell the matcher that skipping the following
673 subpattern entirely is a valid match. In the case of the first two, not
674 skipping the pattern is also valid (greedy and non-greedy). The third is used
675 when a pattern has the quantifier {0,0}. It cannot be entirely discarded,
676 because it may be called as a subroutine from elsewhere in the pattern.
678 A subpattern with an indefinite maximum repetition is replicated in the
679 compiled data its minimum number of times (or once with OP_BRAZERO if the
680 minimum is zero), with the final copy terminating with OP_KETRMIN or OP_KETRMAX
683 A subpattern with a bounded maximum repetition is replicated in a nested
684 fashion up to the maximum number of times, with OP_BRAZERO or OP_BRAMINZERO
685 before each replication after the minimum, so that, for example, (abc){2,5} is
686 compiled as (abc)(abc)((abc)((abc)(abc)?)?)?, except that each bracketed group
689 When a repeated subpattern has an unbounded upper limit, it is checked to see
690 whether it could match an empty string. If this is the case, the opcode in the
691 final replication is changed to OP_SBRA or OP_SCBRA. This tells the matcher
692 that it needs to check for matching an empty string when it hits OP_KETRMIN or
693 OP_KETRMAX, and if so, to break the loop.
699 When a repeated group (capturing or non-capturing) is marked as possessive by
700 the "+" notation, e.g. (abc)++, different opcodes are used. Their names all
701 have POS on the end, e.g. OP_BRAPOS instead of OP_BRA and OP_SCBRAPOS instead
702 of OP_SCBRA. The end of such a group is marked by OP_KETRPOS. If the minimum
703 repetition is zero, the group is preceded by OP_BRAPOSZERO.
706 Once-only (atomic) groups
707 -------------------------
709 These are just like other subpatterns, but they start with the opcode OP_ONCE.
710 The check for matching an empty string in an unbounded repeat is handled
711 entirely at runtime, so there is just this one opcode for atomic groups.
717 Forward assertions are also just like other subpatterns, but starting with one
718 of the opcodes OP_ASSERT or OP_ASSERT_NOT. Backward assertions use the opcodes
719 OP_ASSERTBACK and OP_ASSERTBACK_NOT, and the first opcode inside the assertion
720 is OP_REVERSE, followed by a count of the number of characters to move back the
721 pointer in the subject string. In ASCII or UTF-32 mode, the count is also the
722 number of code units, but in UTF-8/16 mode each character may occupy more than
723 one code unit. A separate count is present in each alternative of a lookbehind
724 assertion, allowing them to have different (but fixed) lengths.
727 Conditional subpatterns
728 -----------------------
730 These are like other subpatterns, but they start with the opcode OP_COND, or
731 OP_SCOND for one that might match an empty string in an unbounded repeat.
733 If the condition is a back reference, this is stored at the start of the
734 subpattern using the opcode OP_CREF followed by a count containing the
735 reference number, provided that the reference is to a unique capturing group.
736 If the reference was by name and there is more than one group with that name,
737 OP_DNCREF is used instead. It is followed by two counts: the index in the group
738 names table, and the number of groups with the same name. The allows the
739 matcher to check if any group with the given name is set.
741 If the condition is "in recursion" (coded as "(?(R)"), or "in recursion of
742 group x" (coded as "(?(Rx)"), the group number is stored at the start of the
743 subpattern using the opcode OP_RREF (with a value of RREF_ANY (0xffff) for "the
744 whole pattern") or OP_DNRREF (with data as for OP_DNCREF).
746 For a DEFINE condition, OP_FALSE is used (with no associated data). During
747 compilation, however, a DEFINE condition is coded as OP_DEFINE so that, when
748 the conditional group is complete, there can be a check to ensure that it
749 contains only one top-level branch. Once this has happened, the opcode is
750 changed to OP_FALSE, so the matcher never sees OP_DEFINE.
752 There is a special PCRE2-specific condition of the form (VERSION[>]=x.y), which
753 tests the PCRE2 version number. This compiles into one of the opcodes OP_TRUE
756 If a condition is not a back reference, recursion test, DEFINE, or VERSION, it
757 must start with a parenthesized assertion, whose opcode normally immediately
758 follows OP_COND or OP_SCOND. However, if automatic callouts are enabled, a
759 callout is inserted immediately before the assertion. It is also possible to
760 insert a manual callout at this point. Only assertion conditions may have
761 callouts preceding the condition.
763 A condition that is the negative assertion (?!) is optimized to OP_FAIL in all
764 parts of the pattern, so this is another opcode that may appear as a condition.
765 It is treated the same as OP_FALSE.
771 Recursion either matches the current pattern, or some subexpression. The opcode
772 OP_RECURSE is followed by a LINK_SIZE value that is the offset to the starting
773 bracket from the start of the whole pattern. OP_RECURSE is also used for
774 "subroutine" calls, even though they are not strictly a recursion. Up till
775 release 10.30 recursions were treated as atomic groups, making them
776 incompatible with Perl (but PCRE had them well before Perl did). From 10.30,
777 backtracking into recursions is supported.
779 Repeated recursions used to be wrapped inside OP_ONCE brackets, which not only
780 forced no backtracking, but also allowed repetition to be handled as for other
781 bracketed groups. From 10.30 onwards, repeated recursions are duplicated for
782 their minimum repetitions, and then wrapped in non-capturing brackets for the
783 remainder. For example, (?1){3} is treated as (?1)(?1)(?1), and (?1){2,4} is
784 treated as (?1)(?1)(?:(?1)){0,2}.
790 A callout may have either a numerical argument or a string argument. These use
791 OP_CALLOUT or OP_CALLOUT_STR, respectively. In each case these are followed by
792 two LINK_SIZE values giving the offset in the pattern string to the start of
793 the following item, and another count giving the length of this item. These
794 values make it possible for pcre2test to output useful tracing information
797 In the case of a numeric callout, after these two values there is a single code
798 unit containing the callout number, in the range 0-255, with 255 being used for
799 callouts that are automatically inserted as a result of the PCRE2_AUTO_CALLOUT
800 option. Thus, this opcode item is of fixed length:
802 [OP_CALLOUT] [PATTERN_OFFSET] [PATTERN_LENGTH] [NUMBER]
804 For callouts with string arguments, OP_CALLOUT_STR has three more data items:
805 a LINK_SIZE value giving the complete length of the entire opcode item, a
806 LINK_SIZE item containing the offset within the pattern string to the start of
807 the string argument, and the string itself, preceded by its starting delimiter
808 and followed by a binary zero. When a callout function is called, a pointer to
809 the actual string is passed, but the delimiter can be accessed as string[-1] if
810 the application needs it. In the 8-bit library, the callout in /X(?C'abc')Y/ is
811 compiled as the following bytes (decimal numbers represent binary values):
813 [OP_CALLOUT_STR] [0] [10] [0] [1] [0] [14] [0] [5] ['] [a] [b] [c] [0]
814 -------- ------- -------- -------
816 ------- LINK_SIZE items ------
818 Opcode table checking
819 ---------------------
821 The last opcode that is defined in pcre2_internal.h is OP_TABLE_LENGTH. This is
822 not a real opcode, but is used to check at compile time that tables indexed by
823 opcode are the correct length, in order to catch updating errors.
projects / ossec-hids.git / blob