1Technical Notes about PCRE 2-------------------------- 3 4These are very rough technical notes that record potentially useful information 5about PCRE internals. For information about testing PCRE, see the pcretest 6documentation and the comment at the head of the RunTest file. 7 8 9Historical note 1 10----------------- 11 12Many years ago I implemented some regular expression functions to an algorithm 13suggested by Martin Richards. These were not Unix-like in form, and were quite 14restricted in what they could do by comparison with Perl. The interesting part 15about the algorithm was that the amount of space required to hold the compiled 16form of an expression was known in advance. The code to apply an expression did 17not operate by backtracking, as the original Henry Spencer code and current 18Perl code does, but instead checked all possibilities simultaneously by keeping 19a list of current states and checking all of them as it advanced through the 20subject string. In the terminology of Jeffrey Friedl's book, it was a "DFA 21algorithm", though it was not a traditional Finite State Machine (FSM). When 22the pattern was all used up, all remaining states were possible matches, and 23the one matching the longest subset of the subject string was chosen. This did 24not necessarily maximize the individual wild portions of the pattern, as is 25expected in Unix and Perl-style regular expressions. 26 27 28Historical note 2 29----------------- 30 31By contrast, the code originally written by Henry Spencer (which was 32subsequently heavily modified for Perl) compiles the expression twice: once in 33a dummy mode in order to find out how much store will be needed, and then for 34real. (The Perl version probably doesn't do this any more; I'm talking about 35the original library.) The execution function operates by backtracking and 36maximizing (or, optionally, minimizing in Perl) the amount of the subject that 37matches individual wild portions of the pattern. This is an "NFA algorithm" in 38Friedl's terminology. 39 40 41OK, here's the real stuff 42------------------------- 43 44For the set of functions that form the "basic" PCRE library (which are 45unrelated to those mentioned above), I tried at first to invent an algorithm 46that used an amount of store bounded by a multiple of the number of characters 47in the pattern, to save on compiling time. However, because of the greater 48complexity in Perl regular expressions, I couldn't do this. In any case, a 49first pass through the pattern is helpful for other reasons. 50 51 52Support for 16-bit data strings 53------------------------------- 54 55From release 8.30, PCRE supports 16-bit as well as 8-bit data strings, by being 56compilable in either 8-bit or 16-bit modes, or both. Thus, two different 57libraries can be created. In the description that follows, the word "short" is 58used for a 16-bit data quantity, and the word "unit" is used for a quantity 59that is a byte in 8-bit mode and a short in 16-bit mode. However, so as not to 60over-complicate the text, the names of PCRE functions are given in 8-bit form 61only. 62 63 64Computing the memory requirement: how it was 65-------------------------------------------- 66 67Up to and including release 6.7, PCRE worked by running a very degenerate first 68pass to calculate a maximum store size, and then a second pass to do the real 69compile - which might use a bit less than the predicted amount of memory. The 70idea was that this would turn out faster than the Henry Spencer code because 71the first pass is degenerate and the second pass can just store stuff straight 72into the vector, which it knows is big enough. 73 74 75Computing the memory requirement: how it is 76------------------------------------------- 77 78By the time I was working on a potential 6.8 release, the degenerate first pass 79had become very complicated and hard to maintain. Indeed one of the early 80things I did for 6.8 was to fix Yet Another Bug in the memory computation. Then 81I had a flash of inspiration as to how I could run the real compile function in 82a "fake" mode that enables it to compute how much memory it would need, while 83actually only ever using a few hundred bytes of working memory, and without too 84many tests of the mode that might slow it down. So I refactored the compiling 85functions to work this way. This got rid of about 600 lines of source. It 86should make future maintenance and development easier. As this was such a major 87change, I never released 6.8, instead upping the number to 7.0 (other quite 88major changes were also present in the 7.0 release). 89 90A side effect of this work was that the previous limit of 200 on the nesting 91depth of parentheses was removed. However, there is a downside: pcre_compile() 92runs more slowly than before (30% or more, depending on the pattern) because it 93is doing a full analysis of the pattern. My hope was that this would not be a 94big issue, and in the event, nobody has commented on it. 95 96 97Traditional matching function 98----------------------------- 99 100The "traditional", and original, matching function is called pcre_exec(), and 101it implements an NFA algorithm, similar to the original Henry Spencer algorithm 102and the way that Perl works. This is not surprising, since it is intended to be 103as compatible with Perl as possible. This is the function most users of PCRE 104will use most of the time. From release 8.20, if PCRE is compiled with 105just-in-time (JIT) support, and studying a compiled pattern with JIT is 106successful, the JIT code is run instead of the normal pcre_exec() code, but the 107result is the same. 108 109 110Supplementary matching function 111------------------------------- 112 113From PCRE 6.0, there is also a supplementary matching function called 114pcre_dfa_exec(). This implements a DFA matching algorithm that searches 115simultaneously for all possible matches that start at one point in the subject 116string. (Going back to my roots: see Historical Note 1 above.) This function 117intreprets the same compiled pattern data as pcre_exec(); however, not all the 118facilities are available, and those that are do not always work in quite the 119same way. See the user documentation for details. 120 121The algorithm that is used for pcre_dfa_exec() is not a traditional FSM, 122because it may have a number of states active at one time. More work would be 123needed at compile time to produce a traditional FSM where only one state is 124ever active at once. I believe some other regex matchers work this way. 125 126 127Changeable options 128------------------ 129 130The /i, /m, or /s options (PCRE_CASELESS, PCRE_MULTILINE, PCRE_DOTALL) may 131change in the middle of patterns. From PCRE 8.13, their processing is handled 132entirely at compile time by generating different opcodes for the different 133settings. The runtime functions do not need to keep track of an options state 134any more. 135 136 137Format of compiled patterns 138--------------------------- 139 140The compiled form of a pattern is a vector of units (bytes in 8-bit mode, or 141shorts in 16-bit mode), containing items of variable length. The first unit in 142an item contains an opcode, and the length of the item is either implicit in 143the opcode or contained in the data that follows it. 144 145In many cases listed below, LINK_SIZE data values are specified for offsets 146within the compiled pattern. LINK_SIZE always specifies a number of bytes. The 147default value for LINK_SIZE is 2, but PCRE can be compiled to use 3-byte or 1484-byte values for these offsets, although this impairs the performance. (3-byte 149LINK_SIZE values are available only in 8-bit mode.) Specifing a LINK_SIZE 150larger than 2 is necessary only when patterns whose compiled length is greater 151than 64K are going to be processed. In this description, we assume the "normal" 152compilation options. Data values that are counts (e.g. for quantifiers) are 153always just two bytes long (one short in 16-bit mode). 154 155Opcodes with no following data 156------------------------------ 157 158These items are all just one unit long 159 160 OP_END end of pattern 161 OP_ANY match any one character other than newline 162 OP_ALLANY match any one character, including newline 163 OP_ANYBYTE match any single byte, even in UTF-8 mode 164 OP_SOD match start of data: \A 165 OP_SOM, start of match (subject + offset): \G 166 OP_SET_SOM, set start of match (\K) 167 OP_CIRC ^ (start of data) 168 OP_CIRCM ^ multiline mode (start of data or after newline) 169 OP_NOT_WORD_BOUNDARY \W 170 OP_WORD_BOUNDARY \w 171 OP_NOT_DIGIT \D 172 OP_DIGIT \d 173 OP_NOT_HSPACE \H 174 OP_HSPACE \h 175 OP_NOT_WHITESPACE \S 176 OP_WHITESPACE \s 177 OP_NOT_VSPACE \V 178 OP_VSPACE \v 179 OP_NOT_WORDCHAR \W 180 OP_WORDCHAR \w 181 OP_EODN match end of data or \n at end: \Z 182 OP_EOD match end of data: \z 183 OP_DOLL $ (end of data, or before final newline) 184 OP_DOLLM $ multiline mode (end of data or before newline) 185 OP_EXTUNI match an extended Unicode character 186 OP_ANYNL match any Unicode newline sequence 187 188 OP_ACCEPT ) These are Perl 5.10's "backtracking control 189 OP_COMMIT ) verbs". If OP_ACCEPT is inside capturing 190 OP_FAIL ) parentheses, it may be preceded by one or more 191 OP_PRUNE ) OP_CLOSE, followed by a 2-byte number, 192 OP_SKIP ) indicating which parentheses must be closed. 193 194 195Backtracking control verbs with (optional) data 196----------------------------------------------- 197 198(*THEN) without an argument generates the opcode OP_THEN and no following data. 199OP_MARK is followed by the mark name, preceded by a one-unit length, and 200followed by a binary zero. For (*PRUNE), (*SKIP), and (*THEN) with arguments, 201the opcodes OP_PRUNE_ARG, OP_SKIP_ARG, and OP_THEN_ARG are used, with the name 202following in the same format. 203 204 205Matching literal characters 206--------------------------- 207 208The OP_CHAR opcode is followed by a single character that is to be matched 209casefully. For caseless matching, OP_CHARI is used. In UTF-8 or UTF-16 modes, 210the character may be more than one unit long. 211 212 213Repeating single characters 214--------------------------- 215 216The common repeats (*, +, ?), when applied to a single character, use the 217following opcodes, which come in caseful and caseless versions: 218 219 Caseful Caseless 220 OP_STAR OP_STARI 221 OP_MINSTAR OP_MINSTARI 222 OP_POSSTAR OP_POSSTARI 223 OP_PLUS OP_PLUSI 224 OP_MINPLUS OP_MINPLUSI 225 OP_POSPLUS OP_POSPLUSI 226 OP_QUERY OP_QUERYI 227 OP_MINQUERY OP_MINQUERYI 228 OP_POSQUERY OP_POSQUERYI 229 230Each opcode is followed by the character that is to be repeated. In ASCII mode, 231these are two-unit items; in UTF-8 or UTF-16 modes, the length is variable. 232Those with "MIN" in their names are the minimizing versions. Those with "POS" 233in their names are possessive versions. Other repeats make use of these 234opcodes: 235 236 Caseful Caseless 237 OP_UPTO OP_UPTOI 238 OP_MINUPTO OP_MINUPTOI 239 OP_POSUPTO OP_POSUPTOI 240 OP_EXACT OP_EXACTI 241 242Each of these is followed by a two-byte (one short) count (most significant 243byte first in 8-bit mode) and then the repeated character. OP_UPTO matches from 2440 to the given number. A repeat with a non-zero minimum and a fixed maximum is 245coded as an OP_EXACT followed by an OP_UPTO (or OP_MINUPTO or OPT_POSUPTO). 246 247 248Repeating character types 249------------------------- 250 251Repeats of things like \d are done exactly as for single characters, except 252that instead of a character, the opcode for the type is stored in the data 253unit. The opcodes are: 254 255 OP_TYPESTAR 256 OP_TYPEMINSTAR 257 OP_TYPEPOSSTAR 258 OP_TYPEPLUS 259 OP_TYPEMINPLUS 260 OP_TYPEPOSPLUS 261 OP_TYPEQUERY 262 OP_TYPEMINQUERY 263 OP_TYPEPOSQUERY 264 OP_TYPEUPTO 265 OP_TYPEMINUPTO 266 OP_TYPEPOSUPTO 267 OP_TYPEEXACT 268 269 270Match by Unicode property 271------------------------- 272 273OP_PROP and OP_NOTPROP are used for positive and negative matches of a 274character by testing its Unicode property (the \p and \P escape sequences). 275Each is followed by two units that encode the desired property as a type and a 276value. 277 278Repeats of these items use the OP_TYPESTAR etc. set of opcodes, followed by 279three units: OP_PROP or OP_NOTPROP, and then the desired property type and 280value. 281 282 283Character classes 284----------------- 285 286If there is only one character in the class, OP_CHAR or OP_CHARI is used for a 287positive class, and OP_NOT or OP_NOTI for a negative one (that is, for 288something like [^a]). 289 290Another set of 13 repeating opcodes (called OP_NOTSTAR etc.) are used for 291repeated, negated, single-character classes. The normal single-character 292opcodes (OP_STAR, etc.) are used for repeated positive single-character 293classes. 294 295When there is more than one character in a class and all the characters are 296less than 256, OP_CLASS is used for a positive class, and OP_NCLASS for a 297negative one. In either case, the opcode is followed by a 32-byte (16-short) 298bit map containing a 1 bit for every character that is acceptable. The bits are 299counted from the least significant end of each unit. In caseless mode, bits for 300both cases are set. 301 302The reason for having both OP_CLASS and OP_NCLASS is so that, in UTF-8/16 mode, 303subject characters with values greater than 255 can be handled correctly. For 304OP_CLASS they do not match, whereas for OP_NCLASS they do. 305 306For classes containing characters with values greater than 255, OP_XCLASS is 307used. It optionally uses a bit map (if any characters lie within it), followed 308by a list of pairs (for a range) and single characters. In caseless mode, both 309cases are explicitly listed. There is a flag character than indicates whether 310it is a positive or a negative class. 311 312 313Back references 314--------------- 315 316OP_REF (caseful) or OP_REFI (caseless) is followed by two bytes (one short) 317containing the reference number. 318 319 320Repeating character classes and back references 321----------------------------------------------- 322 323Single-character classes are handled specially (see above). This section 324applies to OP_CLASS and OP_REF[I]. In both cases, the repeat information 325follows the base item. The matching code looks at the following opcode to see 326if it is one of 327 328 OP_CRSTAR 329 OP_CRMINSTAR 330 OP_CRPLUS 331 OP_CRMINPLUS 332 OP_CRQUERY 333 OP_CRMINQUERY 334 OP_CRRANGE 335 OP_CRMINRANGE 336 337All but the last two are just single-unit items. The others are followed by 338four bytes (two shorts) of data, comprising the minimum and maximum repeat 339counts. There are no special possessive opcodes for these repeats; a possessive 340repeat is compiled into an atomic group. 341 342 343Brackets and alternation 344------------------------ 345 346A pair of non-capturing (round) brackets is wrapped round each expression at 347compile time, so alternation always happens in the context of brackets. 348 349[Note for North Americans: "bracket" to some English speakers, including 350myself, can be round, square, curly, or pointy. Hence this usage rather than 351"parentheses".] 352 353Non-capturing brackets use the opcode OP_BRA. Originally PCRE was limited to 99 354capturing brackets and it used a different opcode for each one. From release 3553.5, the limit was removed by putting the bracket number into the data for 356higher-numbered brackets. From release 7.0 all capturing brackets are handled 357this way, using the single opcode OP_CBRA. 358 359A bracket opcode is followed by LINK_SIZE bytes which give the offset to the 360next alternative OP_ALT or, if there aren't any branches, to the matching 361OP_KET opcode. Each OP_ALT is followed by LINK_SIZE bytes giving the offset to 362the next one, or to the OP_KET opcode. For capturing brackets, the bracket 363number immediately follows the offset, always as a 2-byte (one short) item. 364 365OP_KET is used for subpatterns that do not repeat indefinitely, and 366OP_KETRMIN and OP_KETRMAX are used for indefinite repetitions, minimally or 367maximally respectively (see below for possessive repetitions). All three are 368followed by LINK_SIZE bytes giving (as a positive number) the offset back to 369the matching bracket opcode. 370 371If a subpattern is quantified such that it is permitted to match zero times, it 372is preceded by one of OP_BRAZERO, OP_BRAMINZERO, or OP_SKIPZERO. These are 373single-unit opcodes that tell the matcher that skipping the following 374subpattern entirely is a valid branch. In the case of the first two, not 375skipping the pattern is also valid (greedy and non-greedy). The third is used 376when a pattern has the quantifier {0,0}. It cannot be entirely discarded, 377because it may be called as a subroutine from elsewhere in the regex. 378 379A subpattern with an indefinite maximum repetition is replicated in the 380compiled data its minimum number of times (or once with OP_BRAZERO if the 381minimum is zero), with the final copy terminating with OP_KETRMIN or OP_KETRMAX 382as appropriate. 383 384A subpattern with a bounded maximum repetition is replicated in a nested 385fashion up to the maximum number of times, with OP_BRAZERO or OP_BRAMINZERO 386before each replication after the minimum, so that, for example, (abc){2,5} is 387compiled as (abc)(abc)((abc)((abc)(abc)?)?)?, except that each bracketed group 388has the same number. 389 390When a repeated subpattern has an unbounded upper limit, it is checked to see 391whether it could match an empty string. If this is the case, the opcode in the 392final replication is changed to OP_SBRA or OP_SCBRA. This tells the matcher 393that it needs to check for matching an empty string when it hits OP_KETRMIN or 394OP_KETRMAX, and if so, to break the loop. 395 396Possessive brackets 397------------------- 398 399When a repeated group (capturing or non-capturing) is marked as possessive by 400the "+" notation, e.g. (abc)++, different opcodes are used. Their names all 401have POS on the end, e.g. OP_BRAPOS instead of OP_BRA and OP_SCPBRPOS instead 402of OP_SCBRA. The end of such a group is marked by OP_KETRPOS. If the minimum 403repetition is zero, the group is preceded by OP_BRAPOSZERO. 404 405 406Assertions 407---------- 408 409Forward assertions are just like other subpatterns, but starting with one of 410the opcodes OP_ASSERT or OP_ASSERT_NOT. Backward assertions use the opcodes 411OP_ASSERTBACK and OP_ASSERTBACK_NOT, and the first opcode inside the assertion 412is OP_REVERSE, followed by a two byte (one short) count of the number of 413characters to move back the pointer in the subject string. In ASCII mode, the 414count is a number of units, but in UTF-8/16 mode each character may occupy more 415than one unit. A separate count is present in each alternative of a lookbehind 416assertion, allowing them to have different fixed lengths. 417 418 419Once-only (atomic) subpatterns 420------------------------------ 421 422These are also just like other subpatterns, but they start with the opcode 423OP_ONCE. The check for matching an empty string in an unbounded repeat is 424handled entirely at runtime, so there is just this one opcode. 425 426 427Conditional subpatterns 428----------------------- 429 430These are like other subpatterns, but they start with the opcode OP_COND, or 431OP_SCOND for one that might match an empty string in an unbounded repeat. If 432the condition is a back reference, this is stored at the start of the 433subpattern using the opcode OP_CREF followed by two bytes (one short) 434containing the reference number. OP_NCREF is used instead if the reference was 435generated by name (so that the runtime code knows to check for duplicate 436names). 437 438If the condition is "in recursion" (coded as "(?(R)"), or "in recursion of 439group x" (coded as "(?(Rx)"), the group number is stored at the start of the 440subpattern using the opcode OP_RREF or OP_NRREF (cf OP_NCREF), and a value of 441zero for "the whole pattern". For a DEFINE condition, just the single unit 442OP_DEF is used (it has no associated data). Otherwise, a conditional subpattern 443always starts with one of the assertions. 444 445 446Recursion 447--------- 448 449Recursion either matches the current regex, or some subexpression. The opcode 450OP_RECURSE is followed by an value which is the offset to the starting bracket 451from the start of the whole pattern. From release 6.5, OP_RECURSE is 452automatically wrapped inside OP_ONCE brackets (because otherwise some patterns 453broke it). OP_RECURSE is also used for "subroutine" calls, even though they 454are not strictly a recursion. 455 456 457Callout 458------- 459 460OP_CALLOUT is followed by one unit of data that holds a callout number in the 461range 0 to 254 for manual callouts, or 255 for an automatic callout. In both 462cases there follows a two-byte (one short) value giving the offset in the 463pattern to the start of the following item, and another two-byte (one short) 464item giving the length of the next item. 465 466 467Philip Hazel 468February 2012 469