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