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 | |
| 10 | PCRE1 releases were up to 8.3x when PCRE2 was developed. The 8.xx series will |
| 11 | continue for bugfixes if necessary. PCRE2 releases started at 10.00 to avoid |
| 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 |
| 19 | suggested by Martin Richards. These were not Unix-like in form, and were quite |
| 20 | restricted in what they could do by comparison with Perl. The interesting part |
| 21 | about the algorithm was that the amount of space required to hold the compiled |
| 22 | form of an expression was known in advance. The code to apply an expression did |
| 23 | not operate by backtracking, as the original Henry Spencer code and current |
| 24 | PCRE2 and Perl code does, but instead checked all possibilities simultaneously |
| 25 | by keeping a list of current states and checking all of them as it advanced |
| 26 | through the subject string. In the terminology of Jeffrey Friedl's book, it was |
| 27 | a "DFA algorithm", though it was not a traditional Finite State Machine (FSM). |
| 28 | When the pattern was all used up, all remaining states were possible matches, |
| 29 | and the one matching the longest subset of the subject string was chosen. This |
| 30 | did not necessarily maximize the individual wild portions of the pattern, as is |
| 31 | expected in Unix and Perl-style regular expressions. |
| 32 | |
| 33 | |
| 34 | Historical note 2 |
| 35 | ----------------- |
| 36 | |
| 37 | By contrast, the code originally written by Henry Spencer (which was |
| 38 | subsequently heavily modified for Perl) compiles the expression twice: once in |
| 39 | a dummy mode in order to find out how much store will be needed, and then for |
| 40 | real. (The Perl version probably doesn't do this any more; I'm talking about |
| 41 | the original library.) The execution function operates by backtracking and |
| 42 | maximizing (or, optionally, minimizing, in Perl) the amount of the subject that |
| 43 | matches individual wild portions of the pattern. This is an "NFA algorithm" in |
| 44 | Friedl's terminology. |
| 45 | |
| 46 | |
| 47 | OK, here's the real stuff |
| 48 | ------------------------- |
| 49 | |
| 50 | For the set of functions that formed the original PCRE1 library (which are |
| 51 | unrelated to those mentioned above), I tried at first to invent an algorithm |
| 52 | that used an amount of store bounded by a multiple of the number of characters |
| 53 | in the pattern, to save on compiling time. However, because of the greater |
| 54 | complexity in Perl regular expressions, I couldn't do this. In any case, a |
| 55 | first pass through the pattern is helpful for other reasons. |
| 56 | |
| 57 | |
| 58 | Support for 16-bit and 32-bit data strings |
| 59 | ------------------------------------------- |
| 60 | |
| 61 | The library can be compiled in any combination of 8-bit, 16-bit or 32-bit |
| 62 | modes, creating up to three different libraries. In the description that |
| 63 | follows, the word "short" is used for a 16-bit data quantity, and the phrase |
| 64 | "code unit" is used for a quantity that is a byte in 8-bit mode, a short in |
| 65 | 16-bit mode and a 32-bit word in 32-bit mode. The names of PCRE2 functions are |
| 66 | given in generic form, without the _8, _16, or _32 suffix. |
| 67 | |
| 68 | |
| 69 | Computing the memory requirement: how it was |
| 70 | -------------------------------------------- |
| 71 | |
| 72 | Up to and including release 6.7, PCRE1 worked by running a very degenerate |
| 73 | first pass to calculate a maximum memory requirement, and then a second pass to |
| 74 | do the real compile - which might use a bit less than the predicted amount of |
| 75 | memory. The idea was that this would turn out faster than the Henry Spencer |
| 76 | code because the first pass is degenerate and the second pass can just store |
| 77 | stuff straight into memory, which it knows is big enough. |
| 78 | |
| 79 | |
| 80 | Computing the memory requirement: how it is |
| 81 | ------------------------------------------- |
| 82 | |
| 83 | By the time I was working on a potential 6.8 release, the degenerate first pass |
| 84 | had become very complicated and hard to maintain. Indeed one of the early |
| 85 | things I did for 6.8 was to fix Yet Another Bug in the memory computation. Then |
| 86 | I had a flash of inspiration as to how I could run the real compile function in |
| 87 | a "fake" mode that enables it to compute how much memory it would need, while |
| 88 | actually only ever using a few hundred bytes of working memory, and without too |
| 89 | many tests of the mode that might slow it down. So I refactored the compiling |
| 90 | functions to work this way. This got rid of about 600 lines of source. It |
| 91 | should make future maintenance and development easier. As this was such a major |
| 92 | change, I never released 6.8, instead upping the number to 7.0 (other quite |
| 93 | major changes were also present in the 7.0 release). |
| 94 | |
| 95 | A side effect of this work was that the previous limit of 200 on the nesting |
| 96 | depth of parentheses was removed. However, there was a downside: compiling ran |
| 97 | more slowly than before (30% or more, depending on the pattern) because it now |
| 98 | did a full analysis of the pattern. My hope was that this would not be a big |
| 99 | issue, and in the event, nobody has commented on it. |
| 100 | |
| 101 | At release 8.34, a limit on the nesting depth of parentheses was re-introduced |
| 102 | (default 250, settable at build time) so as to put a limit on the amount of |
| 103 | system stack used by the compile function, which uses recursive function calls |
| 104 | for nested parenthesized groups. This is a safety feature for environments with |
| 105 | small stacks where the patterns are provided by users. |
| 106 | |
| 107 | History repeated itself for release 10.20. A number of bugs relating to named |
| 108 | subpatterns had been discovered by fuzzers. Most of these were related to the |
| 109 | handling of forward references when it was not known if the named pattern was |
| 110 | unique. (References to non-unique names use a different opcode and more |
| 111 | memory.) The use of duplicate group numbers (the (?| facility) also caused |
| 112 | issues. |
| 113 | |
| 114 | To get around these problems I adopted a new approach by adding a third pass, |
| 115 | really a "pre-pass", over the pattern, which does nothing other than identify |
| 116 | all the named subpatterns and their corresponding group numbers. This means |
| 117 | that the actual compile (both pre-pass and real compile) have full knowledge of |
| 118 | group names and numbers throughout. Several dozen lines of messy code were |
| 119 | eliminated, though the new pre-pass is not short (skipping over [] classes is |
| 120 | complicated). |
| 121 | |
| 122 | |
| 123 | Traditional matching function |
| 124 | ----------------------------- |
| 125 | |
| 126 | The "traditional", and original, matching function is called pcre2_match(), and |
| 127 | it implements an NFA algorithm, similar to the original Henry Spencer algorithm |
| 128 | and the way that Perl works. This is not surprising, since it is intended to be |
| 129 | as compatible with Perl as possible. This is the function most users of PCRE2 |
| 130 | will use most of the time. If PCRE2 is compiled with just-in-time (JIT) |
| 131 | support, and studying a compiled pattern with JIT is successful, the JIT code |
| 132 | is run instead of the normal pcre2_match() code, but the result is the same. |
| 133 | |
| 134 | |
| 135 | Supplementary matching function |
| 136 | ------------------------------- |
| 137 | |
| 138 | There is also a supplementary matching function called pcre2_dfa_match(). This |
| 139 | implements a DFA matching algorithm that searches simultaneously for all |
| 140 | possible matches that start at one point in the subject string. (Going back to |
| 141 | my roots: see Historical Note 1 above.) This function intreprets the same |
| 142 | compiled pattern data as pcre2_match(); however, not all the facilities are |
| 143 | available, and those that are do not always work in quite the same way. See the |
| 144 | user documentation for details. |
| 145 | |
| 146 | The algorithm that is used for pcre2_dfa_match() is not a traditional FSM, |
| 147 | because it may have a number of states active at one time. More work would be |
| 148 | needed at compile time to produce a traditional FSM where only one state is |
| 149 | ever active at once. I believe some other regex matchers work this way. JIT |
| 150 | support is not available for this kind of matching. |
| 151 | |
| 152 | |
| 153 | Changeable options |
| 154 | ------------------ |
| 155 | |
| 156 | The /i, /m, or /s options (PCRE2_CASELESS, PCRE2_MULTILINE, PCRE2_DOTALL, and |
| 157 | some others) may change in the middle of patterns. Their processing is handled |
| 158 | entirely at compile time by generating different opcodes for the different |
| 159 | settings. The runtime functions do not need to keep track of an options state. |
| 160 | |
| 161 | |
| 162 | Format of compiled patterns |
| 163 | --------------------------- |
| 164 | |
| 165 | The compiled form of a pattern is a vector of unsigned code units (bytes in |
| 166 | 8-bit mode, shorts in 16-bit mode, 32-bit words in 32-bit mode), containing |
| 167 | items of variable length. The first code unit in an item contains an opcode, |
| 168 | and the length of the item is either implicit in the opcode or contained in the |
| 169 | data that follows it. |
| 170 | |
| 171 | In many cases listed below, LINK_SIZE data values are specified for offsets |
| 172 | within the compiled pattern. LINK_SIZE always specifies a number of bytes. The |
| 173 | default value for LINK_SIZE is 2, except for the 32-bit library, where it can |
| 174 | only be 4. The 8-bit library can be compiled to used 3-byte or 4-byte values, |
| 175 | and the 16-bit library can be compiled to use 4-byte values, though this |
| 176 | impairs performance. Specifing a LINK_SIZE larger than 2 for these libraries is |
| 177 | necessary only when patterns whose compiled length is greater than 64K code |
| 178 | units are going to be processed. When a LINK_SIZE value uses more than one code |
| 179 | unit, the most significant unit is first. |
| 180 | |
| 181 | In this description, we assume the "normal" compilation options. Data values |
| 182 | that are counts (e.g. quantifiers) are always two bytes long in 8-bit mode |
| 183 | (most significant byte first), or one code unit in 16-bit and 32-bit modes. |
| 184 | |
| 185 | |
| 186 | Opcodes with no following data |
| 187 | ------------------------------ |
| 188 | |
| 189 | These items are all just one unit long |
| 190 | |
| 191 | OP_END end of pattern |
| 192 | OP_ANY match any one character other than newline |
| 193 | OP_ALLANY match any one character, including newline |
| 194 | OP_ANYBYTE match any single code unit, even in UTF-8/16 mode |
| 195 | OP_SOD match start of data: \A |
| 196 | OP_SOM, start of match (subject + offset): \G |
| 197 | OP_SET_SOM, set start of match (\K) |
| 198 | OP_CIRC ^ (start of data) |
| 199 | OP_CIRCM ^ multiline mode (start of data or after newline) |
| 200 | OP_NOT_WORD_BOUNDARY \W |
| 201 | OP_WORD_BOUNDARY \w |
| 202 | OP_NOT_DIGIT \D |
| 203 | OP_DIGIT \d |
| 204 | OP_NOT_HSPACE \H |
| 205 | OP_HSPACE \h |
| 206 | OP_NOT_WHITESPACE \S |
| 207 | OP_WHITESPACE \s |
| 208 | OP_NOT_VSPACE \V |
| 209 | OP_VSPACE \v |
| 210 | OP_NOT_WORDCHAR \W |
| 211 | OP_WORDCHAR \w |
| 212 | OP_EODN match end of data or newline at end: \Z |
| 213 | OP_EOD match end of data: \z |
| 214 | OP_DOLL $ (end of data, or before final newline) |
| 215 | OP_DOLLM $ multiline mode (end of data or before newline) |
| 216 | OP_EXTUNI match an extended Unicode grapheme cluster |
| 217 | OP_ANYNL match any Unicode newline sequence |
| 218 | |
| 219 | OP_ASSERT_ACCEPT ) |
| 220 | OP_ACCEPT ) These are Perl 5.10's "backtracking control |
| 221 | OP_COMMIT ) verbs". If OP_ACCEPT is inside capturing |
| 222 | OP_FAIL ) parentheses, it may be preceded by one or more |
| 223 | OP_PRUNE ) OP_CLOSE, each followed by a count that |
| 224 | OP_SKIP ) indicates which parentheses must be closed. |
| 225 | OP_THEN ) |
| 226 | |
| 227 | OP_ASSERT_ACCEPT is used when (*ACCEPT) is encountered within an assertion. |
| 228 | This ends the assertion, not the entire pattern match. The assertion (?!) is |
| 229 | always optimized to OP_FAIL. |
| 230 | |
Janis Danisevskis | 8b979b2 | 2016-08-15 16:09:16 +0100 | [diff] [blame] | 231 | OP_ALLANY is used for '.' when PCRE2_DOTALL is set. It is also used for \C in |
| 232 | non-UTF modes and in UTF-32 mode (since one code unit still equals one |
| 233 | character). Another use is for [^] when empty classes are permitted |
| 234 | (PCRE2_ALLOW_EMPTY_CLASS is set). |
| 235 | |
Janis Danisevskis | 53e448c | 2016-03-31 13:35:25 +0100 | [diff] [blame] | 236 | |
| 237 | Backtracking control verbs with optional data |
| 238 | --------------------------------------------- |
| 239 | |
| 240 | (*THEN) without an argument generates the opcode OP_THEN and no following data. |
| 241 | OP_MARK is followed by the mark name, preceded by a length in one code unit, |
| 242 | and followed by a binary zero. For (*PRUNE), (*SKIP), and (*THEN) with |
| 243 | arguments, the opcodes OP_PRUNE_ARG, OP_SKIP_ARG, and OP_THEN_ARG are used, |
| 244 | with the name following in the same format as OP_MARK. |
| 245 | |
| 246 | |
| 247 | Matching literal characters |
| 248 | --------------------------- |
| 249 | |
| 250 | The OP_CHAR opcode is followed by a single character that is to be matched |
| 251 | casefully. For caseless matching, OP_CHARI is used. In UTF-8 or UTF-16 modes, |
| 252 | the character may be more than one code unit long. In UTF-32 mode, characters |
| 253 | are always exactly one code unit long. |
| 254 | |
| 255 | If there is only one character in a character class, OP_CHAR or OP_CHARI is |
| 256 | used for a positive class, and OP_NOT or OP_NOTI for a negative one (that is, |
| 257 | for something like [^a]). |
| 258 | |
| 259 | |
| 260 | Repeating single characters |
| 261 | --------------------------- |
| 262 | |
| 263 | The common repeats (*, +, ?), when applied to a single character, use the |
| 264 | following opcodes, which come in caseful and caseless versions: |
| 265 | |
| 266 | Caseful Caseless |
| 267 | OP_STAR OP_STARI |
| 268 | OP_MINSTAR OP_MINSTARI |
| 269 | OP_POSSTAR OP_POSSTARI |
| 270 | OP_PLUS OP_PLUSI |
| 271 | OP_MINPLUS OP_MINPLUSI |
| 272 | OP_POSPLUS OP_POSPLUSI |
| 273 | OP_QUERY OP_QUERYI |
| 274 | OP_MINQUERY OP_MINQUERYI |
| 275 | OP_POSQUERY OP_POSQUERYI |
| 276 | |
| 277 | Each opcode is followed by the character that is to be repeated. In ASCII or |
| 278 | UTF-32 modes, these are two-code-unit items; in UTF-8 or UTF-16 modes, the |
| 279 | length is variable. Those with "MIN" in their names are the minimizing |
| 280 | versions. Those with "POS" in their names are possessive versions. Other kinds |
| 281 | of repeat make use of these opcodes: |
| 282 | |
| 283 | Caseful Caseless |
| 284 | OP_UPTO OP_UPTOI |
| 285 | OP_MINUPTO OP_MINUPTOI |
| 286 | OP_POSUPTO OP_POSUPTOI |
| 287 | OP_EXACT OP_EXACTI |
| 288 | |
| 289 | Each of these is followed by a count and then the repeated character. The count |
| 290 | is two bytes long in 8-bit mode (most significant byte first), or one code unit |
| 291 | in 16-bit and 32-bit modes. |
| 292 | |
| 293 | OP_UPTO matches from 0 to the given number. A repeat with a non-zero minimum |
| 294 | and a fixed maximum is coded as an OP_EXACT followed by an OP_UPTO (or |
| 295 | OP_MINUPTO or OPT_POSUPTO). |
| 296 | |
| 297 | Another set of matching repeating opcodes (called OP_NOTSTAR, OP_NOTSTARI, |
| 298 | etc.) are used for repeated, negated, single-character classes such as [^a]*. |
| 299 | The normal single-character opcodes (OP_STAR, etc.) are used for repeated |
| 300 | positive single-character classes. |
| 301 | |
| 302 | |
| 303 | Repeating character types |
| 304 | ------------------------- |
| 305 | |
| 306 | Repeats of things like \d are done exactly as for single characters, except |
| 307 | that instead of a character, the opcode for the type (e.g. OP_DIGIT) is stored |
| 308 | in the next code unit. The opcodes are: |
| 309 | |
| 310 | OP_TYPESTAR |
| 311 | OP_TYPEMINSTAR |
| 312 | OP_TYPEPOSSTAR |
| 313 | OP_TYPEPLUS |
| 314 | OP_TYPEMINPLUS |
| 315 | OP_TYPEPOSPLUS |
| 316 | OP_TYPEQUERY |
| 317 | OP_TYPEMINQUERY |
| 318 | OP_TYPEPOSQUERY |
| 319 | OP_TYPEUPTO |
| 320 | OP_TYPEMINUPTO |
| 321 | OP_TYPEPOSUPTO |
| 322 | OP_TYPEEXACT |
| 323 | |
| 324 | |
| 325 | Match by Unicode property |
| 326 | ------------------------- |
| 327 | |
| 328 | OP_PROP and OP_NOTPROP are used for positive and negative matches of a |
| 329 | character by testing its Unicode property (the \p and \P escape sequences). |
| 330 | Each is followed by two code units that encode the desired property as a type |
| 331 | and a value. The types are a set of #defines of the form PT_xxx, and the values |
| 332 | are enumerations of the form ucp_xx, defined in the pcre2_ucp.h source file. |
| 333 | The value is relevant only for PT_GC (General Category), PT_PC (Particular |
| 334 | Category), and PT_SC (Script). |
| 335 | |
| 336 | Repeats of these items use the OP_TYPESTAR etc. set of opcodes, followed by |
| 337 | three code units: OP_PROP or OP_NOTPROP, and then the desired property type and |
| 338 | value. |
| 339 | |
| 340 | |
| 341 | Character classes |
| 342 | ----------------- |
| 343 | |
| 344 | If there is only one character in a class, OP_CHAR or OP_CHARI is used for a |
| 345 | positive class, and OP_NOT or OP_NOTI for a negative one (that is, for |
| 346 | something like [^a]). |
| 347 | |
| 348 | A set of repeating opcodes (called OP_NOTSTAR etc.) are used for repeated, |
| 349 | negated, single-character classes. The normal single-character opcodes |
| 350 | (OP_STAR, etc.) are used for repeated positive single-character classes. |
| 351 | |
| 352 | When there is more than one character in a class, and all the code points are |
| 353 | less than 256, OP_CLASS is used for a positive class, and OP_NCLASS for a |
| 354 | negative one. In either case, the opcode is followed by a 32-byte (16-short, |
| 355 | 8-word) bit map containing a 1 bit for every character that is acceptable. The |
| 356 | bits are counted from the least significant end of each unit. In caseless mode, |
| 357 | bits for both cases are set. |
| 358 | |
| 359 | The reason for having both OP_CLASS and OP_NCLASS is so that, in UTF-8 and |
| 360 | 16-bit and 32-bit modes, subject characters with values greater than 255 can be |
| 361 | handled correctly. For OP_CLASS they do not match, whereas for OP_NCLASS they |
| 362 | do. |
| 363 | |
| 364 | For classes containing characters with values greater than 255 or that contain |
| 365 | \p or \P, OP_XCLASS is used. It optionally uses a bit map if any acceptable |
| 366 | code points are less than 256, followed by a list of pairs (for a range) and/or |
| 367 | single characters and/or properties. In caseless mode, both cases are |
| 368 | explicitly listed. |
| 369 | |
| 370 | OP_XCLASS is followed by a LINK_SIZE value containing the total length of the |
| 371 | opcode and its data. This is followed by a code unit containing flag bits: |
| 372 | XCL_NOT indicates that this is a negative class, and XCL_MAP indicates that a |
| 373 | bit map is present. There follows the bit map, if XCL_MAP is set, and then a |
| 374 | sequence of items coded as follows: |
| 375 | |
| 376 | XCL_END marks the end of the list |
| 377 | XCL_SINGLE one character follows |
| 378 | XCL_RANGE two characters follow |
| 379 | XCL_PROP a Unicode property (type, value) follows |
| 380 | XCL_NOTPROP a Unicode property (type, value) follows |
| 381 | |
| 382 | If a range starts with a code point less than 256 and ends with one greater |
| 383 | than 255, it is split into two ranges, with characters less than 256 being |
| 384 | indicated in the bit map, and the rest with XCL_RANGE. |
| 385 | |
| 386 | When XCL_NOT is set, the bit map, if present, contains bits for characters that |
| 387 | are allowed (exactly as for OP_NCLASS), but the list of items that follow it |
| 388 | specifies characters and properties that are not allowed. |
| 389 | |
| 390 | |
| 391 | Back references |
| 392 | --------------- |
| 393 | |
| 394 | OP_REF (caseful) or OP_REFI (caseless) is followed by a count containing the |
| 395 | reference number when the reference is to a unique capturing group (either by |
| 396 | number or by name). When named groups are used, there may be more than one |
| 397 | group with the same name. In this case, a reference to such a group by name |
| 398 | generates OP_DNREF or OP_DNREFI. These are followed by two counts: the index |
| 399 | (not the byte offset) in the group name table of the first entry for the |
| 400 | required name, followed by the number of groups with the same name. The |
| 401 | matching code can then search for the first one that is set. |
| 402 | |
| 403 | |
| 404 | Repeating character classes and back references |
| 405 | ----------------------------------------------- |
| 406 | |
| 407 | Single-character classes are handled specially (see above). This section |
| 408 | applies to other classes and also to back references. In both cases, the repeat |
| 409 | information follows the base item. The matching code looks at the following |
| 410 | opcode to see if it is one of these: |
| 411 | |
| 412 | OP_CRSTAR |
| 413 | OP_CRMINSTAR |
| 414 | OP_CRPOSSTAR |
| 415 | OP_CRPLUS |
| 416 | OP_CRMINPLUS |
| 417 | OP_CRPOSPLUS |
| 418 | OP_CRQUERY |
| 419 | OP_CRMINQUERY |
| 420 | OP_CRPOSQUERY |
| 421 | OP_CRRANGE |
| 422 | OP_CRMINRANGE |
| 423 | OP_CRPOSRANGE |
| 424 | |
| 425 | All but the last three are single-code-unit items, with no data. The others are |
| 426 | followed by the minimum and maximum repeat counts. |
| 427 | |
| 428 | |
| 429 | Brackets and alternation |
| 430 | ------------------------ |
| 431 | |
| 432 | A pair of non-capturing round brackets is wrapped round each expression at |
| 433 | compile time, so alternation always happens in the context of brackets. |
| 434 | |
| 435 | [Note for North Americans: "bracket" to some English speakers, including |
| 436 | myself, can be round, square, curly, or pointy. Hence this usage rather than |
| 437 | "parentheses".] |
| 438 | |
| 439 | Non-capturing brackets use the opcode OP_BRA, capturing brackets use OP_CBRA. A |
| 440 | bracket opcode is followed by a LINK_SIZE value which gives the offset to the |
| 441 | next alternative OP_ALT or, if there aren't any branches, to the matching |
| 442 | OP_KET opcode. Each OP_ALT is followed by a LINK_SIZE value giving the offset |
| 443 | to the next one, or to the OP_KET opcode. For capturing brackets, the bracket |
| 444 | number is a count that immediately follows the offset. |
| 445 | |
| 446 | OP_KET is used for subpatterns that do not repeat indefinitely, and OP_KETRMIN |
| 447 | and OP_KETRMAX are used for indefinite repetitions, minimally or maximally |
| 448 | respectively (see below for possessive repetitions). All three are followed by |
| 449 | a LINK_SIZE value giving (as a positive number) the offset back to the matching |
| 450 | bracket opcode. |
| 451 | |
| 452 | If a subpattern is quantified such that it is permitted to match zero times, it |
| 453 | is preceded by one of OP_BRAZERO, OP_BRAMINZERO, or OP_SKIPZERO. These are |
| 454 | single-unit opcodes that tell the matcher that skipping the following |
| 455 | subpattern entirely is a valid match. In the case of the first two, not |
| 456 | skipping the pattern is also valid (greedy and non-greedy). The third is used |
| 457 | when a pattern has the quantifier {0,0}. It cannot be entirely discarded, |
| 458 | because it may be called as a subroutine from elsewhere in the pattern. |
| 459 | |
| 460 | A subpattern with an indefinite maximum repetition is replicated in the |
| 461 | compiled data its minimum number of times (or once with OP_BRAZERO if the |
| 462 | minimum is zero), with the final copy terminating with OP_KETRMIN or OP_KETRMAX |
| 463 | as appropriate. |
| 464 | |
| 465 | A subpattern with a bounded maximum repetition is replicated in a nested |
| 466 | fashion up to the maximum number of times, with OP_BRAZERO or OP_BRAMINZERO |
| 467 | before each replication after the minimum, so that, for example, (abc){2,5} is |
| 468 | compiled as (abc)(abc)((abc)((abc)(abc)?)?)?, except that each bracketed group |
| 469 | has the same number. |
| 470 | |
| 471 | When a repeated subpattern has an unbounded upper limit, it is checked to see |
| 472 | whether it could match an empty string. If this is the case, the opcode in the |
| 473 | final replication is changed to OP_SBRA or OP_SCBRA. This tells the matcher |
| 474 | that it needs to check for matching an empty string when it hits OP_KETRMIN or |
| 475 | OP_KETRMAX, and if so, to break the loop. |
| 476 | |
| 477 | |
| 478 | Possessive brackets |
| 479 | ------------------- |
| 480 | |
| 481 | When a repeated group (capturing or non-capturing) is marked as possessive by |
| 482 | the "+" notation, e.g. (abc)++, different opcodes are used. Their names all |
| 483 | have POS on the end, e.g. OP_BRAPOS instead of OP_BRA and OP_SCBRAPOS instead |
| 484 | of OP_SCBRA. The end of such a group is marked by OP_KETRPOS. If the minimum |
| 485 | repetition is zero, the group is preceded by OP_BRAPOSZERO. |
| 486 | |
| 487 | |
| 488 | Once-only (atomic) groups |
| 489 | ------------------------- |
| 490 | |
| 491 | These are just like other subpatterns, but they start with the opcode |
| 492 | OP_ONCE or OP_ONCE_NC. The former is used when there are no capturing brackets |
| 493 | within the atomic group; the latter when there are. The distinction is needed |
| 494 | for when there is a backtrack to before the group - any captures within the |
| 495 | group must be reset, so it is necessary to retain backtracking points inside |
| 496 | the group, even after it is complete, in order to do this. When there are no |
| 497 | captures in an atomic group, all the backtracking can be discarded when it is |
| 498 | complete. This is more efficient, and also uses less stack. |
| 499 | |
| 500 | The check for matching an empty string in an unbounded repeat is handled |
| 501 | entirely at runtime, so there are just these two opcodes for atomic groups. |
| 502 | |
| 503 | |
| 504 | Assertions |
| 505 | ---------- |
| 506 | |
| 507 | Forward assertions are also just like other subpatterns, but starting with one |
| 508 | of the opcodes OP_ASSERT or OP_ASSERT_NOT. Backward assertions use the opcodes |
| 509 | OP_ASSERTBACK and OP_ASSERTBACK_NOT, and the first opcode inside the assertion |
| 510 | is OP_REVERSE, followed by a count of the number of characters to move back the |
| 511 | pointer in the subject string. In ASCII or UTF-32 mode, the count is also the |
| 512 | number of code units, but in UTF-8/16 mode each character may occupy more than |
| 513 | one code unit. A separate count is present in each alternative of a lookbehind |
| 514 | assertion, allowing them to have different (but fixed) lengths. |
| 515 | |
| 516 | |
| 517 | Conditional subpatterns |
| 518 | ----------------------- |
| 519 | |
| 520 | These are like other subpatterns, but they start with the opcode OP_COND, or |
| 521 | OP_SCOND for one that might match an empty string in an unbounded repeat. |
| 522 | |
| 523 | If the condition is a back reference, this is stored at the start of the |
| 524 | subpattern using the opcode OP_CREF followed by a count containing the |
| 525 | reference number, provided that the reference is to a unique capturing group. |
| 526 | If the reference was by name and there is more than one group with that name, |
| 527 | OP_DNCREF is used instead. It is followed by two counts: the index in the group |
| 528 | names table, and the number of groups with the same name. The allows the |
| 529 | matcher to check if any group with the given name is set. |
| 530 | |
| 531 | If the condition is "in recursion" (coded as "(?(R)"), or "in recursion of |
| 532 | group x" (coded as "(?(Rx)"), the group number is stored at the start of the |
| 533 | subpattern using the opcode OP_RREF (with a value of RREF_ANY (0xffff) for "the |
| 534 | whole pattern") or OP_DNRREF (with data as for OP_DNCREF). |
| 535 | |
| 536 | For a DEFINE condition, OP_FALSE is used (with no associated data). During |
| 537 | compilation, however, a DEFINE condition is coded as OP_DEFINE so that, when |
| 538 | the conditional group is complete, there can be a check to ensure that it |
| 539 | contains only one top-level branch. Once this has happened, the opcode is |
| 540 | changed to OP_FALSE, so the matcher never sees OP_DEFINE. |
| 541 | |
| 542 | There is a special PCRE2-specific condition of the form (VERSION[>]=x.y), which |
| 543 | tests the PCRE2 version number. This compiles into one of the opcodes OP_TRUE |
| 544 | or OP_FALSE. |
| 545 | |
| 546 | If a condition is not a back reference, recursion test, DEFINE, or VERSION, it |
| 547 | must start with an assertion, whose opcode normally immediately follows OP_COND |
| 548 | or OP_SCOND. However, if automatic callouts are enabled, a callout is inserted |
| 549 | immediately before the assertion. It is also possible to insert a manual |
| 550 | callout at this point. Only assertion conditions may have callouts preceding |
| 551 | the condition. |
| 552 | |
| 553 | A condition that is the negative assertion (?!) is optimized to OP_FAIL in all |
| 554 | parts of the pattern, so this is another opcode that may appear as a condition. |
| 555 | It is treated the same as OP_FALSE. |
| 556 | |
| 557 | |
| 558 | Recursion |
| 559 | --------- |
| 560 | |
| 561 | Recursion either matches the current pattern, or some subexpression. The opcode |
| 562 | OP_RECURSE is followed by a LINK_SIZE value that is the offset to the starting |
| 563 | bracket from the start of the whole pattern. OP_RECURSE is also used for |
| 564 | "subroutine" calls, even though they are not strictly a recursion. Repeated |
| 565 | recursions are automatically wrapped inside OP_ONCE brackets, because otherwise |
| 566 | some patterns broke them. A non-repeated recursion is not wrapped in OP_ONCE |
| 567 | brackets, but it is nevertheless still treated as an atomic group. |
| 568 | |
| 569 | |
| 570 | Callout |
| 571 | ------- |
| 572 | |
| 573 | A callout can nowadays have either a numerical argument or a string argument. |
| 574 | These use OP_CALLOUT or OP_CALLOUT_STR, respectively. In each case these are |
| 575 | followed by two LINK_SIZE values giving the offset in the pattern string to the |
| 576 | start of the following item, and another count giving the length of this item. |
| 577 | These values make it possible for pcre2test to output useful tracing |
| 578 | information using callouts. |
| 579 | |
| 580 | In the case of a numeric callout, after these two values there is a single code |
| 581 | unit containing the callout number, in the range 0-255, with 255 being used for |
| 582 | callouts that are automatically inserted as a result of the PCRE2_AUTO_CALLOUT |
| 583 | option. Thus, this opcode item is of fixed length: |
| 584 | |
| 585 | [OP_CALLOUT] [PATTERN_OFFSET] [PATTERN_LENGTH] [NUMBER] |
| 586 | |
| 587 | For callouts with string arguments, OP_CALLOUT_STR has three more data items: |
| 588 | a LINK_SIZE value giving the complete length of the entire opcode item, a |
| 589 | LINK_SIZE item containing the offset within the pattern string to the start of |
| 590 | the string argument, and the string itself, preceded by its starting delimiter |
| 591 | and followed by a binary zero. When a callout function is called, a pointer to |
| 592 | the actual string is passed, but the delimiter can be accessed as string[-1] if |
| 593 | the application needs it. In the 8-bit library, the callout in /X(?C'abc')Y/ is |
| 594 | compiled as the following bytes (decimal numbers represent binary values): |
| 595 | |
| 596 | [OP_CALLOUT] [0] [10] [0] [1] [0] [14] [0] [5] ['] [a] [b] [c] [0] |
| 597 | -------- ------- -------- ------- |
| 598 | | | | | |
| 599 | ------- LINK_SIZE items ------ |
| 600 | |
| 601 | Opcode table checking |
| 602 | --------------------- |
| 603 | |
| 604 | The last opcode that is defined in pcre2_internal.h is OP_TABLE_LENGTH. This is |
| 605 | not a real opcode, but is used to check that tables indexed by opcode are the |
| 606 | correct length, in order to catch updating errors. |
| 607 | |
| 608 | Philip Hazel |
Janis Danisevskis | 8b979b2 | 2016-08-15 16:09:16 +0100 | [diff] [blame] | 609 | June 2016 |