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, 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>).
target string, and determines whether or not the string satisfies the
constraints. See L<perlre> for a full definition of the language.
-So in less grandiose terms the first part of the job is to turn a pattern into
+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.
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 class
+additional 4-byte (32-bit) bitmap indicating which POSIX char classes
have been included.
regnode_charclass_class U32 arg1;
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
+"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()>, C<regbranch()>
+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
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
+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 have failed.
+the engine will know that the entire set of branches has failed.
=head3 Peep-hole Optimisation and Analysis
=back
-Another form of optimisation that can occur is post-parse "peep-hole"
-optimisations, where inefficient constructs are replaced by
-more efficient constructs. An example of this are C<TAIL> regops which are used
-during parsing to mark the end of branches and the end of groups. 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 thing that the C<TAIL> points to, thus "skipping" the node.
+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
and C<pregexec()> may even call C<re_intuit_start()> on its own. Nevertheless
other parts of the the perl source code may call into either, or both.
-Execution of the interpreter itself used to be recursive. Due to the
-efforts of Dave Mitchell in the 5.9.x development track, it is now iterative. Now an
+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 that two consecutive lines in the
=head2 Base Structures
There are two structures used to store a compiled regular expression.
-One, the regexp structure is considered to be perl's property, and the
+One, the regexp structure, is considered to be perl's property, and the
other is considered to be the property of the regex engine which
compiled the regular expression; in the case of the stock engine this
structure is called regexp_internal.
typedef struct regexp {
/* what engine created this regexp? */
- const struct regexp_engine* engine;
+ const struct regexp_engine* engine;
/* Information about the match that the perl core uses to manage things */
U32 extflags; /* Flags used both externally and internally */
=item C<engine>
This field points at a regexp_engine structure which contains pointers
-to the subroutine that are to be used for performing a match. It
-is the compiling routines responsibility to populate this field before
+to the subroutines that are to be used for performing a match. It
+is the compiling routine's responsibility to populate this field before
returning the regexp object.
-=item C<precomp> C<prelen>
+=item C<precomp> C<prelen>
Used for debugging purposes. C<precomp> holds a copy of the pattern
-that was compiled.
+that was compiled.
=item C<extflags>
=item C<minlen> C<minlenret>
-C<minlen> is the minimum string length required for the pattern to match.
-This is used to prune the search space by not bothering to match any
-closer to the end of a string than would allow a match. For instance
-there is no point in even starting the regex engine if the minlen is
-10 but the string is only 5 characters long. There is no way that the
+C<minlen> is the minimum string length required for the pattern to match.
+This is used to prune the search space by not bothering to match any
+closer to the end of a string than would allow a match. For instance
+there is no point in even starting the regex engine if the minlen is
+10 but the string is only 5 characters long. There is no way that the
pattern can match.
C<minlenret> is the minimum length of the string that would be found
-in $& after a match.
+in $& after a match.
The difference between C<minlen> and C<minlenret> can be seen in the
following pattern:
/ns(?=\d)/
-where the C<minlen> would be 3 but the minlen ret would only be 2 as
+where the C<minlen> would be 3 but the minlen ret would only be 2 as
the \d is required to match but is not actually included in the matched
content. This distinction is particularly important as the substitution
logic uses the C<minlenret> to tell whether it can do in-place substition
Fast-Boyer-Moore searches on the string to find out if its worth using
the regex engine at all, and if so where in the string to search.
-=item C<startp>, C<endp>,
+=item C<startp>, C<endp>
These fields store arrays that are used to hold the offsets of the begining
and end of each capture group that has matched. -1 is used to indicate no match.
=item C<seen_evals>
-This stores the number of eval groups in the pattern. This is used
-for security purposes when embedding compiled regexes into larger
+This stores the number of eval groups in the pattern. This is used
+for security purposes when embedding compiled regexes into larger
patterns.
=back
=head3 Engine Private Data About Pattern
-Additionally regexp.h contains the following "private" definition which is perl
-specific and is only of curiosity value to other engine implementations.
+Additionally, regexp.h contains the following "private" definition which is
+perl-specific and is only of curiosity value to other engine implementations.
typedef struct regexp_internal {
regexp_paren_ofs *swap; /* Swap copy of *startp / *endp */
=item C<swap>
C<swap> is an extra set of startp/endp stored in a C<regexp_paren_ofs>
-struct. This is used when the last successful match was from same pattern
+struct. This is used when the last successful match was from the same pattern
as the current pattern, so that a partial match doesn't overwrite the
previous match's results. When this field is data filled the matching
engine will swap buffers before every match attempt. If the match fails,
=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 ActiveStates
+to offset in the C<precomp> string. This is only used by ActiveState's
visual regex debugger.
=item C<regstclass>
#endif
} regexp_engine;
-When a regexp is compiled its C<engine> field is then set to point at
+When a regexp is compiled, its C<engine> field is then set to point at
the appropriate structure so that when it needs to be used Perl can find
the right routines to do so.
In order to install a new regexp handler, C<$^H{regcomp}> is set
to an integer which (when casted appropriately) resolves to one of these
-structures. When compiling the C<comp> method is executed, and the
-resulting regexp structures engine field is expected to point back at
+structures. When compiling, the C<comp> method is executed, and the
+resulting regexp structure's engine field is expected to point back at
the same structure.
The pTHX_ symbol in the definition is a macro used by perl under threading
pm and return a pointer to a prepared regexp structure that can perform
the match.
+The utf8'ness of the string can be found by testing
+
+ pm->op_pmdynflags & PMdf_CMP_UTF8
+
+Additional various flags reflecting the modifiers used are contained in
+
+ pm->op_pmflags
+
+some of these have exact equivelents in re->extflags. See regcomp.h and op.h
+for details of these values.
+
=item exec
I32 exec(regexp* prog,
Find the start position where a regex match should be attempted,
or possibly whether the regex engine should not be run because the
pattern can't match. This is called as appropriate by the core
-depending on the values of the extflags member of the regexp
+depending on the values of the extflags member of the regexp
structure.
=item checkstr
Called by perl when it is freeing a regexp pattern so that the engine
can release any resources pointed to by the C<pprivate> member of the
-regexp structure. This is only responsible for freeing private data,
+regexp structure. This is only responsible for freeing private data;
perl will handle releasing anything else contained in the regexp structure.
=item dupe
duplication of any private data pointed to by the C<pprivate> member of
the regexp structure. It will be called with the preconstructed new
regexp structure as an argument, the C<pprivate> member will point at
-the B<old> private structue, and it is this routines responsibility to
+the B<old> private structue, and it is this routine's responsibility to
construct a copy and return a pointer to it (which perl will then use to
overwrite the field as passed to this routine.)
Any patch that adds data items to the regexp will need to include
changes to F<sv.c> (C<Perl_re_dup()>) and F<regcomp.c> (C<pregfree()>). This
-involves freeing or cloning items in the regexes data array based
+involves freeing or cloning items in the regexp's data array based
on the data item's type.
=head1 SEE ALSO
projects / p5sagit/p5-mst-13.2.git / blobdiff