edicl/cl-ppcre — pull request #18 by nbtrap (2014-03-01 14:01:39+00:00)
Title: Merge subpattern references

Subpattern references enable the matching of self-similar strings by
way of recursion. Unlike backreferences, which refer to the string
matched by a register, subpattern references refer to the pattern
contained within the register and cause the regex engine to recurse,
as though by an actual function call, to the referenced subpattern.

SYNTAX

A subpattern reference node has the form

(:SUBPATTERN-REFERENCE )

where is a positive fixnum denoting a register number or a
string or symbol denoting a register name.

Using the Perl syntax, a subpattern reference looks like

(?N)
or
(?&NAME)

where N is a positive (decimal) integer and NAME is a register name.

API CHANGES

There are no API changes.

KNOWN ISSUES

Perl Incompatibilities
======================
The semantics of subpattern references (or "sub calls") in Perl are
not well defined. In particular, as of version 5.19.9, the
interaction between subpattern references and backreferences is
inconsistent. This issue was recently raised on the p5p mailing
list, and the Perl devs seem to be seriously considering adopting
the semantics implemented here. See
https://rt.perl.org/Public/Bug/Display.html?id=121299 for details.

Embedded Modifiers
==================
The interaction between subpattern references and embedded modifiers
(e.g. :CASE-INSENSITIVE-P) is undefined for now and will be
addressed in a future release.

AllegroCL Compatibility Mode
===========================
So far as I know, the AllegroCL compatibility mode (enabled by
adding :USE-ACL-REGEXP2-ENGINE to *FEATURES* before compiling) does
not support this feature.

Other Bugs
==========
Several outstanding bugs are known to at least indirectly affect
subpattern references. Cf. #17 and #12, for example.

IMPLEMENTATION DETAILS

During the match phase, the subpattern reference closure calls the
register closure, passing it an extra argument: the match
continuation.

When the register closure sees that it has been called with an extra
argument, it knows that it has been entered via subpattern
reference. At this point, it saves the state of the local
registers' offsets and creates new dynamic "bindings" for them.
Then it calls the register's inner matcher, restoring the register
offsets state upon return therefrom. If the inner matcher has
succeeded, the subpattern reference's continuation is called.

The presence of one or more subpattern references precludes certain
optimizations. However, the performance for existing code (i.e.,
for regular expressions not containing subpattern references) should
be unaffected hereby.

OTHER CHANGES

The testing code has been overhauled. Of note:

1. The Perl script that generates many of tests has been modified,
among other things, to print results for as many capture groups as
are defined by each regex, but no more. (The purpose of this was
to support tests involving arbitrarily many capture groups.)
Thus, much of perltestdata file seems to have changed, but it's
mostly superficial.

2. Perl tests are now run with *ALLOW-NAMED-REGISTERS* bound to T
when the regex contains one or more named registers.

3. Many more tests have been added to *TESTS-TO-SKIP*. These are
by and large a result of Perl's undefined behavior vis-a-vis
subpattern references.