summaryrefslogtreecommitdiff
path: root/Master/tlpkg/tlperl/lib/pods/perlreguts.pod
diff options
context:
space:
mode:
Diffstat (limited to 'Master/tlpkg/tlperl/lib/pods/perlreguts.pod')
-rw-r--r--Master/tlpkg/tlperl/lib/pods/perlreguts.pod886
1 files changed, 0 insertions, 886 deletions
diff --git a/Master/tlpkg/tlperl/lib/pods/perlreguts.pod b/Master/tlpkg/tlperl/lib/pods/perlreguts.pod
deleted file mode 100644
index ec1c243f8a9..00000000000
--- a/Master/tlpkg/tlperl/lib/pods/perlreguts.pod
+++ /dev/null
@@ -1,886 +0,0 @@
-=head1 NAME
-
-perlreguts - Description of the Perl regular expression engine.
-
-=head1 DESCRIPTION
-
-This document is an attempt to shine some light on the guts of the regex
-engine and how it works. The regex engine represents a significant chunk
-of the perl codebase, but is relatively poorly understood. This document
-is a meagre attempt at addressing this situation. It is derived from the
-author's experience, comments in the source code, other papers on the
-regex engine, feedback on the perl5-porters mail list, and no doubt other
-places as well.
-
-B<NOTICE!> It should be clearly understood that the behavior and
-structures discussed in this represents the state of the engine as the
-author understood it at the time of writing. It is B<NOT> an API
-definition, it is purely an internals guide for those who want to hack
-the regex engine, or understand how the regex engine works. Readers of
-this document are expected to understand perl's regex syntax and its
-usage in detail. If you want to learn about the basics of Perl's
-regular expressions, see L<perlre>. And if you want to replace the
-regex engine with your own, see L<perlreapi>.
-
-=head1 OVERVIEW
-
-=head2 A quick note on terms
-
-There is some debate as to whether to say "regexp" or "regex". In this
-document we will use the term "regex" unless there is a special reason
-not to, in which case we will explain why.
-
-When speaking about regexes we need to distinguish between their source
-code form and their internal form. In this document we will use the term
-"pattern" when we speak of their textual, source code form, and the term
-"program" when we speak of their internal representation. These
-correspond to the terms I<S-regex> and I<B-regex> that Mark Jason
-Dominus employs in his paper on "Rx" ([1] in L</REFERENCES>).
-
-=head2 What is a regular expression engine?
-
-A regular expression engine is a program that takes a set of constraints
-specified in a mini-language, and then applies those constraints to a
-target string, and determines whether or not the string satisfies the
-constraints. See L<perlre> for a full definition of the language.
-
-In less grandiose terms, the first part of the job is to turn a pattern into
-something the computer can efficiently use to find the matching point in
-the string, and the second part is performing the search itself.
-
-To do this we need to produce a program by parsing the text. We then
-need to execute the program to find the point in the string that
-matches. And we need to do the whole thing efficiently.
-
-=head2 Structure of a Regexp Program
-
-=head3 High Level
-
-Although it is a bit confusing and some people object to the terminology, it
-is worth taking a look at a comment that has
-been in F<regexp.h> for years:
-
-I<This is essentially a linear encoding of a nondeterministic
-finite-state machine (aka syntax charts or "railroad normal form" in
-parsing technology).>
-
-The term "railroad normal form" is a bit esoteric, with "syntax
-diagram/charts", or "railroad diagram/charts" being more common terms.
-Nevertheless it provides a useful mental image of a regex program: each
-node can be thought of as a unit of track, with a single entry and in
-most cases a single exit point (there are pieces of track that fork, but
-statistically not many), and the whole forms a layout with a
-single entry and single exit point. The matching process can be thought
-of as a car that moves along the track, with the particular route through
-the system being determined by the character read at each possible
-connector point. A car can fall off the track at any point but it may
-only proceed as long as it matches the track.
-
-Thus the pattern C</foo(?:\w+|\d+|\s+)bar/> can be thought of as the
-following chart:
-
- [start]
- |
- <foo>
- |
- +-----+-----+
- | | |
- <\w+> <\d+> <\s+>
- | | |
- +-----+-----+
- |
- <bar>
- |
- [end]
-
-The truth of the matter is that perl's regular expressions these days are
-much more complex than this kind of structure, but visualising it this way
-can help when trying to get your bearings, and it matches the
-current implementation pretty closely.
-
-To be more precise, we will say that a regex program is an encoding
-of a graph. Each node in the graph corresponds to part of
-the original regex pattern, such as a literal string or a branch,
-and has a pointer to the nodes representing the next component
-to be matched. Since "node" and "opcode" already have other meanings in the
-perl source, we will call the nodes in a regex program "regops".
-
-The program is represented by an array of C<regnode> structures, one or
-more of which represent a single regop of the program. Struct
-C<regnode> is the smallest struct needed, and has a field structure which is
-shared with all the other larger structures.
-
-The "next" pointers of all regops except C<BRANCH> implement concatenation;
-a "next" pointer with a C<BRANCH> on both ends of it is connecting two
-alternatives. [Here we have one of the subtle syntax dependencies: an
-individual C<BRANCH> (as opposed to a collection of them) is never
-concatenated with anything because of operator precedence.]
-
-The operand of some types of regop is a literal string; for others,
-it is a regop leading into a sub-program. In particular, the operand
-of a C<BRANCH> node is the first regop of the branch.
-
-B<NOTE>: As the railroad metaphor suggests, this is B<not> a tree
-structure: the tail of the branch connects to the thing following the
-set of C<BRANCH>es. It is a like a single line of railway track that
-splits as it goes into a station or railway yard and rejoins as it comes
-out the other side.
-
-=head3 Regops
-
-The base structure of a regop is defined in F<regexp.h> as follows:
-
- struct regnode {
- U8 flags; /* Various purposes, sometimes overridden */
- U8 type; /* Opcode value as specified by regnodes.h */
- U16 next_off; /* Offset in size regnode */
- };
-
-Other larger C<regnode>-like structures are defined in F<regcomp.h>. They
-are almost like subclasses in that they have the same fields as
-C<regnode>, with possibly additional fields following in
-the structure, and in some cases the specific meaning (and name)
-of some of base fields are overridden. The following is a more
-complete description.
-
-=over 4
-
-=item C<regnode_1>
-
-=item C<regnode_2>
-
-C<regnode_1> structures have the same header, followed by a single
-four-byte argument; C<regnode_2> structures contain two two-byte
-arguments instead:
-
- regnode_1 U32 arg1;
- regnode_2 U16 arg1; U16 arg2;
-
-=item C<regnode_string>
-
-C<regnode_string> structures, used for literal strings, follow the header
-with a one-byte length and then the string data. Strings are padded on
-the end with zero bytes so that the total length of the node is a
-multiple of four bytes:
-
- regnode_string char string[1];
- U8 str_len; /* overrides flags */
-
-=item C<regnode_charclass>
-
-Character classes are represented by C<regnode_charclass> structures,
-which have a four-byte argument and then a 32-byte (256-bit) bitmap
-indicating which characters are included in the class.
-
- regnode_charclass U32 arg1;
- char bitmap[ANYOF_BITMAP_SIZE];
-
-=item C<regnode_charclass_class>
-
-There is also a larger form of a char class structure used to represent
-POSIX char classes called C<regnode_charclass_class> which has an
-additional 4-byte (32-bit) bitmap indicating which POSIX char classes
-have been included.
-
- regnode_charclass_class U32 arg1;
- char bitmap[ANYOF_BITMAP_SIZE];
- char classflags[ANYOF_CLASSBITMAP_SIZE];
-
-=back
-
-F<regnodes.h> defines an array called C<regarglen[]> which gives the size
-of each opcode in units of C<size regnode> (4-byte). A macro is used
-to calculate the size of an C<EXACT> node based on its C<str_len> field.
-
-The regops are defined in F<regnodes.h> which is generated from
-F<regcomp.sym> by F<regcomp.pl>. Currently the maximum possible number
-of distinct regops is restricted to 256, with about a quarter already
-used.
-
-A set of macros makes accessing the fields
-easier and more consistent. These include C<OP()>, which is used to determine
-the type of a C<regnode>-like structure; C<NEXT_OFF()>, which is the offset to
-the next node (more on this later); C<ARG()>, C<ARG1()>, C<ARG2()>, C<ARG_SET()>,
-and equivalents for reading and setting the arguments; and C<STR_LEN()>,
-C<STRING()> and C<OPERAND()> for manipulating strings and regop bearing
-types.
-
-=head3 What regop is next?
-
-There are three distinct concepts of "next" in the regex engine, and
-it is important to keep them clear.
-
-=over 4
-
-=item *
-
-There is the "next regnode" from a given regnode, a value which is
-rarely useful except that sometimes it matches up in terms of value
-with one of the others, and that sometimes the code assumes this to
-always be so.
-
-=item *
-
-There is the "next regop" from a given regop/regnode. This is the
-regop physically located after the current one, as determined by
-the size of the current regop. This is often useful, such as when
-dumping the structure we use this order to traverse. Sometimes the code
-assumes that the "next regnode" is the same as the "next regop", or in
-other words assumes that the sizeof a given regop type is always going
-to be one regnode large.
-
-=item *
-
-There is the "regnext" from a given regop. This is the regop which
-is reached by jumping forward by the value of C<NEXT_OFF()>,
-or in a few cases for longer jumps by the C<arg1> field of the C<regnode_1>
-structure. The subroutine C<regnext()> handles this transparently.
-This is the logical successor of the node, which in some cases, like
-that of the C<BRANCH> regop, has special meaning.
-
-=back
-
-=head1 Process Overview
-
-Broadly speaking, performing a match of a string against a pattern
-involves the following steps:
-
-=over 5
-
-=item A. Compilation
-
-=over 5
-
-=item 1. Parsing for size
-
-=item 2. Parsing for construction
-
-=item 3. Peep-hole optimisation and analysis
-
-=back
-
-=item B. Execution
-
-=over 5
-
-=item 4. Start position and no-match optimisations
-
-=item 5. Program execution
-
-=back
-
-=back
-
-
-Where these steps occur in the actual execution of a perl program is
-determined by whether the pattern involves interpolating any string
-variables. If interpolation occurs, then compilation happens at run time. If it
-does not, then compilation is performed at compile time. (The C</o> modifier changes this,
-as does C<qr//> to a certain extent.) The engine doesn't really care that
-much.
-
-=head2 Compilation
-
-This code resides primarily in F<regcomp.c>, along with the header files
-F<regcomp.h>, F<regexp.h> and F<regnodes.h>.
-
-Compilation starts with C<pregcomp()>, which is mostly an initialisation
-wrapper which farms work out to two other routines for the heavy lifting: the
-first is C<reg()>, which is the start point for parsing; the second,
-C<study_chunk()>, is responsible for optimisation.
-
-Initialisation in C<pregcomp()> mostly involves the creation and data-filling
-of a special structure, C<RExC_state_t> (defined in F<regcomp.c>).
-Almost all internally-used routines in F<regcomp.h> take a pointer to one
-of these structures as their first argument, with the name C<pRExC_state>.
-This structure is used to store the compilation state and contains many
-fields. Likewise there are many macros which operate on this
-variable: anything that looks like C<RExC_xxxx> is a macro that operates on
-this pointer/structure.
-
-=head3 Parsing for size
-
-In this pass the input pattern is parsed in order to calculate how much
-space is needed for each regop we would need to emit. The size is also
-used to determine whether long jumps will be required in the program.
-
-This stage is controlled by the macro C<SIZE_ONLY> being set.
-
-The parse proceeds pretty much exactly as it does during the
-construction phase, except that most routines are short-circuited to
-change the size field C<RExC_size> and not do anything else.
-
-=head3 Parsing for construction
-
-Once the size of the program has been determined, the pattern is parsed
-again, but this time for real. Now C<SIZE_ONLY> will be false, and the
-actual construction can occur.
-
-C<reg()> is the start of the parse process. It is responsible for
-parsing an arbitrary chunk of pattern up to either the end of the
-string, or the first closing parenthesis it encounters in the pattern.
-This means it can be used to parse the top-level regex, or any section
-inside of a grouping parenthesis. It also handles the "special parens"
-that perl's regexes have. For instance when parsing C</x(?:foo)y/> C<reg()>
-will at one point be called to parse from the "?" symbol up to and
-including the ")".
-
-Additionally, C<reg()> is responsible for parsing the one or more
-branches from the pattern, and for "finishing them off" by correctly
-setting their next pointers. In order to do the parsing, it repeatedly
-calls out to C<regbranch()>, which is responsible for handling up to the
-first C<|> symbol it sees.
-
-C<regbranch()> in turn calls C<regpiece()> which
-handles "things" followed by a quantifier. In order to parse the
-"things", C<regatom()> is called. This is the lowest level routine, which
-parses out constant strings, character classes, and the
-various special symbols like C<$>. If C<regatom()> encounters a "("
-character it in turn calls C<reg()>.
-
-The routine C<regtail()> is called by both C<reg()> and C<regbranch()>
-in order to "set the tail pointer" correctly. When executing and
-we get to the end of a branch, we need to go to the node following the
-grouping parens. When parsing, however, we don't know where the end will
-be until we get there, so when we do we must go back and update the
-offsets as appropriate. C<regtail> is used to make this easier.
-
-A subtlety of the parsing process means that a regex like C</foo/> is
-originally parsed into an alternation with a single branch. It is only
-afterwards that the optimiser converts single branch alternations into the
-simpler form.
-
-=head3 Parse Call Graph and a Grammar
-
-The call graph looks like this:
-
- reg() # parse a top level regex, or inside of parens
- regbranch() # parse a single branch of an alternation
- regpiece() # parse a pattern followed by a quantifier
- regatom() # parse a simple pattern
- regclass() # used to handle a class
- reg() # used to handle a parenthesised subpattern
- ....
- ...
- regtail() # finish off the branch
- ...
- regtail() # finish off the branch sequence. Tie each
- # branch's tail to the tail of the sequence
- # (NEW) In Debug mode this is
- # regtail_study().
-
-A grammar form might be something like this:
-
- atom : constant | class
- quant : '*' | '+' | '?' | '{min,max}'
- _branch: piece
- | piece _branch
- | nothing
- branch: _branch
- | _branch '|' branch
- group : '(' branch ')'
- _piece: atom | group
- piece : _piece
- | _piece quant
-
-=head3 Debug Output
-
-In the 5.9.x development version of perl you can C<< use re Debug => 'PARSE' >>
-to see some trace information about the parse process. We will start with some
-simple patterns and build up to more complex patterns.
-
-So when we parse C</foo/> we see something like the following table. The
-left shows what is being parsed, and the number indicates where the next regop
-would go. The stuff on the right is the trace output of the graph. The
-names are chosen to be short to make it less dense on the screen. 'tsdy'
-is a special form of C<regtail()> which does some extra analysis.
-
- >foo< 1 reg
- brnc
- piec
- atom
- >< 4 tsdy~ EXACT <foo> (EXACT) (1)
- ~ attach to END (3) offset to 2
-
-The resulting program then looks like:
-
- 1: EXACT <foo>(3)
- 3: END(0)
-
-As you can see, even though we parsed out a branch and a piece, it was ultimately
-only an atom. The final program shows us how things work. We have an C<EXACT> regop,
-followed by an C<END> regop. The number in parens indicates where the C<regnext> of
-the node goes. The C<regnext> of an C<END> regop is unused, as C<END> regops mean
-we have successfully matched. The number on the left indicates the position of
-the regop in the regnode array.
-
-Now let's try a harder pattern. We will add a quantifier, so now we have the pattern
-C</foo+/>. We will see that C<regbranch()> calls C<regpiece()> twice.
-
- >foo+< 1 reg
- brnc
- piec
- atom
- >o+< 3 piec
- atom
- >< 6 tail~ EXACT <fo> (1)
- 7 tsdy~ EXACT <fo> (EXACT) (1)
- ~ PLUS (END) (3)
- ~ attach to END (6) offset to 3
-
-And we end up with the program:
-
- 1: EXACT <fo>(3)
- 3: PLUS(6)
- 4: EXACT <o>(0)
- 6: END(0)
-
-Now we have a special case. The C<EXACT> regop has a C<regnext> of 0. This is
-because if it matches it should try to match itself again. The C<PLUS> regop
-handles the actual failure of the C<EXACT> regop and acts appropriately (going
-to regnode 6 if the C<EXACT> matched at least once, or failing if it didn't).
-
-Now for something much more complex: C</x(?:foo*|b[a][rR])(foo|bar)$/>
-
- >x(?:foo*|b... 1 reg
- brnc
- piec
- atom
- >(?:foo*|b[... 3 piec
- atom
- >?:foo*|b[a... reg
- >foo*|b[a][... brnc
- piec
- atom
- >o*|b[a][rR... 5 piec
- atom
- >|b[a][rR])... 8 tail~ EXACT <fo> (3)
- >b[a][rR])(... 9 brnc
- 10 piec
- atom
- >[a][rR])(f... 12 piec
- atom
- >a][rR])(fo... clas
- >[rR])(foo|... 14 tail~ EXACT <b> (10)
- piec
- atom
- >rR])(foo|b... clas
- >)(foo|bar)... 25 tail~ EXACT <a> (12)
- tail~ BRANCH (3)
- 26 tsdy~ BRANCH (END) (9)
- ~ attach to TAIL (25) offset to 16
- tsdy~ EXACT <fo> (EXACT) (4)
- ~ STAR (END) (6)
- ~ attach to TAIL (25) offset to 19
- tsdy~ EXACT <b> (EXACT) (10)
- ~ EXACT <a> (EXACT) (12)
- ~ ANYOF[Rr] (END) (14)
- ~ attach to TAIL (25) offset to 11
- >(foo|bar)$< tail~ EXACT <x> (1)
- piec
- atom
- >foo|bar)$< reg
- 28 brnc
- piec
- atom
- >|bar)$< 31 tail~ OPEN1 (26)
- >bar)$< brnc
- 32 piec
- atom
- >)$< 34 tail~ BRANCH (28)
- 36 tsdy~ BRANCH (END) (31)
- ~ attach to CLOSE1 (34) offset to 3
- tsdy~ EXACT <foo> (EXACT) (29)
- ~ attach to CLOSE1 (34) offset to 5
- tsdy~ EXACT <bar> (EXACT) (32)
- ~ attach to CLOSE1 (34) offset to 2
- >$< tail~ BRANCH (3)
- ~ BRANCH (9)
- ~ TAIL (25)
- piec
- atom
- >< 37 tail~ OPEN1 (26)
- ~ BRANCH (28)
- ~ BRANCH (31)
- ~ CLOSE1 (34)
- 38 tsdy~ EXACT <x> (EXACT) (1)
- ~ BRANCH (END) (3)
- ~ BRANCH (END) (9)
- ~ TAIL (END) (25)
- ~ OPEN1 (END) (26)
- ~ BRANCH (END) (28)
- ~ BRANCH (END) (31)
- ~ CLOSE1 (END) (34)
- ~ EOL (END) (36)
- ~ attach to END (37) offset to 1
-
-Resulting in the program
-
- 1: EXACT <x>(3)
- 3: BRANCH(9)
- 4: EXACT <fo>(6)
- 6: STAR(26)
- 7: EXACT <o>(0)
- 9: BRANCH(25)
- 10: EXACT <ba>(14)
- 12: OPTIMIZED (2 nodes)
- 14: ANYOF[Rr](26)
- 25: TAIL(26)
- 26: OPEN1(28)
- 28: TRIE-EXACT(34)
- [StS:1 Wds:2 Cs:6 Uq:5 #Sts:7 Mn:3 Mx:3 Stcls:bf]
- <foo>
- <bar>
- 30: OPTIMIZED (4 nodes)
- 34: CLOSE1(36)
- 36: EOL(37)
- 37: END(0)
-
-Here we can see a much more complex program, with various optimisations in
-play. At regnode 10 we see an example where a character class with only
-one character in it was turned into an C<EXACT> node. We can also see where
-an entire alternation was turned into a C<TRIE-EXACT> node. As a consequence,
-some of the regnodes have been marked as optimised away. We can see that
-the C<$> symbol has been converted into an C<EOL> regop, a special piece of
-code that looks for C<\n> or the end of the string.
-
-The next pointer for C<BRANCH>es is interesting in that it points at where
-execution should go if the branch fails. When executing, if the engine
-tries to traverse from a branch to a C<regnext> that isn't a branch then
-the engine will know that the entire set of branches has failed.
-
-=head3 Peep-hole Optimisation and Analysis
-
-The regular expression engine can be a weighty tool to wield. On long
-strings and complex patterns it can end up having to do a lot of work
-to find a match, and even more to decide that no match is possible.
-Consider a situation like the following pattern.
-
- 'ababababababababababab' =~ /(a|b)*z/
-
-The C<(a|b)*> part can match at every char in the string, and then fail
-every time because there is no C<z> in the string. So obviously we can
-avoid using the regex engine unless there is a C<z> in the string.
-Likewise in a pattern like:
-
- /foo(\w+)bar/
-
-In this case we know that the string must contain a C<foo> which must be
-followed by C<bar>. We can use Fast Boyer-Moore matching as implemented
-in C<fbm_instr()> to find the location of these strings. If they don't exist
-then we don't need to resort to the much more expensive regex engine.
-Even better, if they do exist then we can use their positions to
-reduce the search space that the regex engine needs to cover to determine
-if the entire pattern matches.
-
-There are various aspects of the pattern that can be used to facilitate
-optimisations along these lines:
-
-=over 5
-
-=item * anchored fixed strings
-
-=item * floating fixed strings
-
-=item * minimum and maximum length requirements
-
-=item * start class
-
-=item * Beginning/End of line positions
-
-=back
-
-Another form of optimisation that can occur is the post-parse "peep-hole"
-optimisation, where inefficient constructs are replaced by more efficient
-constructs. The C<TAIL> regops which are used during parsing to mark the end
-of branches and the end of groups are examples of this. These regops are used
-as place-holders during construction and "always match" so they can be
-"optimised away" by making the things that point to the C<TAIL> point to the
-thing that C<TAIL> points to, thus "skipping" the node.
-
-Another optimisation that can occur is that of "C<EXACT> merging" which is
-where two consecutive C<EXACT> nodes are merged into a single
-regop. An even more aggressive form of this is that a branch
-sequence of the form C<EXACT BRANCH ... EXACT> can be converted into a
-C<TRIE-EXACT> regop.
-
-All of this occurs in the routine C<study_chunk()> which uses a special
-structure C<scan_data_t> to store the analysis that it has performed, and
-does the "peep-hole" optimisations as it goes.
-
-The code involved in C<study_chunk()> is extremely cryptic. Be careful. :-)
-
-=head2 Execution
-
-Execution of a regex generally involves two phases, the first being
-finding the start point in the string where we should match from,
-and the second being running the regop interpreter.
-
-If we can tell that there is no valid start point then we don't bother running
-interpreter at all. Likewise, if we know from the analysis phase that we
-cannot detect a short-cut to the start position, we go straight to the
-interpreter.
-
-The two entry points are C<re_intuit_start()> and C<pregexec()>. These routines
-have a somewhat incestuous relationship with overlap between their functions,
-and C<pregexec()> may even call C<re_intuit_start()> on its own. Nevertheless
-other parts of the perl source code may call into either, or both.
-
-Execution of the interpreter itself used to be recursive, but thanks to the
-efforts of Dave Mitchell in the 5.9.x development track, that has changed: now an
-internal stack is maintained on the heap and the routine is fully
-iterative. This can make it tricky as the code is quite conservative
-about what state it stores, with the result that two consecutive lines in the
-code can actually be running in totally different contexts due to the
-simulated recursion.
-
-=head3 Start position and no-match optimisations
-
-C<re_intuit_start()> is responsible for handling start points and no-match
-optimisations as determined by the results of the analysis done by
-C<study_chunk()> (and described in L<Peep-hole Optimisation and Analysis>).
-
-The basic structure of this routine is to try to find the start- and/or
-end-points of where the pattern could match, and to ensure that the string
-is long enough to match the pattern. It tries to use more efficient
-methods over less efficient methods and may involve considerable
-cross-checking of constraints to find the place in the string that matches.
-For instance it may try to determine that a given fixed string must be
-not only present but a certain number of chars before the end of the
-string, or whatever.
-
-It calls several other routines, such as C<fbm_instr()> which does
-Fast Boyer Moore matching and C<find_byclass()> which is responsible for
-finding the start using the first mandatory regop in the program.
-
-When the optimisation criteria have been satisfied, C<reg_try()> is called
-to perform the match.
-
-=head3 Program execution
-
-C<pregexec()> is the main entry point for running a regex. It contains
-support for initialising the regex interpreter's state, running
-C<re_intuit_start()> if needed, and running the interpreter on the string
-from various start positions as needed. When it is necessary to use
-the regex interpreter C<pregexec()> calls C<regtry()>.
-
-C<regtry()> is the entry point into the regex interpreter. It expects
-as arguments a pointer to a C<regmatch_info> structure and a pointer to
-a string. It returns an integer 1 for success and a 0 for failure.
-It is basically a set-up wrapper around C<regmatch()>.
-
-C<regmatch> is the main "recursive loop" of the interpreter. It is
-basically a giant switch statement that implements a state machine, where
-the possible states are the regops themselves, plus a number of additional
-intermediate and failure states. A few of the states are implemented as
-subroutines but the bulk are inline code.
-
-=head1 MISCELLANEOUS
-
-=head2 Unicode and Localisation Support
-
-When dealing with strings containing characters that cannot be represented
-using an eight-bit character set, perl uses an internal representation
-that is a permissive version of Unicode's UTF-8 encoding[2]. This uses single
-bytes to represent characters from the ASCII character set, and sequences
-of two or more bytes for all other characters. (See L<perlunitut>
-for more information about the relationship between UTF-8 and perl's
-encoding, utf8. The difference isn't important for this discussion.)
-
-No matter how you look at it, Unicode support is going to be a pain in a
-regex engine. Tricks that might be fine when you have 256 possible
-characters often won't scale to handle the size of the UTF-8 character
-set. Things you can take for granted with ASCII may not be true with
-Unicode. For instance, in ASCII, it is safe to assume that
-C<sizeof(char1) == sizeof(char2)>, but in UTF-8 it isn't. Unicode case folding is
-vastly more complex than the simple rules of ASCII, and even when not
-using Unicode but only localised single byte encodings, things can get
-tricky (for example, B<LATIN SMALL LETTER SHARP S> (U+00DF, E<szlig>)
-should match 'SS' in localised case-insensitive matching).
-
-Making things worse is that UTF-8 support was a later addition to the
-regex engine (as it was to perl) and this necessarily made things a lot
-more complicated. Obviously it is easier to design a regex engine with
-Unicode support in mind from the beginning than it is to retrofit it to
-one that wasn't.
-
-Nearly all regops that involve looking at the input string have
-two cases, one for UTF-8, and one not. In fact, it's often more complex
-than that, as the pattern may be UTF-8 as well.
-
-Care must be taken when making changes to make sure that you handle
-UTF-8 properly, both at compile time and at execution time, including
-when the string and pattern are mismatched.
-
-The following comment in F<regcomp.h> gives an example of exactly how
-tricky this can be:
-
- Two problematic code points in Unicode casefolding of EXACT nodes:
-
- U+0390 - GREEK SMALL LETTER IOTA WITH DIALYTIKA AND TONOS
- U+03B0 - GREEK SMALL LETTER UPSILON WITH DIALYTIKA AND TONOS
-
- which casefold to
-
- Unicode UTF-8
-
- U+03B9 U+0308 U+0301 0xCE 0xB9 0xCC 0x88 0xCC 0x81
- U+03C5 U+0308 U+0301 0xCF 0x85 0xCC 0x88 0xCC 0x81
-
- This means that in case-insensitive matching (or "loose matching",
- as Unicode calls it), an EXACTF of length six (the UTF-8 encoded
- byte length of the above casefolded versions) can match a target
- string of length two (the byte length of UTF-8 encoded U+0390 or
- U+03B0). This would rather mess up the minimum length computation.
-
- What we'll do is to look for the tail four bytes, and then peek
- at the preceding two bytes to see whether we need to decrease
- the minimum length by four (six minus two).
-
- Thanks to the design of UTF-8, there cannot be false matches:
- A sequence of valid UTF-8 bytes cannot be a subsequence of
- another valid sequence of UTF-8 bytes.
-
-
-=head2 Base Structures
-
-The C<regexp> structure described in L<perlreapi> is common to all
-regex engines. Two of its fields that are intended for the private use
-of the regex engine that compiled the pattern. These are the
-C<intflags> and pprivate members. The C<pprivate> is a void pointer to
-an arbitrary structure whose use and management is the responsibility
-of the compiling engine. perl will never modify either of these
-values. In the case of the stock engine the structure pointed to by
-C<pprivate> is called C<regexp_internal>.
-
-Its C<pprivate> and C<intflags> fields contain data
-specific to each engine.
-
-There are two structures used to store a compiled regular expression.
-One, the C<regexp> structure described in L<perlreapi> is populated by
-the engine currently being. used and some of its fields read by perl to
-implement things such as the stringification of C<qr//>.
-
-
-The other structure is pointed to be the C<regexp> struct's
-C<pprivate> and is in addition to C<intflags> in the same struct
-considered to be the property of the regex engine which compiled the
-regular expression;
-
-The regexp structure contains all the data that perl needs to be aware of
-to properly work with the regular expression. It includes data about
-optimisations that perl can use to determine if the regex engine should
-really be used, and various other control info that is needed to properly
-execute patterns in various contexts such as is the pattern anchored in
-some way, or what flags were used during the compile, or whether the
-program contains special constructs that perl needs to be aware of.
-
-In addition it contains two fields that are intended for the private use
-of the regex engine that compiled the pattern. These are the C<intflags>
-and pprivate members. The C<pprivate> is a void pointer to an arbitrary
-structure whose use and management is the responsibility of the compiling
-engine. perl will never modify either of these values.
-
-As mentioned earlier, in the case of the default engines, the C<pprivate>
-will be a pointer to a regexp_internal structure which holds the compiled
-program and any additional data that is private to the regex engine
-implementation.
-
-=head3 Perl's C<pprivate> structure
-
-The following structure is used as the C<pprivate> struct by perl's
-regex engine. Since it is specific to perl it is only of curiosity
-value to other engine implementations.
-
- typedef struct regexp_internal {
- regexp_paren_ofs *swap; /* Swap copy of *startp / *endp */
- U32 *offsets; /* offset annotations 20001228 MJD
- data about mapping the program to the
- string*/
- regnode *regstclass; /* Optional startclass as identified or constructed
- by the optimiser */
- struct reg_data *data; /* Additional miscellaneous data used by the program.
- Used to make it easier to clone and free arbitrary
- data that the regops need. Often the ARG field of
- a regop is an index into this structure */
- regnode program[1]; /* Unwarranted chumminess with compiler. */
- } regexp_internal;
-
-=over 5
-
-=item C<swap>
-
-C<swap> formerly was an extra set of startp/endp stored in a
-C<regexp_paren_ofs> struct. This was used when the last successful match
-was from the same pattern as the current pattern, so that a partial
-match didn't overwrite the previous match's results, but it caused a
-problem with re-entrant code such as trying to build the UTF-8 swashes.
-Currently unused and left for backward compatibility with 5.10.0.
-
-=item C<offsets>
-
-Offsets holds a mapping of offset in the C<program>
-to offset in the C<precomp> string. This is only used by ActiveState's
-visual regex debugger.
-
-=item C<regstclass>
-
-Special regop that is used by C<re_intuit_start()> to check if a pattern
-can match at a certain position. For instance if the regex engine knows
-that the pattern must start with a 'Z' then it can scan the string until
-it finds one and then launch the regex engine from there. The routine
-that handles this is called C<find_by_class()>. Sometimes this field
-points at a regop embedded in the program, and sometimes it points at
-an independent synthetic regop that has been constructed by the optimiser.
-
-=item C<data>
-
-This field points at a reg_data structure, which is defined as follows
-
- struct reg_data {
- U32 count;
- U8 *what;
- void* data[1];
- };
-
-This structure is used for handling data structures that the regex engine
-needs to handle specially during a clone or free operation on the compiled
-product. Each element in the data array has a corresponding element in the
-what array. During compilation regops that need special structures stored
-will add an element to each array using the add_data() routine and then store
-the index in the regop.
-
-=item C<program>
-
-Compiled program. Inlined into the structure so the entire struct can be
-treated as a single blob.
-
-=back
-
-=head1 SEE ALSO
-
-L<perlreapi>
-
-L<perlre>
-
-L<perlunitut>
-
-=head1 AUTHOR
-
-by Yves Orton, 2006.
-
-With excerpts from Perl, and contributions and suggestions from
-Ronald J. Kimball, Dave Mitchell, Dominic Dunlop, Mark Jason Dominus,
-Stephen McCamant, and David Landgren.
-
-=head1 LICENCE
-
-Same terms as Perl.
-
-=head1 REFERENCES
-
-[1] L<http://perl.plover.com/Rx/paper/>
-
-[2] L<http://www.unicode.org>
-
-=cut