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