/[pcre]/code/trunk/HACKING

Diff of /code/trunk/HACKING

Parent Directory | Revision Log | View Patch Patch

-code/trunk/doc/Tech.Notes
revision 75 by nigel,
Sat Feb 24 21:40:37 2007 UTC
+code/trunk/HACKING
revision 212 by ph10,
Thu Aug  9 11:16:34 2007 UTC
 Line 1
  Technical Notes about PCRE
  --------------------------
+ These are very rough technical notes that record potentially useful information
+ about PCRE internals.
  Historical note 1
  -----------------
-Line 13 
 not operate by backtracking, as the orig
+Line 16 
 not operate by backtracking, as the orig
  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
+ algorithm", though it was not a traditional Finite State Machine (FSM). When
- possible matches, and the one matching the longest subset of the subject string
+ the pattern was all used up, all remaining states were possible matches, and
- was chosen. This did not necessarily maximize the individual wild portions of
+ the one matching the longest subset of the subject string was chosen. This did
- the pattern, as is expected in Unix and Perl-style regular expressions.
+ 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 and subsequently
+ By contrast, the code originally written by Henry Spencer (which was
- heavily modified for Perl actually compiles the expression twice: once in a
+ subsequently heavily modified for Perl) compiles the expression twice: once in
- dummy mode in order to find out how much store will be needed, and then for
+ a dummy mode in order to find out how much store will be needed, and then for
- real. The execution function operates by backtracking and maximizing (or,
+ real. (The Perl version probably doesn't do this any more; I'm talking about
- optionally, minimizing in Perl) the amount of the subject that matches
+ the original library.) The execution function operates by backtracking and
- individual wild portions of the pattern. This is an "NFA algorithm" in Friedl's
+ maximizing (or, optionally, minimizing in Perl) the amount of the subject that
- terminology.
+ 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 forms PCRE (which are unrelated to those
+ For the set of functions that form the "basic" PCRE library (which are
- mentioned above), I tried at first to invent an algorithm that used an amount
+ unrelated to those mentioned above), I tried at first to invent an algorithm
- of store bounded by a multiple of the number of characters in the pattern, to
+ that used an amount of store bounded by a multiple of the number of characters
- save on compiling time. However, because of the greater complexity in Perl
+ in the pattern, to save on compiling time. However, because of the greater
- regular expressions, I couldn't do this. In any case, a first pass through the
+ complexity in Perl regular expressions, I couldn't do this. In any case, a
- pattern is needed, for a number of reasons. PCRE works by running a very
+ first pass through the pattern is helpful for other reasons.
- 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
+ Computing the memory requirement: how it was
- 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. It does make the compiling functions bigger, of course, but they have
+ Up to and including release 6.7, PCRE worked by running a very degenerate first
- got quite big anyway to handle all the Perl stuff.
+ 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 "two-byte" data values are specified. This is in fact just
+ In many cases below LINK_SIZE data values are specified for offsets within the
- a default. PCRE can be compiled to use 3-byte or 4-byte values (impairing 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.
+ "normal" compilation options. Data values that are counts (e.g. for
+ quantifiers) are always just two bytes long.
- A list of all the opcodes follows:
+ A list of the opcodes follows:
  Opcodes with no following data
  ------------------------------
-Line 68 
 These items are all just one byte long
+Line 129 
 These items are all just one byte long
    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
-Line 91 
 following opcodes:
+Line 165 
 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
+ Those with "MIN" in their name are the minimizing versions. Those with "POS" in
- the character that is to be repeated. Other repeats make use of
+ 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
-Line 119 
 byte. The opcodes are:
+Line 198 
 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
-Line 133 
 Match by Unicode property
+Line 216 
 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 a single byte that encodes the desired property value.
+ 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 two
+ Repeats of these items use the OP_TYPESTAR etc. set of opcodes, followed by
- bytes: OP_PROP or OP_NOTPROP and then the desired property value.
+ three bytes: OP_PROP or OP_NOTPROP and then the desired property type and
+ value.
  Matching literal characters
-Line 186 
 OP_REF is followed by two bytes containi
+Line 271 
 OP_REF is followed by two bytes containi
  Repeating character classes and back references
  -----------------------------------------------
- Single-character classes are handled specially (see above). This applies to
+ Single-character classes are handled specially (see above). This section
- OP_CLASS and OP_REF. In both cases, the repeat information follows the base
+ applies to OP_CLASS and OP_REF. In both cases, the repeat information follows
- item. The matching code looks at the following opcode to see if it is one of
+ the base item. The matching code looks at the following opcode to see if it is
+ one of
    OP_CRSTAR
    OP_CRMINSTAR
-Line 200 
 item. The matching code looks at the fol
+Line 286 
 item. The matching code looks at the fol
    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
-Line 209 
 Brackets and alternation
+Line 297 
 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
+ [Note for North Americans: "bracket" to some English speakers, including
- OP_BRA+1, OP_BRA+2, etc. [Note for North Americans: "bracket" to some English
+ myself, can be round, square, curly, or pointy. Hence this usage.]
- 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
- Originally PCRE was limited to 99 capturing brackets (so as not to use up all
+.5, the limit was removed by putting the bracket number into the data for
- the opcodes). From release 3.5, there is no limit. What happens is that the
+ higher-numbered brackets. From release 7.0 all capturing brackets are handled
- first ones, up to EXTRACT_BASIC_MAX are handled with separate opcodes, as
+ this way, using the single opcode OP_CBRA.
- 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
+ A bracket opcode is followed by LINK_SIZE bytes which give the offset to the
- number. This opcode is ignored while matching, but is fished out when handling
+ next alternative OP_ALT or, if there aren't any branches, to the matching
- the bracket itself. (They could have all been done like this, but I was making
+ OP_KET opcode. Each OP_ALT is followed by LINK_SIZE bytes giving the offset to
- minimal changes.)
+ 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.
- A bracket opcode is followed by two 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 two bytes giving the offset to the next one,
- or to the OP_KET opcode.
  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 two bytes giving (as a
+ 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
-Line 246 
 as appropriate.
+Line 330 
 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
-Line 262 
 each alternative of a lookbehind asserti
+Line 353 
 each alternative of a lookbehind asserti
  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
+ reference number. If the condition is "in recursion" (coded as "(?(R)"), or "in
- same scheme is used, with a "reference number" of 0xffff. Otherwise, a
+ recursion of group x" (coded as "(?(Rx)"), the group number is stored at the
- conditional subpattern always starts with one of the assertions.
+ 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
-Line 285 
 Recursion
+Line 381 
 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 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
-Line 312 
 at compile time, and so does not cause a
+Line 411 
 at compile time, and so does not cause a
  data.
  Philip Hazel
- September 2004
+ August 2007

 Legend:



Removed from v.75
 


changed lines


 
Added in v.212
 Legend:



Removed from v.75
 


changed lines


 
Added in v.212
-Removed from v.75
+Added in v.212

webmaster@exim.org	ViewVC Help
Powered by ViewVC 1.1.12