Branch: refs/heads/yves/split_matched_state_regexp_struct
Home: https://github.com/Perl/perl5
Commit: 422fb1c70ab8662568b8875739843b6a6ba84b59
https://github.com/Perl/perl5/commit/422fb1c70ab8662568b8875739843b6a6ba84b59
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M pod/perldebguts.pod
M pp_ctl.c
M regcomp.c
M regcomp.h
M regcomp.sym
M regcomp_debug.c
M regexec.c
M regexp.h
M regnodes.h
M t/re/pat.t
M t/re/pat_rt_report.t
M t/re/re_tests
Log Message:
-----------
regcomp.c - Resolve issues clearing buffers in CURLYX (MAJOR-CHANGE)
CURLYX doesn't reset capture buffers properly. It is possible
for multiple buffers to be defined at once with values from
different iterations of the loop, which doesn't make sense really.
An example is this:
"foobarfoo"=~/((foo)|(bar))+/
after this matches $1 should equal $2 and $3 should be undefined,
or $1 should equal $3 and $2 should be undefined. Prior to this
patch this would not be the case.
The solution that this patches uses is to introduce a form of
"layered transactional storage" for paren data. The existing
pair of start/end data for capture data is extended with a
start_new/end_new pair. When the vast majority of our code wants
to check if a given capture buffer is defined they first check
"start_new/end_new", if either is -1 then they fall back to
whatever is in start/end.
When a capture buffer is CLOSEd the data is written into the
start_new/end_new pair instead of the start/end pair. When a CURLYX
loop is executing and has matched something (at least one "A" in
/A*B/ -- thus actually in WHILEM) it "commits" the start_new/end_new
data by writing it into start/end. When we begin a new iteration of
the loop we clear the start_new/end_new pairs that are contained by
the loop, by setting them to -1. If the loop fails then we roll back
as we used to. If the loop succeeds we continue. When we hit an END
block we commit everything.
Consider the example above. We start off with everything set to -1.
$1 = (-1,-1):(-1,-1)
$2 = (-1,-1):(-1,-1)
$3 = (-1,-1):(-1,-1)
In the first iteration we have matched "foo" and end up with this:
$1 = (-1,-1):( 0, 3)
$2 = (-1,-1):( 0, 3)
$3 = (-1,-1):(-1,-1)
We commit the results of $2 and $3, and then clear the new data in
the beginning of the next loop:
$1 = (-1,-1):( 0, 3)
$2 = ( 0, 3):(-1,-1)
$3 = (-1,-1):(-1,-1)
We then match "bar":
$1 = (-1,-1):( 0, 3)
$2 = ( 0, 3):(-1,-1)
$3 = (-1,-1):( 3, 7)
and then commit the result and clear the new data:
$1 = (-1,-1):( 0, 3)
$2 = (-1,-1):(-1,-1)
$3 = ( 3, 7):(-1,-1)
and then we match "foo" again:
$1 = (-1,-1):( 0, 3)
$2 = (-1,-1):( 7,10)
$3 = ( 3, 7):(-1,-1)
And we then commit. We do a regcppush here as normal.
$1 = (-1,-1):( 0, 3)
$2 = ( 7,10):( 7,10)
$3 = (-1,-1):(-1,-1)
We then clear it again, but since we don't match when we regcppop
we store the buffers back to the above layout. When we finally
hit the END buffer we also do a commit as well on all buffers, including
the 0th (for the full match).
Fixes GH Issue #18865, and adds tests for it and other things.
Commit: 668c2282e8f415b0b717c6cc59ee6cc940a8c5c3
https://github.com/Perl/perl5/commit/668c2282e8f415b0b717c6cc59ee6cc940a8c5c3
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M pod/perldebguts.pod
M regcomp.c
M regcomp.h
M regcomp.sym
M regcomp_debug.c
M regcomp_trie.c
M regexec.c
M regexp.h
M regnodes.h
M t/re/re_tests
Log Message:
-----------
regexec.c - teach BRANCH and BRANCHJ nodes to reset capture buffers
In /((a)(b)|(a))+/ we should not end up with $2 and $4 being set at
the same time. When a branch fails it should reset any capture buffers
that might be touched by its branch.
We change BRANCH and BRANCHJ to store the number of parens before the
branch, and the number of parens after the branch was completed. When
a BRANCH operation fails, we clear the buffers it contains before we
continue on.
It is a bit more complex than it should be because we have BRANCHJ
and BRANCH. (One of these days we should merge them together.)
This is also made somewhat more complex because TRIE nodes are actually
branches, and may need to track capture buffers also, at two levels.
The overall TRIE op, and for jump tries especially where we emulate
the behavior of branches. So we have to do the same clearing logic if
a trie branch fails as well.
Commit: 0745440c388b5b6dc36de45317c6a6cc13648e73
https://github.com/Perl/perl5/commit/0745440c388b5b6dc36de45317c6a6cc13648e73
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M pod/perldelta.pod
Log Message:
-----------
perldelta - add note about regex engine changes
capture buffer semantics should now be consistent.
Commit: 7c57ce86b0a857d6a44aff9a170b2ec56113432b
https://github.com/Perl/perl5/commit/7c57ce86b0a857d6a44aff9a170b2ec56113432b
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M regexec.c
M regexp.h
M t/re/re_tests
Log Message:
-----------
regexec.c - incredibly inefficient solution to backref problem
Backrefs to unclosed parens inside of a quantified group were not being
properly handled, which revealed we are not unrolling the paren state properly
on failure and backtracking.
Much of the code assumes that when we execute a "conditional" operation (where
more than one thing could match) that we need not concern ourself with the
paren state unless the conditional operation itself represents a paren, and
that generally opcodes only needed to concern themselves with parens to their
right. When you exclude backrefs from the equation this is broadly reasonable
(i think), as on failure we typically dont care about the state of the paren
buffers. They either get reset as we find a new different accepting pathway,
or their state is irrelevant if the overal match is rejected (eg it fails).
However backreferences are different. Consider the following pattern
from the tests
"xa=xaaa" =~ /^(xa|=?\1a){2}\z/
in the first iteration through this the first branch matches, and in fact
because the \1 is in the second branch it can't match on the first iteration
at all. After this $1 = "xa". We then perform the second iteration. "xa" does
not match "=xaaa" so we fall to the second branch. The '=?' matches, but sets
up a backtracking action to not match if the rest of the pattern does not
match. \1 matches 'xa', and then the 'a' matches, leaving an unmatched 'a' in
the string, we exit the quantifier loop with $1 = "=xaa" and match \z against
the remaining "a" in the pattern, and fail.
Here is where things go wrong in the old code, we unwind to the outer loop,
but we do not unwind the paren state. We then unwind further into the 2nds
iteration of the loop, to the '=?' where we then try to match the tail with
the quantifier matching the empty string. We then match the old $1 (which was
not unwound) as "=xaa", and then the "a" matches, and we are the end of the
string and we have incorrectly accpeted this string as matching the pattern.
What should have happend was when the \1 was resolved the second time it
should have returned the same string as it did when the =? matched '=', which
then would have resulted in the tail matching again, and etc, eventually
unwinding the entire pattern when the second iteration failed entirely.
This patch is very crude. It simple pushes the state of the parens and creates
and unwind point for every case where we do a transition to a B or _next
operation, and we make the corresponding _next_fail do the appropriate
unwinding. The objective was to achieve correctness and then work towards
making it more efficient. We almost certainly overstore items on the stack.
In a future patch we can perhaps keep track of the unclosed parens before the
relevant operators and make sure that they are properly pushed and unwound at
the correct times.
Commit: db2e22ec8c53d9880d646a02782187c601982198
https://github.com/Perl/perl5/commit/db2e22ec8c53d9880d646a02782187c601982198
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M regcomp.c
M regcomp.h
M regcomp.sym
M regcomp_internal.h
M regexec.c
M regexp.h
M regnodes.h
Log Message:
-----------
regexec.c - make REF into a backtracking state
This way we can do the required paren restoration only when it is in use. When
we match a REF type node which is potentially a reference to an unclosed paren
we push the match context information, currently for "everything", but in a
future patch we can teach it to be more efficient by adding a new parameter to
the REF regop to track which parens it should save.
This converts the backtracking changes from the previous commit, so that it is
run only when specifically enabled via the define RE_PESSIMISTIC_PARENS which
is by default 0. We don't make the new fields in the struct conditional as the
stack frames are large and our changes don't make any real difference and it
keeps things simpler to not have conditional members, especially since some of
the structures have to line up with each other.
If enabling RE_PESSIMISTIC_PARENS fixes a backtracking bug then it means
something is sensitive to us not necessarily restoring the parens properly on
failure. We make some assumptions that the paren state after a failing state
will be corrected by a future successful state, or that the state of the
parens is irrelevant as we will fail anyway. This can be made not true by
EVAL, backrefs, and potentially some other scenarios. Thus I have left this
inefficient logic in place but guarded by the flag.
Commit: c825104c1afb888b97e61867992ad5c547bd1d8d
https://github.com/Perl/perl5/commit/c825104c1afb888b97e61867992ad5c547bd1d8d
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M embed.fnc
M embed.h
M pod/perldebguts.pod
M proto.h
M regcomp.c
M regcomp.h
M regcomp.sym
M regcomp_debug.c
M regcomp_study.c
M regcomp_trie.c
M regexec.c
M reginline.h
M regnodes.h
Log Message:
-----------
regex engine - simplify regnode structures and make them consistent
This eliminates the regnode_2L data structure, and merges it with the older
regnode_2 data structure. At the same time it makes each "arg" property of the
various regnode types that have one be consistently structured as an anonymous
union like this:
union {
U32 arg1u;
I32 arg2i;
struct {
U16 arg1a;
U16 arg1b;
};
};
We then expose four macros for accessing each slot: ARG1u() ARG1i() and
ARG1a() and ARG1b(). Code then explicitly designates which they want. The old
logic used ARG() to access an U32 arg1, and ARG1() to access an I32 arg1,
which was confusing to say the least. The regnode_2L structure had a U32 arg1,
and I32 arg2, and the regnode_2 data strucutre had two I32 args. With the new
set of macros we use the regnode_2 for both, and use the appropriate macros to
show whether we want to signed or unsigned values.
This also renames the regnode_4 to regnode_3. The 3 stands for "three 32-bit
args". However as each slot can also store two U16s, a regnode_3 can hold up
to 6 U16s, or as 3 I32's, or a combination. For instance the CURLY style nodes
use regnode_3 to store 4 values, ARG1i() for min count, ARG2i() for max count
and ARG3a() and ARG3b() for parens before and inside the quantifier.
It also changes the functions reganode() to reg1node() and changes reg2Lanode()
to reg2node(). The 2L thing was just confusing.
Commit: 7cbf8c2f59e8c5b6abca0bed32e2905f58ad36cf
https://github.com/Perl/perl5/commit/7cbf8c2f59e8c5b6abca0bed32e2905f58ad36cf
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M pod/perldebguts.pod
M regcomp.c
M regcomp.sym
M regcomp_debug.c
M regexec.c
M regnodes.h
M t/re/pat_advanced.t
Log Message:
-----------
regcomp.c - extend REF to hold the paren it needs to regcppush
this way we can avoid pushing every buffer, we only need to push
the nestroot of the ref.
Commit: f0cfd368693af69fbce7573ac0b498e50d1a1f29
https://github.com/Perl/perl5/commit/f0cfd368693af69fbce7573ac0b498e50d1a1f29
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M regexec.c
Log Message:
-----------
regexec.c - minor cleanup of CAPTURE_xxx code
I left a bit of debugging and commented out code in the PR. This
removes or reworks that code to not run in production mode.
Commit: 49e6c5728f8be267ac3043d1372687db5a0fbdaa
https://github.com/Perl/perl5/commit/49e6c5728f8be267ac3043d1372687db5a0fbdaa
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M dump.c
M regcomp.c
M regexec.c
M regexp.h
Log Message:
-----------
regcomp.c - Use RXp_OFFSp() to access offset data
This insulates access to the regexp match offset data so we can
fix the define later and move the offset structure into a new struct.
The RXp_OFFSp() was introduced in a recent commit to deliberately
break anything using RXp_OFFS() directly. It is hard to type
deliberately, nothing but the internals should use it. Everything
else should use one of the wrappers around it.
Commit: 36cec2119d558173b0aa958b5e3a34b6d3a3ee12
https://github.com/Perl/perl5/commit/36cec2119d558173b0aa958b5e3a34b6d3a3ee12
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M regexp.h
Log Message:
-----------
regexp.h - standardize macros, and parenthesize parameters
Obviously this isn't required as we build fine. But doing this
future proofs us to other changes.
Commit: f43a6b67aafd53be2ed9cbb74d200f54a18dd4f9
https://github.com/Perl/perl5/commit/f43a6b67aafd53be2ed9cbb74d200f54a18dd4f9
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M dump.c
M regcomp_debug.c
M regexec.c
Log Message:
-----------
regexec.c - use RXp_LASTPAREN(rex) to access rex->lastparen
This field will be moving to a new struct. Converting this to a macro
will make that move easier.
Commit: 1c82e0c50b1ddccd25cb6c97d9f05e7b8869bb18
https://github.com/Perl/perl5/commit/1c82e0c50b1ddccd25cb6c97d9f05e7b8869bb18
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M regexp.h
Log Message:
-----------
regexp.h - add missing defines
We were missing various RXp_XXXX() and RX_XXXX() macros. This adds
them so we can use them in places where we are unreasonable intimate
with the regexp struct internals.
Commit: e96d39bbd2453982bf0ff6ca0dd7057e7573af1a
https://github.com/Perl/perl5/commit/e96d39bbd2453982bf0ff6ca0dd7057e7573af1a
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M dump.c
Log Message:
-----------
dump.c - use RXp_ macros to access regexp struct members
We will move some of these members out of the regexp structure
into a new sub structucture. This isolates those changes to the
macro definitions
Commit: fbce07f414658892c0fff1b901e377517848e7cc
https://github.com/Perl/perl5/commit/fbce07f414658892c0fff1b901e377517848e7cc
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M regexec.c
Log Message:
-----------
regexec.c - use RXp_LASTCLOSEPAREN(r) to access r->lastcloseparen
We will move this struct member into a new struct in a future patch,
and using the macros means we can reduce the number of places that
needs to be explcitly aware of the new structure.
Commit: bc85b371644de56b676fb5ec47fbce970eb42bad
https://github.com/Perl/perl5/commit/bc85b371644de56b676fb5ec47fbce970eb42bad
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M dump.c
Log Message:
-----------
dump.c - fixup missing case
Commit: 5d00e9f8efb429a355ebc6a8d6ff585b976af823
https://github.com/Perl/perl5/commit/5d00e9f8efb429a355ebc6a8d6ff585b976af823
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M regexec.c
Log Message:
-----------
regexec.c - use macro to access rex->subbeg
We will move this member to a new struct in the near future,
converting all uses to a macro isolates that change.
Commit: b19b1dc972ee925feb9c3e2cfebd138f7341ec14
https://github.com/Perl/perl5/commit/b19b1dc972ee925feb9c3e2cfebd138f7341ec14
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M regexec.c
Log Message:
-----------
regexec.c - use RXp_SUBLEN(ret) for ret->sublen
This member of the regexp structure will be moved to a new
structure in the near future. Converting to use the macro
will make this change easier to manage.
Commit: 24f141ee214453e9dba374bee65fac96a71ba586
https://github.com/Perl/perl5/commit/24f141ee214453e9dba374bee65fac96a71ba586
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M regexec.c
Log Message:
-----------
regexec.c - use RXp_SUBOFFSET(rx) instead of rx->suboffset
We will migrate this struct member to a new struct in the near future
this change will make that patch more minimal and hide the gory details.
Commit: 374ed4128540512f5a8c0adc00ba8a628156ebdd
https://github.com/Perl/perl5/commit/374ed4128540512f5a8c0adc00ba8a628156ebdd
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M regexec.c
Log Message:
-----------
regexec.c - use RXp_SUBCOFFSET instead of rx->subcoffset
This member of the regexp struct will soon be migrated to a new
independent structure. This change ensure that when we do the migration
the changes are restricted to the least code possible.
Commit: 47bf790ba20746ecfae05bfdf16291d03a15f6cf
https://github.com/Perl/perl5/commit/47bf790ba20746ecfae05bfdf16291d03a15f6cf
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M regexec.c
Log Message:
-----------
regexec.c - use RXp_SAVED_COPY(rex) instead of rex->saved_copy
We will migrate this member to a new structure in the near future,
wrapping with a macro makes that migration simpler and less invasive.
Commit: bf5ba5d7f3df1042eba07de70b4ca74f35d6481b
https://github.com/Perl/perl5/commit/bf5ba5d7f3df1042eba07de70b4ca74f35d6481b
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M regcomp.c
Log Message:
-----------
regcomp.c - use macro wrappers to minimize impact of struct split
We will move various members of the regexp structure to a new
structure which just contains information about the match. Wrapping
the members in the standard macros means that change can be made
less invasive. We already did all of this in regexec.c
Commit: 6e591e98d6d056000274eeb09c4049a0d922f3db
https://github.com/Perl/perl5/commit/6e591e98d6d056000274eeb09c4049a0d922f3db
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M regexp.h
Log Message:
-----------
regexp.h - use RXp_SAVED_COPY(ret) to access ret->saved_copy
This member is moving out of the regexp structure and into a
new structure in the very near future. Using the macro to access
it minimizes the size of that change.
Commit: ece1c4a012ea9c9a708d623469ae9753acdd1107
https://github.com/Perl/perl5/commit/ece1c4a012ea9c9a708d623469ae9753acdd1107
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M regexp.h
Log Message:
-----------
regexp.h - fixup mistake in comment
rex->maxlen holds the maximum length the pattern can match, not the
minimum. The copy was obviously copied from the rex->minlen case,
so fix it to be correct.
Commit: 127a0c0938c3299ea16984e3f11bbb7672e988f5
https://github.com/Perl/perl5/commit/127a0c0938c3299ea16984e3f11bbb7672e988f5
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M regcomp.c
M regexp.h
Log Message:
-----------
WIP
Commit: d93664dbe03390148055bb7b39b97eb78dfac162
https://github.com/Perl/perl5/commit/d93664dbe03390148055bb7b39b97eb78dfac162
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M dump.c
M ext/B/B.xs
M perl.h
M regcomp.c
M regexp.h
M sv.h
M sv_inline.h
Log Message:
-----------
WIP - add SVt_RXMO to store regex match offsets
Commit: 18f4108b80a911aab926dd17b005333eba8f0ca4
https://github.com/Perl/perl5/commit/18f4108b80a911aab926dd17b005333eba8f0ca4
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M dump.c
M embed.fnc
M embed.h
M proto.h
Log Message:
-----------
dump.c - add a function that returns the name for a SVt_ type
We have the data in dump.c but we don't seem to use it in very
many places.
Commit: 6710616c977c9006fc80d24d2180b6900be85fb8
https://github.com/Perl/perl5/commit/6710616c977c9006fc80d24d2180b6900be85fb8
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M sv.c
M sv_inline.h
Log Message:
-----------
sv.c - provide better error messages for sv_upgrade and newSV_type()
newSV_type() claimed it was actually sv_upgrade, which it isn't.
Also the error message is less than helpful when someone is adding
a new type. So show a better error message and distinguish between
"I don't know how to handle this new type you have added" and
"That type id is simply not valid" in both cases, with the correct
C sub names in the error message.
Commit: 003beb2de4effa85eb35ae84d26c92b8dde5ff68
https://github.com/Perl/perl5/commit/003beb2de4effa85eb35ae84d26c92b8dde5ff68
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M MANIFEST
M dump.c
M ext/B/B.pm
M ext/XS-APItest/APItest.xs
A ext/XS-APItest/t/rxmo.t
M perl.h
M regexp.h
M sv.h
M sv_inline.h
Log Message:
-----------
WIP - RXMO works-ish
Commit: 8c371603ca8e6f418c4638a268deae75b855a927
https://github.com/Perl/perl5/commit/8c371603ca8e6f418c4638a268deae75b855a927
Author: Yves Orton <[email protected]>
Date: 2023-01-29 (Sun, 29 Jan 2023)
Changed paths:
M dump.c
M ext/B/B.pm
M ext/B/B.xs
M ext/B/t/b.t
M intrpvar.h
M lib/B/Deparse.pm
M op.c
M op.h
M pod/perl5220delta.pod
M pp_ctl.c
M pp_hot.c
M regcomp.c
M regexec.c
M regexp.h
M sv.c
Log Message:
-----------
WIP
Compare: https://github.com/Perl/perl5/compare/8186a6e0aacd...8c371603ca8e
