Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 1 | Technical Notes about PCRE2 |
| 2 | --------------------------- |
| 3 | |
| 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. |
| 9 | |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 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 |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 12 | confusion with PCRE1. |
| 13 | |
| 14 | |
| 15 | Historical note 1 |
| 16 | ----------------- |
| 17 | |
| 18 | Many years ago I implemented some regular expression functions to an algorithm |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 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 |
| 32 | regular expressions. |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 33 | |
| 34 | |
| 35 | Historical note 2 |
| 36 | ----------------- |
| 37 | |
| 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 |
| 45 | Friedl's terminology. |
| 46 | |
| 47 | |
| 48 | OK, here's the real stuff |
| 49 | ------------------------- |
| 50 | |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 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 |
| 58 | reasons. |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 59 | |
| 60 | |
| 61 | Support for 16-bit and 32-bit data strings |
| 62 | ------------------------------------------- |
| 63 | |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 64 | The PCRE2 library can be compiled in any combination of 8-bit, 16-bit or 32-bit |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 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. |
| 70 | |
| 71 | |
| 72 | Computing the memory requirement: how it was |
| 73 | -------------------------------------------- |
| 74 | |
| 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. |
| 81 | |
| 82 | |
| 83 | Computing the memory requirement: how it is |
| 84 | ------------------------------------------- |
| 85 | |
| 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 |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 91 | in most cases only ever using a small amount of working memory, and without too |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 92 | many tests of the mode that might slow it down. So I refactored the compiling |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 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). |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 97 | |
| 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. |
| 103 | |
| 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. |
| 109 | |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 110 | |
| 111 | Yet another pattern scan |
| 112 | ------------------------ |
| 113 | |
| 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 |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 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 |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 119 | issues. |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 120 | |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 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. |
| 128 | |
| 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: |
| 133 | |
| 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. |
| 145 | |
| 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. |
| 156 | |
| 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 |
| 162 | simpler than before. |
| 163 | |
| 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. |
| 168 | |
| 169 | |
| 170 | The elements of the parsed pattern vector |
| 171 | ----------------------------------------- |
| 172 | |
| 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: |
| 178 | |
| 179 | META_ACCEPT (*ACCEPT) |
| 180 | META_ASTERISK * |
| 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) |
| 195 | META_FAIL (*FAIL) |
| 196 | META_KET ) closing parenthesis |
| 197 | META_LOOKAHEAD (?= start of lookahead |
Elliott Hughes | 2dbd7d2 | 2020-06-03 14:32:37 -0700 | [diff] [blame] | 198 | META_LOOKAHEAD_NA (*napla: start of non-atomic lookahead |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 199 | META_LOOKAHEADNOT (?! start of negative lookahead |
| 200 | META_NOCAPTURE (?: no capture parens |
| 201 | META_PLUS + |
| 202 | META_PLUS_PLUS ++ |
| 203 | META_PLUS_QUERY +? |
| 204 | META_PRUNE (*PRUNE) - no argument |
| 205 | META_QUERY ? |
| 206 | META_QUERY_PLUS ?+ |
| 207 | META_QUERY_QUERY ?? |
| 208 | META_RANGE_ESCAPED hyphen in class range with at least one escape |
| 209 | META_RANGE_LITERAL hyphen in class range defined literally |
| 210 | META_SKIP (*SKIP) - no argument |
| 211 | META_THEN (*THEN) - no argument |
| 212 | |
| 213 | The two RANGE values occur only in character classes. They are positioned |
| 214 | between two literals that define the start and end of the range. In an EBCDIC |
| 215 | evironment it is necessary to know whether either of the range values was |
| 216 | specified as an escape. In an ASCII/Unicode environment the distinction is not |
| 217 | relevant. |
| 218 | |
| 219 | The following have data in the lower 16 bits, and may be followed by other data |
| 220 | elements: |
| 221 | |
| 222 | META_ALT | alternation |
| 223 | META_BACKREF back reference |
| 224 | META_CAPTURE start of capturing group |
| 225 | META_ESCAPE non-literal escape sequence |
| 226 | META_RECURSE recursion call |
| 227 | |
| 228 | If the data for META_ALT is non-zero, it is inside a lookbehind, and the data |
| 229 | is the length of its branch, for which OP_REVERSE must be generated. |
| 230 | |
| 231 | META_BACKREF, META_CAPTURE, and META_RECURSE have the capture group number as |
| 232 | their data in the lower 16 bits of the element. |
| 233 | |
| 234 | META_BACKREF is followed by an offset if the back reference group number is 10 |
| 235 | or more. The offsets of the first ocurrences of references to groups whose |
| 236 | numbers are less than 10 are put in cb->small_ref_offset[] (only the first |
| 237 | occurrence is useful). On 64-bit systems this avoids using more than two parsed |
| 238 | pattern elements for items such as \3. The offset is used when an error occurs |
| 239 | because the reference is to a non-existent group. |
| 240 | |
| 241 | META_RECURSE is always followed by an offset, for use in error messages. |
| 242 | |
| 243 | META_ESCAPE has an ESC_xxx value as its data. For ESC_P and ESC_p, the next |
| 244 | element contains the 16-bit type and data property values, packed together. |
| 245 | ESC_g and ESC_k are used only for named references - numerical ones are turned |
| 246 | into META_RECURSE or META_BACKREF as appropriate. ESC_g and ESC_k are followed |
| 247 | by a length and an offset into the pattern to specify the name. |
| 248 | |
| 249 | The following have one data item that follows in the next vector element: |
| 250 | |
| 251 | META_BIGVALUE Next is a literal >= META_END |
| 252 | META_OPTIONS (?i) and friends (data is new option bits) |
| 253 | META_POSIX POSIX class item (data identifies the class) |
| 254 | META_POSIX_NEG negative POSIX class item (ditto) |
| 255 | |
| 256 | The following are followed by a length element, then a number of character code |
| 257 | values (which should match with the length): |
| 258 | |
| 259 | META_MARK (*MARK:xxxx) |
Elliott Hughes | 653c210 | 2019-01-09 15:41:36 -0800 | [diff] [blame] | 260 | META_COMMIT_ARG )*COMMIT:xxxx) |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 261 | META_PRUNE_ARG (*PRUNE:xxx) |
| 262 | META_SKIP_ARG (*SKIP:xxxx) |
| 263 | META_THEN_ARG (*THEN:xxxx) |
| 264 | |
| 265 | The following are followed by a length element, then an offset in the pattern |
| 266 | that identifies the name: |
| 267 | |
| 268 | META_COND_NAME (?(<name>) or (?('name') or (?(name) |
| 269 | META_COND_RNAME (?(R&name) |
| 270 | META_COND_RNUMBER (?(Rdigits) |
| 271 | META_RECURSE_BYNAME (?&name) |
| 272 | META_BACKREF_BYNAME \k'name' |
| 273 | |
| 274 | META_COND_RNUMBER is used for names that start with R and continue with digits, |
| 275 | because this is an ambiguous case. It could be a back reference to a group with |
| 276 | that name, or it could be a recursion test on a numbered group. |
| 277 | |
| 278 | This one is followed by an offset, for use in error messages, then a number: |
| 279 | |
| 280 | META_COND_NUMBER (?([+-]digits) |
| 281 | |
| 282 | The following is followed just by an offset, for use in error messages: |
| 283 | |
| 284 | META_COND_DEFINE (?(DEFINE) |
| 285 | |
| 286 | The following are also followed just by an offset, but also the lower 16 bits |
| 287 | of the main word contain the length of the first branch of the lookbehind |
| 288 | group; this is used when generating OP_REVERSE for that branch. |
| 289 | |
Elliott Hughes | 2dbd7d2 | 2020-06-03 14:32:37 -0700 | [diff] [blame] | 290 | META_LOOKBEHIND (?<= start of lookbehind |
| 291 | META_LOOKBEHIND_NA (*naplb: start of non-atomic lookbehind |
| 292 | META_LOOKBEHINDNOT (?<! start of negative lookbehind |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 293 | |
| 294 | The following are followed by two elements, the minimum and maximum. Repeat |
| 295 | values are limited to 65535 (MAX_REPEAT). A maximum value of "unlimited" is |
| 296 | represented by UNLIMITED_REPEAT, which is bigger than MAX_REPEAT: |
| 297 | |
| 298 | META_MINMAX {n,m} repeat |
| 299 | META_MINMAX_PLUS {n,m}+ repeat |
| 300 | META_MINMAX_QUERY {n,m}? repeat |
| 301 | |
| 302 | This one is followed by three elements. The first is 0 for '>' and 1 for '>='; |
| 303 | the next two are the major and minor numbers: |
| 304 | |
| 305 | META_COND_VERSION (?(VERSION<op>x.y) |
| 306 | |
| 307 | Callouts are converted into one of two items: |
| 308 | |
| 309 | META_CALLOUT_NUMBER (?C with numerical argument |
| 310 | META_CALLOUT_STRING (?C with string argument |
| 311 | |
| 312 | In both cases, the next two elements contain the offset and length of the next |
| 313 | item in the pattern. Then there is either one callout number, or a length and |
| 314 | an offset for the string argument. The length includes both delimiters. |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 315 | |
| 316 | |
| 317 | Traditional matching function |
| 318 | ----------------------------- |
| 319 | |
| 320 | The "traditional", and original, matching function is called pcre2_match(), and |
| 321 | it implements an NFA algorithm, similar to the original Henry Spencer algorithm |
| 322 | and the way that Perl works. This is not surprising, since it is intended to be |
| 323 | as compatible with Perl as possible. This is the function most users of PCRE2 |
| 324 | will use most of the time. If PCRE2 is compiled with just-in-time (JIT) |
| 325 | support, and studying a compiled pattern with JIT is successful, the JIT code |
| 326 | is run instead of the normal pcre2_match() code, but the result is the same. |
| 327 | |
| 328 | |
| 329 | Supplementary matching function |
| 330 | ------------------------------- |
| 331 | |
| 332 | There is also a supplementary matching function called pcre2_dfa_match(). This |
| 333 | implements a DFA matching algorithm that searches simultaneously for all |
| 334 | possible matches that start at one point in the subject string. (Going back to |
| 335 | my roots: see Historical Note 1 above.) This function intreprets the same |
| 336 | compiled pattern data as pcre2_match(); however, not all the facilities are |
| 337 | available, and those that are do not always work in quite the same way. See the |
| 338 | user documentation for details. |
| 339 | |
| 340 | The algorithm that is used for pcre2_dfa_match() is not a traditional FSM, |
| 341 | because it may have a number of states active at one time. More work would be |
| 342 | needed at compile time to produce a traditional FSM where only one state is |
| 343 | ever active at once. I believe some other regex matchers work this way. JIT |
| 344 | support is not available for this kind of matching. |
| 345 | |
| 346 | |
| 347 | Changeable options |
| 348 | ------------------ |
| 349 | |
| 350 | The /i, /m, or /s options (PCRE2_CASELESS, PCRE2_MULTILINE, PCRE2_DOTALL, and |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 351 | others) may be changed in the middle of patterns by items such as (?i). Their |
| 352 | processing is handled entirely at compile time by generating different opcodes |
| 353 | for the different settings. The runtime functions do not need to keep track of |
Elliott Hughes | 653c210 | 2019-01-09 15:41:36 -0800 | [diff] [blame] | 354 | an option's state. |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 355 | |
| 356 | PCRE2_DUPNAMES, PCRE2_EXTENDED, PCRE2_EXTENDED_MORE, and PCRE2_NO_AUTO_CAPTURE |
| 357 | are tracked and processed during the parsing pre-pass. The others are handled |
| 358 | from META_OPTIONS items during the main compile phase. |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 359 | |
| 360 | |
| 361 | Format of compiled patterns |
| 362 | --------------------------- |
| 363 | |
| 364 | The compiled form of a pattern is a vector of unsigned code units (bytes in |
| 365 | 8-bit mode, shorts in 16-bit mode, 32-bit words in 32-bit mode), containing |
| 366 | items of variable length. The first code unit in an item contains an opcode, |
| 367 | and the length of the item is either implicit in the opcode or contained in the |
| 368 | data that follows it. |
| 369 | |
| 370 | In many cases listed below, LINK_SIZE data values are specified for offsets |
| 371 | within the compiled pattern. LINK_SIZE always specifies a number of bytes. The |
| 372 | default value for LINK_SIZE is 2, except for the 32-bit library, where it can |
| 373 | only be 4. The 8-bit library can be compiled to used 3-byte or 4-byte values, |
| 374 | and the 16-bit library can be compiled to use 4-byte values, though this |
| 375 | impairs performance. Specifing a LINK_SIZE larger than 2 for these libraries is |
Elliott Hughes | 653c210 | 2019-01-09 15:41:36 -0800 | [diff] [blame] | 376 | necessary only when patterns whose compiled length is greater than 65535 code |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 377 | units are going to be processed. When a LINK_SIZE value uses more than one code |
| 378 | unit, the most significant unit is first. |
| 379 | |
| 380 | In this description, we assume the "normal" compilation options. Data values |
| 381 | that are counts (e.g. quantifiers) are always two bytes long in 8-bit mode |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 382 | (most significant byte first), and one code unit in 16-bit and 32-bit modes. |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 383 | |
| 384 | |
| 385 | Opcodes with no following data |
| 386 | ------------------------------ |
| 387 | |
Elliott Hughes | 653c210 | 2019-01-09 15:41:36 -0800 | [diff] [blame] | 388 | These items are all just one unit long: |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 389 | |
| 390 | OP_END end of pattern |
| 391 | OP_ANY match any one character other than newline |
| 392 | OP_ALLANY match any one character, including newline |
| 393 | OP_ANYBYTE match any single code unit, even in UTF-8/16 mode |
| 394 | OP_SOD match start of data: \A |
| 395 | OP_SOM, start of match (subject + offset): \G |
| 396 | OP_SET_SOM, set start of match (\K) |
| 397 | OP_CIRC ^ (start of data) |
| 398 | OP_CIRCM ^ multiline mode (start of data or after newline) |
| 399 | OP_NOT_WORD_BOUNDARY \W |
| 400 | OP_WORD_BOUNDARY \w |
| 401 | OP_NOT_DIGIT \D |
| 402 | OP_DIGIT \d |
| 403 | OP_NOT_HSPACE \H |
| 404 | OP_HSPACE \h |
| 405 | OP_NOT_WHITESPACE \S |
| 406 | OP_WHITESPACE \s |
| 407 | OP_NOT_VSPACE \V |
| 408 | OP_VSPACE \v |
| 409 | OP_NOT_WORDCHAR \W |
| 410 | OP_WORDCHAR \w |
| 411 | OP_EODN match end of data or newline at end: \Z |
| 412 | OP_EOD match end of data: \z |
| 413 | OP_DOLL $ (end of data, or before final newline) |
| 414 | OP_DOLLM $ multiline mode (end of data or before newline) |
| 415 | OP_EXTUNI match an extended Unicode grapheme cluster |
| 416 | OP_ANYNL match any Unicode newline sequence |
| 417 | |
| 418 | OP_ASSERT_ACCEPT ) |
| 419 | OP_ACCEPT ) These are Perl 5.10's "backtracking control |
| 420 | OP_COMMIT ) verbs". If OP_ACCEPT is inside capturing |
| 421 | OP_FAIL ) parentheses, it may be preceded by one or more |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 422 | OP_PRUNE ) OP_CLOSE, each followed by a number that |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 423 | OP_SKIP ) indicates which parentheses must be closed. |
| 424 | OP_THEN ) |
| 425 | |
| 426 | OP_ASSERT_ACCEPT is used when (*ACCEPT) is encountered within an assertion. |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 427 | This ends the assertion, not the entire pattern match. The assertion (?!) is |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 428 | always optimized to OP_FAIL. |
| 429 | |
Janis Danisevskis | 8b979b2 | 2016-08-15 16:09:16 +0100 | [diff] [blame] | 430 | OP_ALLANY is used for '.' when PCRE2_DOTALL is set. It is also used for \C in |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 431 | non-UTF modes and in UTF-32 mode (since one code unit still equals one |
Janis Danisevskis | 8b979b2 | 2016-08-15 16:09:16 +0100 | [diff] [blame] | 432 | character). Another use is for [^] when empty classes are permitted |
| 433 | (PCRE2_ALLOW_EMPTY_CLASS is set). |
| 434 | |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 435 | |
Elliott Hughes | 653c210 | 2019-01-09 15:41:36 -0800 | [diff] [blame] | 436 | Backtracking control verbs |
| 437 | -------------------------- |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 438 | |
Elliott Hughes | 653c210 | 2019-01-09 15:41:36 -0800 | [diff] [blame] | 439 | Verbs with no arguments generate opcodes with no following data (as listed |
| 440 | in the section above). |
| 441 | |
| 442 | (*MARK:NAME) generates OP_MARK followed by the mark name, preceded by a |
| 443 | length in one code unit, and followed by a binary zero. The name length is |
| 444 | limited by the size of the code unit. |
| 445 | |
| 446 | (*ACCEPT:NAME) and (*FAIL:NAME) are compiled as (*MARK:NAME)(*ACCEPT) and |
| 447 | (*MARK:NAME)(*FAIL) respectively. |
| 448 | |
| 449 | For (*COMMIT:NAME), (*PRUNE:NAME), (*SKIP:NAME), and (*THEN:NAME), the opcodes |
| 450 | OP_COMMIT_ARG, OP_PRUNE_ARG, OP_SKIP_ARG, and OP_THEN_ARG are used, with the |
| 451 | name following in the same format as for OP_MARK. |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 452 | |
| 453 | |
| 454 | Matching literal characters |
| 455 | --------------------------- |
| 456 | |
| 457 | The OP_CHAR opcode is followed by a single character that is to be matched |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 458 | casefully. For caseless matching of characters that have at most two |
| 459 | case-equivalent code points, OP_CHARI is used. In UTF-8 or UTF-16 modes, the |
| 460 | character may be more than one code unit long. In UTF-32 mode, characters are |
| 461 | always exactly one code unit long. |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 462 | |
| 463 | If there is only one character in a character class, OP_CHAR or OP_CHARI is |
| 464 | used for a positive class, and OP_NOT or OP_NOTI for a negative one (that is, |
| 465 | for something like [^a]). |
| 466 | |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 467 | Caseless matching (positive or negative) of characters that have more than two |
| 468 | case-equivalent code points (which is possible only in UTF mode) is handled by |
| 469 | compiling a Unicode property item (see below), with the pseudo-property |
| 470 | PT_CLIST. The value of this property is an offset in a vector called |
| 471 | "ucd_caseless_sets" which identifies the start of a short list of equivalent |
| 472 | characters, terminated by the value NOTACHAR (0xffffffff). |
| 473 | |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 474 | |
| 475 | Repeating single characters |
| 476 | --------------------------- |
| 477 | |
| 478 | The common repeats (*, +, ?), when applied to a single character, use the |
| 479 | following opcodes, which come in caseful and caseless versions: |
| 480 | |
| 481 | Caseful Caseless |
| 482 | OP_STAR OP_STARI |
| 483 | OP_MINSTAR OP_MINSTARI |
| 484 | OP_POSSTAR OP_POSSTARI |
| 485 | OP_PLUS OP_PLUSI |
| 486 | OP_MINPLUS OP_MINPLUSI |
| 487 | OP_POSPLUS OP_POSPLUSI |
| 488 | OP_QUERY OP_QUERYI |
| 489 | OP_MINQUERY OP_MINQUERYI |
| 490 | OP_POSQUERY OP_POSQUERYI |
| 491 | |
| 492 | Each opcode is followed by the character that is to be repeated. In ASCII or |
| 493 | UTF-32 modes, these are two-code-unit items; in UTF-8 or UTF-16 modes, the |
| 494 | length is variable. Those with "MIN" in their names are the minimizing |
| 495 | versions. Those with "POS" in their names are possessive versions. Other kinds |
| 496 | of repeat make use of these opcodes: |
| 497 | |
| 498 | Caseful Caseless |
| 499 | OP_UPTO OP_UPTOI |
| 500 | OP_MINUPTO OP_MINUPTOI |
| 501 | OP_POSUPTO OP_POSUPTOI |
| 502 | OP_EXACT OP_EXACTI |
| 503 | |
| 504 | Each of these is followed by a count and then the repeated character. The count |
| 505 | is two bytes long in 8-bit mode (most significant byte first), or one code unit |
| 506 | in 16-bit and 32-bit modes. |
| 507 | |
| 508 | OP_UPTO matches from 0 to the given number. A repeat with a non-zero minimum |
| 509 | and a fixed maximum is coded as an OP_EXACT followed by an OP_UPTO (or |
| 510 | OP_MINUPTO or OPT_POSUPTO). |
| 511 | |
| 512 | Another set of matching repeating opcodes (called OP_NOTSTAR, OP_NOTSTARI, |
| 513 | etc.) are used for repeated, negated, single-character classes such as [^a]*. |
| 514 | The normal single-character opcodes (OP_STAR, etc.) are used for repeated |
| 515 | positive single-character classes. |
| 516 | |
| 517 | |
| 518 | Repeating character types |
| 519 | ------------------------- |
| 520 | |
| 521 | Repeats of things like \d are done exactly as for single characters, except |
| 522 | that instead of a character, the opcode for the type (e.g. OP_DIGIT) is stored |
| 523 | in the next code unit. The opcodes are: |
| 524 | |
| 525 | OP_TYPESTAR |
| 526 | OP_TYPEMINSTAR |
| 527 | OP_TYPEPOSSTAR |
| 528 | OP_TYPEPLUS |
| 529 | OP_TYPEMINPLUS |
| 530 | OP_TYPEPOSPLUS |
| 531 | OP_TYPEQUERY |
| 532 | OP_TYPEMINQUERY |
| 533 | OP_TYPEPOSQUERY |
| 534 | OP_TYPEUPTO |
| 535 | OP_TYPEMINUPTO |
| 536 | OP_TYPEPOSUPTO |
| 537 | OP_TYPEEXACT |
| 538 | |
| 539 | |
| 540 | Match by Unicode property |
| 541 | ------------------------- |
| 542 | |
| 543 | OP_PROP and OP_NOTPROP are used for positive and negative matches of a |
| 544 | character by testing its Unicode property (the \p and \P escape sequences). |
| 545 | Each is followed by two code units that encode the desired property as a type |
| 546 | and a value. The types are a set of #defines of the form PT_xxx, and the values |
| 547 | are enumerations of the form ucp_xx, defined in the pcre2_ucp.h source file. |
| 548 | The value is relevant only for PT_GC (General Category), PT_PC (Particular |
Elliott Hughes | 4e19c8e | 2022-04-15 15:11:02 -0700 | [diff] [blame] | 549 | Category), PT_SC (Script), PT_BIDICL (Bidi Class), and the pseudo-property |
| 550 | PT_CLIST, which is used to identify a list of case-equivalent characters when |
| 551 | there are three or more. |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 552 | |
| 553 | Repeats of these items use the OP_TYPESTAR etc. set of opcodes, followed by |
| 554 | three code units: OP_PROP or OP_NOTPROP, and then the desired property type and |
| 555 | value. |
| 556 | |
| 557 | |
| 558 | Character classes |
| 559 | ----------------- |
| 560 | |
| 561 | If there is only one character in a class, OP_CHAR or OP_CHARI is used for a |
| 562 | positive class, and OP_NOT or OP_NOTI for a negative one (that is, for |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 563 | something like [^a]), except when caselessly matching a character that has more |
| 564 | than two case-equivalent code points (which can happen only in UTF mode). In |
| 565 | this case a Unicode property item is used, as described above in "Matching |
| 566 | literal characters". |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 567 | |
| 568 | A set of repeating opcodes (called OP_NOTSTAR etc.) are used for repeated, |
| 569 | negated, single-character classes. The normal single-character opcodes |
| 570 | (OP_STAR, etc.) are used for repeated positive single-character classes. |
| 571 | |
| 572 | When there is more than one character in a class, and all the code points are |
| 573 | less than 256, OP_CLASS is used for a positive class, and OP_NCLASS for a |
| 574 | negative one. In either case, the opcode is followed by a 32-byte (16-short, |
| 575 | 8-word) bit map containing a 1 bit for every character that is acceptable. The |
| 576 | bits are counted from the least significant end of each unit. In caseless mode, |
| 577 | bits for both cases are set. |
| 578 | |
| 579 | The reason for having both OP_CLASS and OP_NCLASS is so that, in UTF-8 and |
| 580 | 16-bit and 32-bit modes, subject characters with values greater than 255 can be |
| 581 | handled correctly. For OP_CLASS they do not match, whereas for OP_NCLASS they |
| 582 | do. |
| 583 | |
| 584 | For classes containing characters with values greater than 255 or that contain |
| 585 | \p or \P, OP_XCLASS is used. It optionally uses a bit map if any acceptable |
| 586 | code points are less than 256, followed by a list of pairs (for a range) and/or |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 587 | single characters and/or properties. In caseless mode, all equivalent |
| 588 | characters are explicitly listed. |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 589 | |
| 590 | OP_XCLASS is followed by a LINK_SIZE value containing the total length of the |
| 591 | opcode and its data. This is followed by a code unit containing flag bits: |
| 592 | XCL_NOT indicates that this is a negative class, and XCL_MAP indicates that a |
| 593 | bit map is present. There follows the bit map, if XCL_MAP is set, and then a |
| 594 | sequence of items coded as follows: |
| 595 | |
| 596 | XCL_END marks the end of the list |
| 597 | XCL_SINGLE one character follows |
| 598 | XCL_RANGE two characters follow |
| 599 | XCL_PROP a Unicode property (type, value) follows |
| 600 | XCL_NOTPROP a Unicode property (type, value) follows |
| 601 | |
| 602 | If a range starts with a code point less than 256 and ends with one greater |
| 603 | than 255, it is split into two ranges, with characters less than 256 being |
| 604 | indicated in the bit map, and the rest with XCL_RANGE. |
| 605 | |
| 606 | When XCL_NOT is set, the bit map, if present, contains bits for characters that |
| 607 | are allowed (exactly as for OP_NCLASS), but the list of items that follow it |
| 608 | specifies characters and properties that are not allowed. |
| 609 | |
| 610 | |
| 611 | Back references |
| 612 | --------------- |
| 613 | |
| 614 | OP_REF (caseful) or OP_REFI (caseless) is followed by a count containing the |
| 615 | reference number when the reference is to a unique capturing group (either by |
| 616 | number or by name). When named groups are used, there may be more than one |
| 617 | group with the same name. In this case, a reference to such a group by name |
| 618 | generates OP_DNREF or OP_DNREFI. These are followed by two counts: the index |
| 619 | (not the byte offset) in the group name table of the first entry for the |
| 620 | required name, followed by the number of groups with the same name. The |
| 621 | matching code can then search for the first one that is set. |
| 622 | |
| 623 | |
| 624 | Repeating character classes and back references |
| 625 | ----------------------------------------------- |
| 626 | |
| 627 | Single-character classes are handled specially (see above). This section |
| 628 | applies to other classes and also to back references. In both cases, the repeat |
| 629 | information follows the base item. The matching code looks at the following |
| 630 | opcode to see if it is one of these: |
| 631 | |
| 632 | OP_CRSTAR |
| 633 | OP_CRMINSTAR |
| 634 | OP_CRPOSSTAR |
| 635 | OP_CRPLUS |
| 636 | OP_CRMINPLUS |
| 637 | OP_CRPOSPLUS |
| 638 | OP_CRQUERY |
| 639 | OP_CRMINQUERY |
| 640 | OP_CRPOSQUERY |
| 641 | OP_CRRANGE |
| 642 | OP_CRMINRANGE |
| 643 | OP_CRPOSRANGE |
| 644 | |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 645 | All but the last three are single-code-unit items, with no data. The range |
| 646 | opcodes are followed by the minimum and maximum repeat counts. |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 647 | |
| 648 | |
| 649 | Brackets and alternation |
| 650 | ------------------------ |
| 651 | |
| 652 | A pair of non-capturing round brackets is wrapped round each expression at |
| 653 | compile time, so alternation always happens in the context of brackets. |
| 654 | |
| 655 | [Note for North Americans: "bracket" to some English speakers, including |
| 656 | myself, can be round, square, curly, or pointy. Hence this usage rather than |
| 657 | "parentheses".] |
| 658 | |
| 659 | Non-capturing brackets use the opcode OP_BRA, capturing brackets use OP_CBRA. A |
| 660 | bracket opcode is followed by a LINK_SIZE value which gives the offset to the |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 661 | next alternative OP_ALT or, if there aren't any branches, to the terminating |
| 662 | opcode. Each OP_ALT is followed by a LINK_SIZE value giving the offset to the |
| 663 | next one, or to the final opcode. For capturing brackets, the bracket number is |
| 664 | a count that immediately follows the offset. |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 665 | |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 666 | There are several opcodes that mark the end of a subpattern group. OP_KET is |
| 667 | used for subpatterns that do not repeat indefinitely, OP_KETRMIN and |
| 668 | OP_KETRMAX are used for indefinite repetitions, minimally or maximally |
| 669 | respectively, and OP_KETRPOS for possessive repetitions (see below for more |
| 670 | details). All four are followed by a LINK_SIZE value giving (as a positive |
| 671 | number) the offset back to the matching bracket opcode. |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 672 | |
| 673 | If a subpattern is quantified such that it is permitted to match zero times, it |
| 674 | is preceded by one of OP_BRAZERO, OP_BRAMINZERO, or OP_SKIPZERO. These are |
| 675 | single-unit opcodes that tell the matcher that skipping the following |
| 676 | subpattern entirely is a valid match. In the case of the first two, not |
| 677 | skipping the pattern is also valid (greedy and non-greedy). The third is used |
| 678 | when a pattern has the quantifier {0,0}. It cannot be entirely discarded, |
| 679 | because it may be called as a subroutine from elsewhere in the pattern. |
| 680 | |
| 681 | A subpattern with an indefinite maximum repetition is replicated in the |
| 682 | compiled data its minimum number of times (or once with OP_BRAZERO if the |
| 683 | minimum is zero), with the final copy terminating with OP_KETRMIN or OP_KETRMAX |
| 684 | as appropriate. |
| 685 | |
| 686 | A subpattern with a bounded maximum repetition is replicated in a nested |
| 687 | fashion up to the maximum number of times, with OP_BRAZERO or OP_BRAMINZERO |
| 688 | before each replication after the minimum, so that, for example, (abc){2,5} is |
| 689 | compiled as (abc)(abc)((abc)((abc)(abc)?)?)?, except that each bracketed group |
| 690 | has the same number. |
| 691 | |
| 692 | When a repeated subpattern has an unbounded upper limit, it is checked to see |
| 693 | whether it could match an empty string. If this is the case, the opcode in the |
| 694 | final replication is changed to OP_SBRA or OP_SCBRA. This tells the matcher |
| 695 | that it needs to check for matching an empty string when it hits OP_KETRMIN or |
| 696 | OP_KETRMAX, and if so, to break the loop. |
| 697 | |
| 698 | |
| 699 | Possessive brackets |
| 700 | ------------------- |
| 701 | |
| 702 | When a repeated group (capturing or non-capturing) is marked as possessive by |
| 703 | the "+" notation, e.g. (abc)++, different opcodes are used. Their names all |
| 704 | have POS on the end, e.g. OP_BRAPOS instead of OP_BRA and OP_SCBRAPOS instead |
| 705 | of OP_SCBRA. The end of such a group is marked by OP_KETRPOS. If the minimum |
| 706 | repetition is zero, the group is preceded by OP_BRAPOSZERO. |
| 707 | |
| 708 | |
| 709 | Once-only (atomic) groups |
| 710 | ------------------------- |
| 711 | |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 712 | These are just like other subpatterns, but they start with the opcode OP_ONCE. |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 713 | The check for matching an empty string in an unbounded repeat is handled |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 714 | entirely at runtime, so there is just this one opcode for atomic groups. |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 715 | |
| 716 | |
| 717 | Assertions |
| 718 | ---------- |
| 719 | |
| 720 | Forward assertions are also just like other subpatterns, but starting with one |
Elliott Hughes | 2dbd7d2 | 2020-06-03 14:32:37 -0700 | [diff] [blame] | 721 | of the opcodes OP_ASSERT, OP_ASSERT_NA (non-atomic assertion), or |
| 722 | OP_ASSERT_NOT. Backward assertions use the opcodes OP_ASSERTBACK, |
| 723 | OP_ASSERTBACK_NA, and OP_ASSERTBACK_NOT, and the first opcode inside the |
| 724 | assertion is OP_REVERSE, followed by a count of the number of characters to |
| 725 | move back the pointer in the subject string. In ASCII or UTF-32 mode, the count |
| 726 | is also the number of code units, but in UTF-8/16 mode each character may |
| 727 | occupy more than one code unit. A separate count is present in each alternative |
| 728 | of a lookbehind assertion, allowing each branch to have a different (but fixed) |
| 729 | length. |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 730 | |
| 731 | |
| 732 | Conditional subpatterns |
| 733 | ----------------------- |
| 734 | |
| 735 | These are like other subpatterns, but they start with the opcode OP_COND, or |
| 736 | OP_SCOND for one that might match an empty string in an unbounded repeat. |
| 737 | |
| 738 | If the condition is a back reference, this is stored at the start of the |
| 739 | subpattern using the opcode OP_CREF followed by a count containing the |
| 740 | reference number, provided that the reference is to a unique capturing group. |
| 741 | If the reference was by name and there is more than one group with that name, |
| 742 | OP_DNCREF is used instead. It is followed by two counts: the index in the group |
| 743 | names table, and the number of groups with the same name. The allows the |
| 744 | matcher to check if any group with the given name is set. |
| 745 | |
| 746 | If the condition is "in recursion" (coded as "(?(R)"), or "in recursion of |
| 747 | group x" (coded as "(?(Rx)"), the group number is stored at the start of the |
| 748 | subpattern using the opcode OP_RREF (with a value of RREF_ANY (0xffff) for "the |
| 749 | whole pattern") or OP_DNRREF (with data as for OP_DNCREF). |
| 750 | |
| 751 | For a DEFINE condition, OP_FALSE is used (with no associated data). During |
| 752 | compilation, however, a DEFINE condition is coded as OP_DEFINE so that, when |
| 753 | the conditional group is complete, there can be a check to ensure that it |
| 754 | contains only one top-level branch. Once this has happened, the opcode is |
| 755 | changed to OP_FALSE, so the matcher never sees OP_DEFINE. |
| 756 | |
| 757 | There is a special PCRE2-specific condition of the form (VERSION[>]=x.y), which |
| 758 | tests the PCRE2 version number. This compiles into one of the opcodes OP_TRUE |
| 759 | or OP_FALSE. |
| 760 | |
| 761 | If a condition is not a back reference, recursion test, DEFINE, or VERSION, it |
Elliott Hughes | 2dbd7d2 | 2020-06-03 14:32:37 -0700 | [diff] [blame] | 762 | must start with a parenthesized atomic assertion, whose opcode normally |
| 763 | immediately follows OP_COND or OP_SCOND. However, if automatic callouts are |
| 764 | enabled, a callout is inserted immediately before the assertion. It is also |
| 765 | possible to insert a manual callout at this point. Only assertion conditions |
| 766 | may have callouts preceding the condition. |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 767 | |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 768 | A condition that is the negative assertion (?!) is optimized to OP_FAIL in all |
| 769 | parts of the pattern, so this is another opcode that may appear as a condition. |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 770 | It is treated the same as OP_FALSE. |
| 771 | |
| 772 | |
| 773 | Recursion |
| 774 | --------- |
| 775 | |
| 776 | Recursion either matches the current pattern, or some subexpression. The opcode |
| 777 | OP_RECURSE is followed by a LINK_SIZE value that is the offset to the starting |
| 778 | bracket from the start of the whole pattern. OP_RECURSE is also used for |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 779 | "subroutine" calls, even though they are not strictly a recursion. Up till |
| 780 | release 10.30 recursions were treated as atomic groups, making them |
Elliott Hughes | 653c210 | 2019-01-09 15:41:36 -0800 | [diff] [blame] | 781 | incompatible with Perl (but PCRE had them well before Perl did). From 10.30, |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 782 | backtracking into recursions is supported. |
| 783 | |
| 784 | Repeated recursions used to be wrapped inside OP_ONCE brackets, which not only |
| 785 | forced no backtracking, but also allowed repetition to be handled as for other |
| 786 | bracketed groups. From 10.30 onwards, repeated recursions are duplicated for |
| 787 | their minimum repetitions, and then wrapped in non-capturing brackets for the |
| 788 | remainder. For example, (?1){3} is treated as (?1)(?1)(?1), and (?1){2,4} is |
| 789 | treated as (?1)(?1)(?:(?1)){0,2}. |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 790 | |
| 791 | |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 792 | Callouts |
| 793 | -------- |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 794 | |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 795 | A callout may have either a numerical argument or a string argument. These use |
| 796 | OP_CALLOUT or OP_CALLOUT_STR, respectively. In each case these are followed by |
| 797 | two LINK_SIZE values giving the offset in the pattern string to the start of |
| 798 | the following item, and another count giving the length of this item. These |
| 799 | values make it possible for pcre2test to output useful tracing information |
| 800 | using callouts. |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 801 | |
| 802 | In the case of a numeric callout, after these two values there is a single code |
| 803 | unit containing the callout number, in the range 0-255, with 255 being used for |
| 804 | callouts that are automatically inserted as a result of the PCRE2_AUTO_CALLOUT |
| 805 | option. Thus, this opcode item is of fixed length: |
| 806 | |
| 807 | [OP_CALLOUT] [PATTERN_OFFSET] [PATTERN_LENGTH] [NUMBER] |
| 808 | |
| 809 | For callouts with string arguments, OP_CALLOUT_STR has three more data items: |
| 810 | a LINK_SIZE value giving the complete length of the entire opcode item, a |
| 811 | LINK_SIZE item containing the offset within the pattern string to the start of |
| 812 | the string argument, and the string itself, preceded by its starting delimiter |
| 813 | and followed by a binary zero. When a callout function is called, a pointer to |
| 814 | the actual string is passed, but the delimiter can be accessed as string[-1] if |
| 815 | the application needs it. In the 8-bit library, the callout in /X(?C'abc')Y/ is |
| 816 | compiled as the following bytes (decimal numbers represent binary values): |
| 817 | |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 818 | [OP_CALLOUT_STR] [0] [10] [0] [1] [0] [14] [0] [5] ['] [a] [b] [c] [0] |
| 819 | -------- ------- -------- ------- |
| 820 | | | | | |
| 821 | ------- LINK_SIZE items ------ |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 822 | |
| 823 | Opcode table checking |
| 824 | --------------------- |
| 825 | |
| 826 | The last opcode that is defined in pcre2_internal.h is OP_TABLE_LENGTH. This is |
Elliott Hughes | 9bc971b | 2018-07-27 13:23:14 -0700 | [diff] [blame] | 827 | not a real opcode, but is used to check at compile time that tables indexed by |
| 828 | opcode are the correct length, in order to catch updating errors. |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 829 | |
| 830 | Philip Hazel |
Elliott Hughes | 4e19c8e | 2022-04-15 15:11:02 -0700 | [diff] [blame] | 831 | December 2021 |