upgrade pcre to version 7.0

1 files changed, 99 insertions, 45 deletions

diff --git a/ext/pcre/pcrelib/doc/Tech.Notes b/ext/pcre/pcrelib/doc/Tech.Notes
index 21dbe1f9b5..c75b3e8a5d 100644
--- a/ext/pcre/pcrelib/doc/Tech.Notes
+++ b/ext/pcre/pcrelib/doc/Tech.Notes
@@ -16,10 +16,11 @@ 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". 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.
+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
 -----------------
@@ -41,14 +42,38 @@ 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 needed, for a number of reasons. PCRE works
-by running a very degenerate first pass to calculate a maximum store size, and
-then a second pass to do the real compile - which may use a bit less than the
-predicted amount of store. The idea is that this is going to turn out faster
-because the first pass is degenerate and the second pass can just store stuff
-straight into the vector, which it knows is big enough. It does make the
-compiling functions bigger, of course, but they have become quite big anyway to
-handle all the Perl stuff.
+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
 -----------------------------
@@ -70,6 +95,12 @@ 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
 ---------------------------
 
@@ -79,10 +110,12 @@ item is either implicit in the opcode or contained in the data bytes that
 follow it. 
 
 In many cases below "two-byte" data values are specified. This is in fact just
-a default. PCRE can be compiled to use 3-byte or 4-byte values (impairing the
+a default when the number is an offset within the compiled pattern. 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.
+greater than 64K are going to be processed. In this description, we assume the
+"normal" compilation options. "Two-byte" data values that are counts (e.g. for 
+quantifiers) are always just two bytes.
 
 A list of all the opcodes follows:
 
@@ -109,6 +142,7 @@ These items are all just one byte long
   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 
   
 
 Repeating single characters
@@ -119,23 +153,28 @@ 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. Each is followed by
-the character that is to be repeated. Other repeats make use of
+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).
+OP_UPTO (or OP_MINUPTO or OPT_POSUPTO).
 
 
 Repeating character types
@@ -147,12 +186,16 @@ 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
 
 
@@ -216,9 +259,10 @@ 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 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
+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
@@ -230,7 +274,9 @@ item. The matching code looks at the following opcode to see if it is one of
   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.
+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
@@ -239,29 +285,25 @@ 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.
 
-Non-capturing brackets use the opcode OP_BRA, while capturing brackets use
-OP_BRA+1, OP_BRA+2, etc. [Note for North Americans: "bracket" to some English
-speakers, including myself, can be round, square, curly, or pointy. Hence this
-usage.]
+[Note for North Americans: "bracket" to some English speakers, including
+myself, can be round, square, curly, or pointy. Hence this usage.]
 
-Originally PCRE was limited to 99 capturing brackets (so as not to use up all
-the opcodes). From release 3.5, there is no limit. What happens is that the
-first ones, up to EXTRACT_BASIC_MAX are handled with separate opcodes, as
-above. If there are more, the opcode is set to EXTRACT_BASIC_MAX+1, and the
-first operation in the bracket is OP_BRANUMBER, followed by a 2-byte bracket
-number. This opcode is ignored while matching, but is fished out when handling
-the bracket itself. (They could have all been done like this, but I was making
-minimal changes.)
+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.
+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 OP_BRA opcode.
+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 or OP_BRAMINZERO. These are single-byte
@@ -276,7 +318,14 @@ 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)?)?)?.
+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
@@ -292,22 +341,27 @@ each alternative of a lookbehind assertion, allowing them to have different
 fixed lengths.
 
 
-Once-only subpatterns
----------------------
+Once-only (atomic) subpatterns
+------------------------------
 
 These are also just like other subpatterns, but they start with the opcode
-OP_ONCE.
+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. If
+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)"), the
-same scheme is used, with a "reference number" of 0xffff. Otherwise, a
-conditional subpattern always starts with one of the assertions.
+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
@@ -345,4 +399,4 @@ at compile time, and so does not cause anything to be put into the compiled
 data.
 
 Philip Hazel
-June 2006
+November 2006