diff options
Diffstat (limited to 'crawl-ref/source/util/pcre/HACKING')
| -rw-r--r-- | crawl-ref/source/util/pcre/HACKING | 418 |
1 files changed, 418 insertions, 0 deletions
diff --git a/crawl-ref/source/util/pcre/HACKING b/crawl-ref/source/util/pcre/HACKING new file mode 100644 index 0000000000..1f30d4c487 --- /dev/null +++ b/crawl-ref/source/util/pcre/HACKING @@ -0,0 +1,418 @@ +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 are also present in the 7.0 release). + +A side effect of this work is 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 is that this is not a big +issue. + +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. 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 ) + OP_COMMIT ) + OP_FAIL ) These are Perl 5.10's "backtracking + OP_PRUNE ) control verbs". + OP_SKIP ) + OP_THEN ) + + +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. 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, 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 +April 2008 |