X-Git-Url: http://ftp.carnet.hr/carnet-debian/scm?a=blobdiff_plain;f=src%2Fexternal%2Fpcre2-10.32%2Fdoc%2Fpcre2matching.3;fp=src%2Fexternal%2Fpcre2-10.32%2Fdoc%2Fpcre2matching.3;h=81ce96839cd6639ccb29dddbfa036767333eecb0;hb=3f728675941dc69d4e544d3a880a56240a6e394a;hp=0000000000000000000000000000000000000000;hpb=927951d1c1ad45ba9e7325f07d996154a91c911b;p=ossec-hids.git diff --git a/src/external/pcre2-10.32/doc/pcre2matching.3 b/src/external/pcre2-10.32/doc/pcre2matching.3 new file mode 100644 index 0000000..81ce968 --- /dev/null +++ b/src/external/pcre2-10.32/doc/pcre2matching.3 @@ -0,0 +1,213 @@ +.TH PCRE2MATCHING 3 "29 September 2014" "PCRE2 10.00" +.SH NAME +PCRE2 - Perl-compatible regular expressions (revised API) +.SH "PCRE2 MATCHING ALGORITHMS" +.rs +.sp +This document describes the two different algorithms that are available in +PCRE2 for matching a compiled regular expression against a given subject +string. The "standard" algorithm is the one provided by the \fBpcre2_match()\fP +function. This works in the same as as Perl's matching function, and provide a +Perl-compatible matching operation. The just-in-time (JIT) optimization that is +described in the +.\" HREF +\fBpcre2jit\fP +.\" +documentation is compatible with this function. +.P +An alternative algorithm is provided by the \fBpcre2_dfa_match()\fP function; +it operates in a different way, and is not Perl-compatible. This alternative +has advantages and disadvantages compared with the standard algorithm, and +these are described below. +.P +When there is only one possible way in which a given subject string can match a +pattern, the two algorithms give the same answer. A difference arises, however, +when there are multiple possibilities. For example, if the pattern +.sp + ^<.*> +.sp +is matched against the string +.sp + +.sp +there are three possible answers. The standard algorithm finds only one of +them, whereas the alternative algorithm finds all three. +. +. +.SH "REGULAR EXPRESSIONS AS TREES" +.rs +.sp +The set of strings that are matched by a regular expression can be represented +as a tree structure. An unlimited repetition in the pattern makes the tree of +infinite size, but it is still a tree. Matching the pattern to a given subject +string (from a given starting point) can be thought of as a search of the tree. +There are two ways to search a tree: depth-first and breadth-first, and these +correspond to the two matching algorithms provided by PCRE2. +. +. +.SH "THE STANDARD MATCHING ALGORITHM" +.rs +.sp +In the terminology of Jeffrey Friedl's book "Mastering Regular Expressions", +the standard algorithm is an "NFA algorithm". It conducts a depth-first search +of the pattern tree. That is, it proceeds along a single path through the tree, +checking that the subject matches what is required. When there is a mismatch, +the algorithm tries any alternatives at the current point, and if they all +fail, it backs up to the previous branch point in the tree, and tries the next +alternative branch at that level. This often involves backing up (moving to the +left) in the subject string as well. The order in which repetition branches are +tried is controlled by the greedy or ungreedy nature of the quantifier. +.P +If a leaf node is reached, a matching string has been found, and at that point +the algorithm stops. Thus, if there is more than one possible match, this +algorithm returns the first one that it finds. Whether this is the shortest, +the longest, or some intermediate length depends on the way the greedy and +ungreedy repetition quantifiers are specified in the pattern. +.P +Because it ends up with a single path through the tree, it is relatively +straightforward for this algorithm to keep track of the substrings that are +matched by portions of the pattern in parentheses. This provides support for +capturing parentheses and backreferences. +. +. +.SH "THE ALTERNATIVE MATCHING ALGORITHM" +.rs +.sp +This algorithm conducts a breadth-first search of the tree. Starting from the +first matching point in the subject, it scans the subject string from left to +right, once, character by character, and as it does this, it remembers all the +paths through the tree that represent valid matches. In Friedl's terminology, +this is a kind of "DFA algorithm", though it is not implemented as a +traditional finite state machine (it keeps multiple states active +simultaneously). +.P +Although the general principle of this matching algorithm is that it scans the +subject string only once, without backtracking, there is one exception: when a +lookaround assertion is encountered, the characters following or preceding the +current point have to be independently inspected. +.P +The scan continues until either the end of the subject is reached, or there are +no more unterminated paths. At this point, terminated paths represent the +different matching possibilities (if there are none, the match has failed). +Thus, if there is more than one possible match, this algorithm finds all of +them, and in particular, it finds the longest. The matches are returned in +decreasing order of length. There is an option to stop the algorithm after the +first match (which is necessarily the shortest) is found. +.P +Note that all the matches that are found start at the same point in the +subject. If the pattern +.sp + cat(er(pillar)?)? +.sp +is matched against the string "the caterpillar catchment", the result is the +three strings "caterpillar", "cater", and "cat" that start at the fifth +character of the subject. The algorithm does not automatically move on to find +matches that start at later positions. +.P +PCRE2's "auto-possessification" optimization usually applies to character +repeats at the end of a pattern (as well as internally). For example, the +pattern "a\ed+" is compiled as if it were "a\ed++" because there is no point +even considering the possibility of backtracking into the repeated digits. For +DFA matching, this means that only one possible match is found. If you really +do want multiple matches in such cases, either use an ungreedy repeat +("a\ed+?") or set the PCRE2_NO_AUTO_POSSESS option when compiling. +.P +There are a number of features of PCRE2 regular expressions that are not +supported by the alternative matching algorithm. They are as follows: +.P +1. Because the algorithm finds all possible matches, the greedy or ungreedy +nature of repetition quantifiers is not relevant (though it may affect +auto-possessification, as just described). During matching, greedy and ungreedy +quantifiers are treated in exactly the same way. However, possessive +quantifiers can make a difference when what follows could also match what is +quantified, for example in a pattern like this: +.sp + ^a++\ew! +.sp +This pattern matches "aaab!" but not "aaa!", which would be matched by a +non-possessive quantifier. Similarly, if an atomic group is present, it is +matched as if it were a standalone pattern at the current point, and the +longest match is then "locked in" for the rest of the overall pattern. +.P +2. When dealing with multiple paths through the tree simultaneously, it is not +straightforward to keep track of captured substrings for the different matching +possibilities, and PCRE2's implementation of this algorithm does not attempt to +do this. This means that no captured substrings are available. +.P +3. Because no substrings are captured, backreferences within the pattern are +not supported, and cause errors if encountered. +.P +4. For the same reason, conditional expressions that use a backreference as the +condition or test for a specific group recursion are not supported. +.P +5. Because many paths through the tree may be active, the \eK escape sequence, +which resets the start of the match when encountered (but may be on some paths +and not on others), is not supported. It causes an error if encountered. +.P +6. Callouts are supported, but the value of the \fIcapture_top\fP field is +always 1, and the value of the \fIcapture_last\fP field is always 0. +.P +7. The \eC escape sequence, which (in the standard algorithm) always matches a +single code unit, even in a UTF mode, is not supported in these modes, because +the alternative algorithm moves through the subject string one character (not +code unit) at a time, for all active paths through the tree. +.P +8. Except for (*FAIL), the backtracking control verbs such as (*PRUNE) are not +supported. (*FAIL) is supported, and behaves like a failing negative assertion. +. +. +.SH "ADVANTAGES OF THE ALTERNATIVE ALGORITHM" +.rs +.sp +Using the alternative matching algorithm provides the following advantages: +.P +1. All possible matches (at a single point in the subject) are automatically +found, and in particular, the longest match is found. To find more than one +match using the standard algorithm, you have to do kludgy things with +callouts. +.P +2. Because the alternative algorithm scans the subject string just once, and +never needs to backtrack (except for lookbehinds), it is possible to pass very +long subject strings to the matching function in several pieces, checking for +partial matching each time. Although it is also possible to do multi-segment +matching using the standard algorithm, by retaining partially matched +substrings, it is more complicated. The +.\" HREF +\fBpcre2partial\fP +.\" +documentation gives details of partial matching and discusses multi-segment +matching. +. +. +.SH "DISADVANTAGES OF THE ALTERNATIVE ALGORITHM" +.rs +.sp +The alternative algorithm suffers from a number of disadvantages: +.P +1. It is substantially slower than the standard algorithm. This is partly +because it has to search for all possible matches, but is also because it is +less susceptible to optimization. +.P +2. Capturing parentheses and backreferences are not supported. +.P +3. Although atomic groups are supported, their use does not provide the +performance advantage that it does for the standard algorithm. +. +. +.SH AUTHOR +.rs +.sp +.nf +Philip Hazel +University Computing Service +Cambridge, England. +.fi +. +. +.SH REVISION +.rs +.sp +.nf +Last updated: 29 September 2014 +Copyright (c) 1997-2014 University of Cambridge. +.fi