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 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 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 609 June 2016 610
