+++ /dev/null
-Technical Notes about PCRE
---------------------------
-
-These are very rough technical notes that record potentially useful information
-about PCRE internals.
-
-Historical note 1
------------------
-
-Many years ago I implemented some regular expression functions to an algorithm
-suggested by Martin Richards. These were not Unix-like in form, and were quite
-restricted in what they could do by comparison with Perl. The interesting part
-about the algorithm was that the amount of space required to hold the compiled
-form of an expression was known in advance. The code to apply an expression did
-not operate by backtracking, as the original Henry Spencer code and current
-Perl code does, but instead checked all possibilities simultaneously by keeping
-a list of current states and checking all of them as it advanced through the
-subject string. In the terminology of Jeffrey Friedl's book, it was a "DFA
-algorithm", though it was not a traditional Finite State Machine (FSM). When
-the pattern was all used up, all remaining states were possible matches, and
-the one matching the longest subset of the subject string was chosen. This did
-not necessarily maximize the individual wild portions of the pattern, as is
-expected in Unix and Perl-style regular expressions.
-
-Historical note 2
------------------
-
-By contrast, the code originally written by Henry Spencer (which was
-subsequently heavily modified for Perl) compiles the expression twice: once in
-a dummy mode in order to find out how much store will be needed, and then for
-real. (The Perl version probably doesn't do this any more; I'm talking about
-the original library.) The execution function operates by backtracking and
-maximizing (or, optionally, minimizing in Perl) the amount of the subject that
-matches individual wild portions of the pattern. This is an "NFA algorithm" in
-Friedl's terminology.
-
-OK, here's the real stuff
--------------------------
-
-For the set of functions that form the "basic" PCRE library (which are
-unrelated to those mentioned above), I tried at first to invent an algorithm
-that used an amount of store bounded by a multiple of the number of characters
-in the pattern, to save on compiling time. However, because of the greater
-complexity in Perl regular expressions, I couldn't do this. In any case, a
-first pass through the pattern is helpful for other reasons.
-
-Computing the memory requirement: how it was
---------------------------------------------
-
-Up to and including release 6.7, PCRE worked by running a very degenerate first
-pass to calculate a maximum store size, and then a second pass to do the real
-compile - which might use a bit less than the predicted amount of memory. The
-idea was that this would turn out faster than the Henry Spencer code because
-the first pass is degenerate and the second pass can just store stuff straight
-into the vector, which it knows is big enough.
-
-Computing the memory requirement: how it is
--------------------------------------------
-
-By the time I was working on a potential 6.8 release, the degenerate first pass
-had become very complicated and hard to maintain. Indeed one of the early
-things I did for 6.8 was to fix Yet Another Bug in the memory computation. Then
-I had a flash of inspiration as to how I could run the real compile function in
-a "fake" mode that enables it to compute how much memory it would need, while
-actually only ever using a few hundred bytes of working memory, and without too
-many tests of the mode that might slow it down. So I re-factored the compiling
-functions to work this way. This got rid of about 600 lines of source. It
-should make future maintenance and development easier. As this was such a major
-change, I never released 6.8, instead upping the number to 7.0 (other quite
-major changes were also present in the 7.0 release).
-
-A side effect of this work was that the previous limit of 200 on the nesting
-depth of parentheses was removed. However, there is a downside: pcre_compile()
-runs more slowly than before (30% or more, depending on the pattern) because it
-is doing a full analysis of the pattern. My hope was that this would not be a
-big issue, and in the event, nobody has commented on it.
-
-Traditional matching function
------------------------------
-
-The "traditional", and original, matching function is called pcre_exec(), and
-it implements an NFA algorithm, similar to the original Henry Spencer algorithm
-and the way that Perl works. This is not surprising, since it is intended to be
-as compatible with Perl as possible. This is the function most users of PCRE
-will use most of the time.
-
-Supplementary matching function
--------------------------------
-
-From PCRE 6.0, there is also a supplementary matching function called
-pcre_dfa_exec(). This implements a DFA matching algorithm that searches
-simultaneously for all possible matches that start at one point in the subject
-string. (Going back to my roots: see Historical Note 1 above.) This function
-intreprets the same compiled pattern data as pcre_exec(); however, not all the
-facilities are available, and those that are do not always work in quite the
-same way. See the user documentation for details.
-
-The algorithm that is used for pcre_dfa_exec() is not a traditional FSM,
-because it may have a number of states active at one time. More work would be
-needed at compile time to produce a traditional FSM where only one state is
-ever active at once. I believe some other regex matchers work this way.
-
-
-Format of compiled patterns
----------------------------
-
-The compiled form of a pattern is a vector of bytes, containing items of
-variable length. The first byte in an item is an opcode, and the length of the
-item is either implicit in the opcode or contained in the data bytes that
-follow it.
-
-In many cases below LINK_SIZE data values are specified for offsets within the
-compiled pattern. The default value for LINK_SIZE is 2, but PCRE can be
-compiled to use 3-byte or 4-byte values for these offsets (impairing the
-performance). This is necessary only when patterns whose compiled length is
-greater than 64K are going to be processed. In this description, we assume the
-"normal" compilation options. Data values that are counts (e.g. for
-quantifiers) are always just two bytes long.
-
-A list of the opcodes follows:
-
-
-Opcodes with no following data
-------------------------------
-
-These items are all just one byte long
-
- OP_END end of pattern
- OP_ANY match any one character other than newline
- OP_ALLANY match any one character, including newline
- OP_ANYBYTE match any single byte, even in UTF-8 mode
- OP_SOD match start of data: \A
- OP_SOM, start of match (subject + offset): \G
- OP_SET_SOM, set start of match (\K)
- OP_CIRC ^ (start of data, or after \n in multiline)
- OP_NOT_WORD_BOUNDARY \W
- OP_WORD_BOUNDARY \w
- OP_NOT_DIGIT \D
- OP_DIGIT \d
- OP_NOT_HSPACE \H
- OP_HSPACE \h
- OP_NOT_WHITESPACE \S
- OP_WHITESPACE \s
- OP_NOT_VSPACE \V
- OP_VSPACE \v
- OP_NOT_WORDCHAR \W
- OP_WORDCHAR \w
- OP_EODN match end of data or \n at end: \Z
- OP_EOD match end of data: \z
- OP_DOLL $ (end of data, or before \n in multiline)
- OP_EXTUNI match an extended Unicode character
- OP_ANYNL match any Unicode newline sequence
-
- OP_ACCEPT ) These are Perl 5.10's "backtracking
- OP_COMMIT ) control verbs". If OP_ACCEPT is inside
- OP_FAIL ) capturing parentheses, it may be preceded
- OP_PRUNE ) by one or more OP_CLOSE, followed by a 2-byte
- OP_SKIP ) number, indicating which parentheses must be
- OP_THEN ) closed.
-
-
-Repeating single characters
----------------------------
-
-The common repeats (*, +, ?) when applied to a single character use the
-following opcodes:
-
- OP_STAR
- OP_MINSTAR
- OP_POSSTAR
- OP_PLUS
- OP_MINPLUS
- OP_POSPLUS
- OP_QUERY
- OP_MINQUERY
- OP_POSQUERY
-
-In ASCII mode, these are two-byte items; in UTF-8 mode, the length is variable.
-Those with "MIN" in their name are the minimizing versions. Those with "POS" in
-their names are possessive versions. Each is followed by the character that is
-to be repeated. Other repeats make use of
-
- OP_UPTO
- OP_MINUPTO
- OP_POSUPTO
- OP_EXACT
-
-which are followed by a two-byte count (most significant first) and the
-repeated character. OP_UPTO matches from 0 to the given number. A repeat with a
-non-zero minimum and a fixed maximum is coded as an OP_EXACT followed by an
-OP_UPTO (or OP_MINUPTO or OPT_POSUPTO).
-
-
-Repeating character types
--------------------------
-
-Repeats of things like \d are done exactly as for single characters, except
-that instead of a character, the opcode for the type is stored in the data
-byte. The opcodes are:
-
- OP_TYPESTAR
- OP_TYPEMINSTAR
- OP_TYPEPOSSTAR
- OP_TYPEPLUS
- OP_TYPEMINPLUS
- OP_TYPEPOSPLUS
- OP_TYPEQUERY
- OP_TYPEMINQUERY
- OP_TYPEPOSQUERY
- OP_TYPEUPTO
- OP_TYPEMINUPTO
- OP_TYPEPOSUPTO
- OP_TYPEEXACT
-
-
-Match by Unicode property
--------------------------
-
-OP_PROP and OP_NOTPROP are used for positive and negative matches of a
-character by testing its Unicode property (the \p and \P escape sequences).
-Each is followed by two bytes that encode the desired property as a type and a
-value.
-
-Repeats of these items use the OP_TYPESTAR etc. set of opcodes, followed by
-three bytes: OP_PROP or OP_NOTPROP and then the desired property type and
-value.
-
-
-Matching literal characters
----------------------------
-
-The OP_CHAR opcode is followed by a single character that is to be matched
-casefully. For caseless matching, OP_CHARNC is used. In UTF-8 mode, the
-character may be more than one byte long. (Earlier versions of PCRE used
-multi-character strings, but this was changed to allow some new features to be
-added.)
-
-
-Character classes
------------------
-
-If there is only one character, OP_CHAR or OP_CHARNC is used for a positive
-class, and OP_NOT for a negative one (that is, for something like [^a]).
-However, in UTF-8 mode, the use of OP_NOT applies only to characters with
-values < 128, because OP_NOT is confined to single bytes.
-
-Another set of repeating opcodes (OP_NOTSTAR etc.) are used for a repeated,
-negated, single-character class. The normal ones (OP_STAR etc.) are used for a
-repeated positive single-character class.
-
-When there's more than one character in a class and all the characters are less
-than 256, OP_CLASS is used for a positive class, and OP_NCLASS for a negative
-one. In either case, the opcode is followed by a 32-byte bit map containing a 1
-bit for every character that is acceptable. The bits are counted from the least
-significant end of each byte.
-
-The reason for having both OP_CLASS and OP_NCLASS is so that, in UTF-8 mode,
-subject characters with values greater than 256 can be handled correctly. For
-OP_CLASS they don't match, whereas for OP_NCLASS they do.
-
-For classes containing characters with values > 255, OP_XCLASS is used. It
-optionally uses a bit map (if any characters lie within it), followed by a list
-of pairs and single characters. There is a flag character than indicates
-whether it's a positive or a negative class.
-
-
-Back references
----------------
-
-OP_REF is followed by two bytes containing the reference number.
-
-
-Repeating character classes and back references
------------------------------------------------
-
-Single-character classes are handled specially (see above). This section
-applies to OP_CLASS and OP_REF. In both cases, the repeat information follows
-the base item. The matching code looks at the following opcode to see if it is
-one of
-
- OP_CRSTAR
- OP_CRMINSTAR
- OP_CRPLUS
- OP_CRMINPLUS
- OP_CRQUERY
- OP_CRMINQUERY
- OP_CRRANGE
- OP_CRMINRANGE
-
-All but the last two are just single-byte items. The others are followed by
-four bytes of data, comprising the minimum and maximum repeat counts. There are
-no special possessive opcodes for these repeats; a possessive repeat is
-compiled into an atomic group.
-
-
-Brackets and alternation
-------------------------
-
-A pair of non-capturing (round) brackets is wrapped round each expression at
-compile time, so alternation always happens in the context of brackets.
-
-[Note for North Americans: "bracket" to some English speakers, including
-myself, can be round, square, curly, or pointy. Hence this usage.]
-
-Non-capturing brackets use the opcode OP_BRA. Originally PCRE was limited to 99
-capturing brackets and it used a different opcode for each one. From release
-3.5, the limit was removed by putting the bracket number into the data for
-higher-numbered brackets. From release 7.0 all capturing brackets are handled
-this way, using the single opcode OP_CBRA.
-
-A bracket opcode is followed by LINK_SIZE bytes which give the offset to the
-next alternative OP_ALT or, if there aren't any branches, to the matching
-OP_KET opcode. Each OP_ALT is followed by LINK_SIZE bytes giving the offset to
-the next one, or to the OP_KET opcode. For capturing brackets, the bracket
-number immediately follows the offset, always as a 2-byte item.
-
-OP_KET is used for subpatterns that do not repeat indefinitely, while
-OP_KETRMIN and OP_KETRMAX are used for indefinite repetitions, minimally or
-maximally respectively. All three are followed by LINK_SIZE bytes giving (as a
-positive number) the offset back to the matching bracket opcode.
-
-If a subpattern is quantified such that it is permitted to match zero times, it
-is preceded by one of OP_BRAZERO, OP_BRAMINZERO, or OP_SKIPZERO. These are
-single-byte opcodes that tell the matcher that skipping the following
-subpattern entirely is a valid branch. In the case of the first two, not
-skipping the pattern is also valid (greedy and non-greedy). The third is used
-when a pattern has the quantifier {0,0}. It cannot be entirely discarded,
-because it may be called as a subroutine from elsewhere in the regex.
-
-A subpattern with an indefinite maximum repetition is replicated in the
-compiled data its minimum number of times (or once with OP_BRAZERO if the
-minimum is zero), with the final copy terminating with OP_KETRMIN or OP_KETRMAX
-as appropriate.
-
-A subpattern with a bounded maximum repetition is replicated in a nested
-fashion up to the maximum number of times, with OP_BRAZERO or OP_BRAMINZERO
-before each replication after the minimum, so that, for example, (abc){2,5} is
-compiled as (abc)(abc)((abc)((abc)(abc)?)?)?, except that each bracketed group
-has the same number.
-
-When a repeated subpattern has an unbounded upper limit, it is checked to see
-whether it could match an empty string. If this is the case, the opcode in the
-final replication is changed to OP_SBRA or OP_SCBRA. This tells the matcher
-that it needs to check for matching an empty string when it hits OP_KETRMIN or
-OP_KETRMAX, and if so, to break the loop.
-
-
-Assertions
-----------
-
-Forward assertions are just like other subpatterns, but starting with one of
-the opcodes OP_ASSERT or OP_ASSERT_NOT. Backward assertions use the opcodes
-OP_ASSERTBACK and OP_ASSERTBACK_NOT, and the first opcode inside the assertion
-is OP_REVERSE, followed by a two byte count of the number of characters to move
-back the pointer in the subject string. When operating in UTF-8 mode, the count
-is a character count rather than a byte count. A separate count is present in
-each alternative of a lookbehind assertion, allowing them to have different
-fixed lengths.
-
-
-Once-only (atomic) subpatterns
-------------------------------
-
-These are also just like other subpatterns, but they start with the opcode
-OP_ONCE. The check for matching an empty string in an unbounded repeat is
-handled entirely at runtime, so there is just this one opcode.
-
-
-Conditional subpatterns
------------------------
-
-These are like other subpatterns, but they start with the opcode OP_COND, or
-OP_SCOND for one that might match an empty string in an unbounded repeat. If
-the condition is a back reference, this is stored at the start of the
-subpattern using the opcode OP_CREF followed by two bytes containing the
-reference number. OP_NCREF is used instead if the reference was generated by
-name (so that the runtime code knows to check for duplicate names).
-
-If the condition is "in recursion" (coded as "(?(R)"), or "in recursion of
-group x" (coded as "(?(Rx)"), the group number is stored at the start of the
-subpattern using the opcode OP_RREF or OP_NRREF (cf OP_NCREF), and a value of
-zero for "the whole pattern". For a DEFINE condition, just the single byte
-OP_DEF is used (it has no associated data). Otherwise, a conditional subpattern
-always starts with one of the assertions.
-
-
-Recursion
----------
-
-Recursion either matches the current regex, or some subexpression. The opcode
-OP_RECURSE is followed by an value which is the offset to the starting bracket
-from the start of the whole pattern. From release 6.5, OP_RECURSE is
-automatically wrapped inside OP_ONCE brackets (because otherwise some patterns
-broke it). OP_RECURSE is also used for "subroutine" calls, even though they
-are not strictly a recursion.
-
-
-Callout
--------
-
-OP_CALLOUT is followed by one byte of data that holds a callout number in the
-range 0 to 254 for manual callouts, or 255 for an automatic callout. In both
-cases there follows a two-byte value giving the offset in the pattern to the
-start of the following item, and another two-byte item giving the length of the
-next item.
-
-
-Changing options
-----------------
-
-If any of the /i, /m, or /s options are changed within a pattern, an OP_OPT
-opcode is compiled, followed by one byte containing the new settings of these
-flags. If there are several alternatives, there is an occurrence of OP_OPT at
-the start of all those following the first options change, to set appropriate
-options for the start of the alternative. Immediately after the end of the
-group there is another such item to reset the flags to their previous values. A
-change of flag right at the very start of the pattern can be handled entirely
-at compile time, and so does not cause anything to be put into the compiled
-data.
-
-Philip Hazel
-October 2009
projects / vuplus_xbmc / blobdiff