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