Corvus/Regex/Vm.pm

filter: Statementstmt 58.4% 467 / 799 Branchbran 47.9% 279 / 582 Conditioncond 37.2% 112 / 301 MC/DCmcdc 15.5% 28 / 180 Subroutinesub 87.5% 42 / 48 Podpod 0.0% 0 / 3 totaltotal 48.5% 928 / 1913 CC 419 SCAR 74.3
CC
419
Cov
51%
_run
4932.8
_first_chars
272.0
_emit
191.5
CRAP 1680.3
↑ Summary Corvus/Collecting.pm »
1 package JSON::Schema::Corvus::Regex::Vm;
2  
3 # The backtracking matcher for the patterns that Perl's own engine is not given: a port of the Go port's compile.go and
4 # vm.go. It runs every pattern exactly as ECMA-262 says, and keeps a limit of time.
5 #
6 # The text is an array of code points (with the u flag) or of UTF-16 code units (without it), so a position is an
7 # index into it. Four things keep the matcher from the time a backtracking matcher can take, as in the Go port: a
8 # repetition whose body cannot consume a character is run once or not at all (simplify); a counted loop gives up at a
9 # position from which the rest of the pattern needs more text than is left (needs); a way the next character rules
10 # out is not taken (quick); and where the pattern has no backreference the matcher remembers the places from which
11 # every way has failed (memo), so a repetition inside a repetition takes time proportional to the pattern times the
12 # text. What is left is ended by the limit of the match.
13  
14 4 ▶use 5.026;
Subroutine BEGIN: called CC=1 SCAR=0.0
15 4 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
16 4 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
17 4 ▶use Time::HiRes ();
Subroutine BEGIN: called CC=1 SCAR=0.0
18 4 ▶use JSON::Schema::Corvus::Regex::Charset ();
Subroutine BEGIN: called CC=1 SCAR=0.0
19  
20 # Opcodes.
21 4 ▶use constant {
Subroutine BEGIN: called CC=1 SCAR=0.0
22 4 OP_CHAR => 0, OP_CHAR_BACK => 1, OP_SET => 2, OP_SET_BACK => 3, OP_FAIL => 4, OP_BOL => 5, OP_EOL => 6,
23 OP_WB => 7, OP_NWB => 8, OP_LINE_START => 9, OP_LINE_END => 10, OP_WB_FOLD => 11, OP_NWB_FOLD => 12,
24 OP_JMP => 13, OP_SPLIT => 14, OP_SAVE_TMP => 15, OP_CAPTURE => 16, OP_CLEAR => 17, OP_BACKREF => 18,
25 OP_BACKREF_BACK => 19, OP_BACKREF_FOLD => 20, OP_BACKREF_FOLD_BACK => 21, OP_LOOK => 22, OP_LOOK_OK => 23,
26 OP_LOOK_FAIL => 24, OP_REP => 25, OP_REP_LAZY => 26, OP_LOOP_INIT => 27, OP_LOOP => 28, OP_LOOP_ITER => 29,
27 OP_MATCH => 30,
28 4 };
29  
30 # The fields of an instruction (an array).
31 4 ▶use constant { I_OP => 0, I_X => 1, I_Y => 2, I_A => 3, I_B => 4, I_R => 5, I_SET => 6, I_MIN => 7, I_MAX => 8,
Subroutine BEGIN: called CC=1 SCAR=0.0
32 4 I_FLAG => 9, I_M => 10, I_NEED => 11, I_ITER => 12 };
33  
34 # Entries of the backtracking stack: [kind, pc, pos, a].
35 4 ▶use constant { E_CHOICE => 0, E_REP => 1, E_REP_LAZY => 2, E_LOOK => 3, E_LOOK_NEG => 4, E_MARK => 5, E_TMP => 6,
Subroutine BEGIN: called CC=1 SCAR=0.0
36 4 E_CAP => 7, E_COUNTER => 8 };
37  
38 4 ▶use constant UNBOUNDED => -1;
Subroutine BEGIN: called CC=1 SCAR=0.0
39 4 ▶use constant NO_MATCH => 1 << 30;
Subroutine BEGIN: called CC=1 SCAR=0.0
40 # The number of steps between two looks at the clock, and the most entries the stack of a match with a limit may hold.
41 4 ▶use constant { CHECK_EVERY => 1 << 12, MAX_STACK => 1 << 20 };
Subroutine BEGIN: called CC=1 SCAR=0.0
42 # The number of loops whose state a memo point can tell apart; the largest memory of failed places, in bits; the steps
43 # for each position of the text that a match makes before it takes the memory into use; the depth of the stack beyond
44 # which a memo point is not marked.
45 4 ▶use constant { MAX_MEMO_LOOPS => 2, MAX_MEMO_BITS => 1 << 26, MEMO_STEPS_PER_POSITION => 64,
Subroutine BEGIN: called CC=1 SCAR=0.0
46 4 MAX_MARK_DEPTH => (1 << 20) / 2 };
47  
48 4 my $C = 'JSON::Schema::Corvus::Regex::Charset';
49  
50 # --- Compilation ---
51  
52 # A program for the tree of a pattern read with or without the u flag.
53 2 ▶sub compile_program {
Subroutine compile_program: called CC=7 SCAR=22.4
Pod undocumented
54 2 my ($root, $unicode) = @_;
55 2 $root = _simplify($root, []);
56 2 my %referenced;
57 2 _collect_backrefs($root, \%referenced);
58 # Slots follow group order, so the groups inside any one subtree take a contiguous range of slots.
59 2 my %tracked;
60 2 my $slot = 0;
61 0 $tracked{$_} = $slot++ for sort { $a <=> $b } keys %referenced;
62 2 ▶ my $c = { insts => [], tracked => \%tracked, loops => 0, unicode => $unicode ? 1 : 0, memo => !%tracked,
Branch: 1 branch
BranchTrueFalseTotal
$unicode ? : 2 0 2
63 open => [], points => [] };
64 2 _emit($c, $root, 0);
65 2 _add($c, [OP_MATCH]);
66 my $p = {
67 insts => $c->{insts}, groups => scalar keys %tracked, loops => $c->{loops}, units => $unicode ? 0 : 1,
68 points => $c->{points},
69 2 ▶ };
Branch: 1 branch
BranchTrueFalseTotal
$unicode ? : 2 0 2
70 2 $p->{need} = _set_needs($p->{insts});
71 2 $p->{quick} = _set_quick($p->{insts});
72 2 $p->{anchored} = _starts_at_bol($root);
73 2 ▶ if (!$p->{anchored}) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($p->{"anchored"}) 0 2 2
74 0 my ($pairs, $empty, $ok) = _first_chars($root, []);
75 0 ▶ $p->{first} = JSON::Schema::Corvus::Regex::Charset::new_set($pairs, 0) if $ok && !$empty;
Branch: 1 branch
BranchTrueFalseTotal
if $ok and not $empty 0 0 0
Condition0%0/3
$ok and not $empty
!ll&&!rl&&r
000
MC/DC0%0/2
$ok and not $empty
$ok not $empty
Truth table0%0/3
A and not(B)
A= $okB= not $empty
ABresult
0X0
100
111
76 }
77 2 return bless $p, __PACKAGE__;
78 }
79  
80 # The tree with two rewrites V8 makes, neither of which changes what the pattern matches or what any group holds: a
81 # backreference to a group it is inside is the empty string (the group is not set until it closes, and a repetition
82 # clears it at the start of each iteration), and a repetition whose body cannot consume a character is the body once
83 # (a minimum of one or more) or nothing (a minimum of zero).
84 57 ▶sub _simplify {
Subroutine _simplify: called CC=12 SCAR=26.5
85 57 my ($n, $open) = @_;
86 57 ▶ if ($n->{kind} eq 'backref') {
Branch: 1 branch
BranchTrueFalseTotal
if ($n->{"kind"} eq "backref") 4 53 57
87 4 for my $g (@{ $n->{groups} }) {
88 0 ▶ return $n unless grep { $_ == $g } @$open;
Branch: 1 branch
BranchTrueFalseTotal
unless grep {$_ == $g;} @$open 4 0 4
89 }
90 0 return { kind => 'empty' };
91 }
92 53 ▶ return $n unless $n->{subs} && @{ $n->{subs} };
Branch: 1 branch
BranchTrueFalseTotal
unless $n->{"subs"} and @{$n->{"subs"};} 20 33 53
Condition66%2/3
$n->{"subs"} and @{$n->{"subs"};}
!ll&&!rl&&r
20033
MC/DC50%1/2
$n->{"subs"} and @{$n->{"subs"};}
$n->{"subs"} @{$n->{"subs"};}
Truth table66%2/3
A and B
A= $n->{"subs"}B= @{$n->{"subs"};}
ABresult
0X0
100
111
93 33 ▶ $open = [ @$open, $n->{group} ] if $n->{kind} eq 'group' && $n->{group};
Branch: 1 branch
BranchTrueFalseTotal
if $n->{"kind"} eq "group" and $n->{"group"} 4 29 33
Condition100%3/3
$n->{"kind"} eq "group" and $n->{"group"}
!ll&&!rl&&r
2544
MC/DC100%2/2
$n->{"kind"} eq "group" and $n->{"group"}
$n->{"kind"} eq "group" $n->{"group"}
Truth table100%3/3
A and B
A= $n->{"kind"} eq "group"B= $n->{"group"}
ABresult
0X0
100
111
94 33 my @subs = map { _simplify($_, $open) } @{ $n->{subs} };
95 33 my $out = { %$n, subs => \@subs };
96 33 ▶ if ($out->{kind} eq 'repeat' && $out->{max} != 0 && !_consumes($subs[0])) {
Branch: 1 branch
BranchTrueFalseTotal
if ($out->{"kind"} eq "repeat" and $out->{"max"} != 0 and not _consumes($subs[0])) 0 33 33
Condition66%4/6
$out->{"kind"} eq "repeat" and $out->{"max"} != 0 and not _consumes($subs[0])
!ll&&!rl&&r
18150
$out->{"kind"} eq "repeat" and $out->{"max"} != 0
!ll&&!rl&&r
18015
MC/DC0%0/3
$out->{"kind"} eq "repeat" and $out->{"max"} != 0 and not _consumes($subs[0])
$out->{"kind"} eq "repeat" $out->{"max"} != 0 not _consumes($subs[0])
Truth table50%2/4
A and B and not(C)
A= $out->{"kind"} eq "repeat"B= $out->{"max"} != 0C= not _consumes($subs[0])
ABCresult
0XX0
10X0
1100
1111
97 0 ▶ return $out->{min} == 0 ? { kind => 'empty' } : $subs[0];
Branch: 1 branch
BranchTrueFalseTotal
$out->{'min'} == 0 ? : 0 0 0
98 }
99 33 return $out;
100 }
101  
102 # Whether n can match one character or more (erring towards true).
103 31 ▶sub _consumes {
Subroutine _consumes: called CC=11 SCAR=25.0
104 31 my ($n) = @_;
105 31 my $k = $n->{kind};
106 31 ▶ return 1 if $k eq 'char' || $k eq 'set' || $k eq 'backref';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "char" or $k eq "set" or $k eq "backref" 15 16 31
Condition100%6/6
$k eq "char" or $k eq "set" or $k eq "backref"
l!l&&r!l&&!r
11416
$k eq "char" or $k eq "set"
l!l&&r!l&&!r
9220
MC/DC100%3/3
$k eq "char" or $k eq "set" or $k eq "backref"
$k eq "char" $k eq "set" $k eq "backref"
Truth table100%4/4
A or B or C
A= $k eq "char"B= $k eq "set"C= $k eq "backref"
ABCresult
1XX1
01X1
0011
0000
107 16 ▶ if ($k eq 'cat' || $k eq 'alt' || $k eq 'group') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "cat" or $k eq "alt" or $k eq "group") 12 4 16
Condition83%5/6
$k eq "cat" or $k eq "alt" or $k eq "group"
l!l&&r!l&&!r
484
$k eq "cat" or $k eq "alt"
l!l&&r!l&&!r
4012
MC/DC66%2/3
$k eq "cat" or $k eq "alt" or $k eq "group"
$k eq "cat" $k eq "alt" $k eq "group"
Truth table75%3/4
A or B or C
A= $k eq "cat"B= $k eq "alt"C= $k eq "group"
ABCresult
1XX1
01X1
0011
0000
108 12 ▶ for (@{ $n->{subs} }) { return 1 if _consumes($_) }
Branch: 1 branch
BranchTrueFalseTotal
if _consumes($_) 12 0 12
109 0 return 0;
110 }
111 4 ▶ return $n->{max} != 0 && _consumes($n->{subs}[0]) if $k eq 'repeat';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "repeat" 4 0 4
Condition33%1/3
$n->{'max'} != 0 && _consumes($n->{'subs'}[0])
!ll&&!rl&&r
004
MC/DC0%0/2
$n->{'max'} != 0 && _consumes($n->{'subs'}[0])
$n->{'max'} != 0 _consumes($n->{'subs'}[0])
Truth table33%1/3
A && B
A= $n->{'max'} != 0B= _consumes($n->{'subs'}[0])
ABresult
0X0
100
111
112 0 return 0;
113 }
114  
115 22 ▶sub _collect_backrefs {
Subroutine _collect_backrefs: called CC=5 SCAR=16.1
116 22 my ($n, $out) = @_;
117 22 ▶ $out->{$_} = 1 for $n->{kind} eq 'backref' ? @{ $n->{groups} } : ();
Branch: 1 branch
BranchTrueFalseTotal
$n->{'kind'} eq 'backref' ? : 2 20 22
118 22 ▶ _collect_backrefs($_, $out) for @{ $n->{subs} // [] };
Condition100%2/2
$n->{"subs"} // []
l!l
148
MC/DC100%1/1
$n->{"subs"} // []
$n->{"subs"}
Truth table100%2/2
A
A= $n->{"subs"}
Aresult
11
00
119 }
120  
121 26 ▶sub _add { my ($c, $i) = @_; push @{ $c->{insts} }, $i; return $#{ $c->{insts} } }
Subroutine _add: called CC=1 SCAR=0.0
122 6 ▶sub _pc { scalar @{ $_[0]{insts} } }
Subroutine _pc: called CC=1 SCAR=0.0
123  
124 # The number of a new memo point for an instruction written here, or 0 when a choice here cannot be remembered: the
125 # pattern has a backreference, or the place is inside a loop with an upper bound, a least count over one, or more
126 # loops than a point can tell apart.
127 6 ▶sub _point {
Subroutine _point: called CC=5 SCAR=28.8
128 6 my ($c) = @_;
129 0 ▶ return 0 if !$c->{memo} || @{ $c->{open} } > MAX_MEMO_LOOPS;
Branch: 1 branch
BranchTrueFalseTotal
if not $c->{"memo"} or @{$c->{"open"};} > 2 6 0 6
Condition33%1/3
not $c->{"memo"} or @{$c->{"open"};} > 2
l!l&&r!l&&!r
600
MC/DC0%0/2
not $c->{"memo"} or @{$c->{"open"};} > 2
not $c->{"memo"} @{$c->{"open"};} > 2
Truth table33%1/3
not(A) or B
A= not $c->{"memo"}B= @{$c->{"open"};} > 2
ABresult
1X1
011
000
130 0 my (@loops, @mins);
131 0 for my $l (@{ $c->{open} }) {
132 0 ▶ return 0 unless $l->[2];
Branch: 1 branch
BranchTrueFalseTotal
unless $l->[2] 0 0 0
133 0 push @loops, $l->[0];
134 0 push @mins, $l->[1];
135 }
136 0 push @{ $c->{points} }, [ \@loops, \@mins ];
137 0 return scalar @{ $c->{points} };
138 }
139  
140 # The first and last slot of the tracked groups inside n, or () when it has none.
141 4 ▶sub _group_range {
Subroutine _group_range: called CC=2 SCAR=7.0
142 4 my ($c, $n) = @_;
143 4 my ($lo, $hi) = (-1, -1);
144 4 my $walk;
145 16 ▶ $walk = sub {
Subroutine __ANON__: called CC=9 SCAR=22.8
146 16 my ($n) = @_;
147 16 ▶ if ($n->{kind} eq 'group' && $n->{group} && exists $c->{tracked}{ $n->{group} }) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n->{"kind"} eq "group" and $n->{"group"} and exists $c->{"tracked"}{$n->{"group"}}) 2 14 16
Condition83%5/6
$n->{"kind"} eq "group" and $n->{"group"} and exists $c->{"tracked"}{$n->{"group"}}
!ll&&!rl&&r
1402
$n->{"kind"} eq "group" and $n->{"group"}
!ll&&!rl&&r
1222
MC/DC66%2/3
$n->{"kind"} eq "group" and $n->{"group"} and exists $c->{"tracked"}{$n->{"group"}}
$n->{"kind"} eq "group" $n->{"group"} exists $c->{"tracked"}{$n->{"group"}}
Truth table75%3/4
A and B and C
A= $n->{"kind"} eq "group"B= $n->{"group"}C= exists $c->{"tracked"}{$n->{"group"}}
ABCresult
0XX0
10X0
1100
1111
148 2 my $t = $c->{tracked}{ $n->{group} };
149 2 ▶ $lo = $t if $lo < 0 || $t < $lo;
Branch: 1 branch
BranchTrueFalseTotal
if $lo < 0 or $t < $lo 2 0 2
Condition33%1/3
$lo < 0 or $t < $lo
l!l&&r!l&&!r
200
MC/DC0%0/2
$lo < 0 or $t < $lo
$lo < 0 $t < $lo
Truth table33%1/3
A or B
A= $lo < 0B= $t < $lo
ABresult
1X1
011
000
150 2 ▶ $hi = $t if $t > $hi;
Branch: 1 branch
BranchTrueFalseTotal
if $t > $hi 2 0 2
151 }
152 16 ▶ $walk->($_) for @{ $n->{subs} // [] };
Condition100%2/2
$n->{"subs"} // []
l!l
106
MC/DC100%1/1
$n->{"subs"} // []
$n->{"subs"}
Truth table100%2/2
A
A= $n->{"subs"}
Aresult
11
00
153 4 };
154 4 $walk->($n);
155 4 undef $walk;
156 4 ▶ return $lo >= 0 ? ($lo, $hi) : ();
Branch: 1 branch
BranchTrueFalseTotal
$lo >= 0 ? : 2 2 4
157 }
158  
159 # Writes the instructions for n; with $back they match right to left, as the body of a lookbehind must.
160 20 ▶sub _emit {
Subroutine _emit: called CC=35 SCAR=52.5
161 20 my ($c, $n, $back) = @_;
162 20 my $k = $n->{kind};
163 0 ▶ if ($k eq 'empty') { return }
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "empty") 0 20 20
164 0 ▶ if ($k eq 'char') { _add($c, [ $back ? OP_CHAR_BACK : OP_CHAR, 0, 0, 0, 0, $n->{r} ]); return }
Branch: 2 branches
BranchTrueFalseTotal
if ($k eq "char") 0 20 20
$back ? : 0 0 0
165 20 ▶ if ($k eq 'set') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "set") 0 20 20
166 0 ▶ if ($n->{set}->is_empty) { _add($c, [OP_FAIL]) }
Branch: 1 branch
BranchTrueFalseTotal
if ($n->{'set'}->is_empty) { } 0 0 0
167 0 ▶ else { _add($c, [ $back ? OP_SET_BACK : OP_SET, 0, 0, 0, 0, 0, $n->{set} ]) }
Branch: 1 branch
BranchTrueFalseTotal
$back ? : 0 0 0
168 0 return;
169 }
170 20 ▶ if ($k eq 'cat') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "cat") 4 16 20
171 4 my @subs = @{ $n->{subs} };
172 4 ▶ @subs = reverse @subs if $back;
Branch: 1 branch
BranchTrueFalseTotal
if $back 0 4 4
173 4 _emit($c, $_, $back) for @subs;
174 4 return;
175 }
176 16 ▶ if ($k eq 'alt') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "alt") 0 16 16
177 0 my @jumps;
178 0 my $subs = $n->{subs};
179 0 for my $i (0 .. $#$subs) {
180 0 ▶ if ($i == $#$subs) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i == $subs->$#*) 0 0 0
181 0 _emit($c, $subs->[$i], $back);
182 0 last;
183 }
184 0 my $split = _add($c, [ OP_SPLIT, 0, 0, 0, 0, 0, undef, 0, 0, 0, _point($c) ]);
185 0 $c->{insts}[$split][I_X] = _pc($c);
186 0 _emit($c, $subs->[$i], $back);
187 0 push @jumps, _add($c, [OP_JMP]);
188 0 $c->{insts}[$split][I_Y] = _pc($c);
189 }
190 0 $c->{insts}[$_][I_X] = _pc($c) for @jumps;
191 0 return;
192 }
193 16 ▶ if ($k eq 'group') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "group") 4 12 16
194 4 ▶ if (!$n->{group} || !exists $c->{tracked}{ $n->{group} }) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($n->{"group"} and exists $c->{"tracked"}{$n->{"group"}}) 2 2 4
Condition66%2/3
$n->{"group"} and exists $c->{"tracked"}{$n->{"group"}}
!ll&&!rl&&r
202
MC/DC50%1/2
$n->{"group"} and exists $c->{"tracked"}{$n->{"group"}}
$n->{"group"} exists $c->{"tracked"}{$n->{"group"}}
Truth table66%2/3
A and B
A= $n->{"group"}B= exists $c->{"tracked"}{$n->{"group"}}
ABresult
0X0
100
111
195 2 _emit($c, $n->{subs}[0], $back);
196 2 return;
197 }
198 2 my $t = $c->{tracked}{ $n->{group} };
199 2 _add($c, [ OP_SAVE_TMP, 0, 0, $t ]);
200 2 _emit($c, $n->{subs}[0], $back);
201 2 ▶ _add($c, [ OP_CAPTURE, 0, 0, $t, 0, 0, undef, 0, 0, $back ? 1 : 0 ]);
Branch: 1 branch
BranchTrueFalseTotal
$back ? : 0 2 2
202 2 return;
203 }
204 12 ▶ if ($k eq 'bol') { _add($c, [OP_BOL]); return }
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "bol") 2 10 12
205 10 ▶ if ($k eq 'eol') { _add($c, [OP_EOL]); return }
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "eol") 2 8 10
206 0 ▶ if ($k eq 'line_start') { _add($c, [OP_LINE_START]); return }
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "line_start") 0 8 8
207 0 ▶ if ($k eq 'line_end') { _add($c, [OP_LINE_END]); return }
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "line_end") 0 8 8
208 0 ▶ if ($k eq 'wb') { _add($c, [ $n->{fold} ? OP_WB_FOLD : OP_WB ]); return }
Branch: 2 branches
BranchTrueFalseTotal
if ($k eq "wb") 0 8 8
$n->{'fold'} ? : 0 0 0
209 0 ▶ if ($k eq 'nwb') { _add($c, [ $n->{fold} ? OP_NWB_FOLD : OP_NWB ]); return }
Branch: 2 branches
BranchTrueFalseTotal
if ($k eq "nwb") 0 8 8
$n->{'fold'} ? : 0 0 0
210 8 ▶ if ($k eq 'backref') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "backref") 2 6 8
211 2 ▶ my $op = $n->{fold} ? ($back ? OP_BACKREF_FOLD_BACK : OP_BACKREF_FOLD) : ($back ? OP_BACKREF_BACK : OP_BACKREF);
Branch: 3 branches
BranchTrueFalseTotal
$n->{'fold'} ? : 0 2 2
$back ? : 0 0 0
$back ? : 0 2 2
212 # When several groups share the name, at most one has taken part and the others match the empty string, so
213 # matching each in turn matches the one that took part.
214 2 for my $g (@{ $n->{groups} }) {
215 2 _add($c, [ $op, 0, 0, $c->{tracked}{$g}, 0, 0, undef, 0, 0, $c->{unicode} ]);
216 }
217 2 return;
218 }
219 6 ▶ if ($k eq 'look') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "look") 0 6 6
220 0 ▶ my $look = _add($c, [ OP_LOOK, 0, 0, 0, 0, 0, undef, 0, 0, $n->{negative} ? 1 : 0 ]);
Branch: 1 branch
BranchTrueFalseTotal
$n->{'negative'} ? : 0 0 0
221 # Whether the body matches depends on nothing outside it.
222 0 my $outer = $c->{open};
223 0 $c->{open} = [];
224 0 _emit($c, $n->{subs}[0], $n->{behind});
225 0 $c->{open} = $outer;
226 0 ▶ _add($c, [ $n->{negative} ? OP_LOOK_FAIL : OP_LOOK_OK ]);
Branch: 1 branch
BranchTrueFalseTotal
$n->{'negative'} ? : 0 0 0
227 0 $c->{insts}[$look][I_X] = _pc($c);
228 0 return;
229 }
230 6 ▶ if ($k eq 'repeat') { _emit_repeat($c, $n, $back); return }
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "repeat") 6 0 6
231 0 die "unknown node $k";
232 }
233  
234 6 ▶sub _emit_repeat {
Subroutine _emit_repeat: called CC=20 SCAR=37.0
235 6 my ($c, $n, $back) = @_;
236 6 my $body = $n->{subs}[0];
237 6 ▶ return if $n->{max} == 0;
Branch: 1 branch
BranchTrueFalseTotal
if $n->{"max"} == 0 0 6 6
238 6 my ($min, $max) = ($n->{min}, $n->{max});
239 6 ▶ if (!$back && ($body->{kind} eq 'char' || ($body->{kind} eq 'set' && !$body->{set}->is_empty))) {
Branch: 1 branch
BranchTrueFalseTotal
if (not $back and $body->{"kind"} eq "char" || $body->{"kind"} eq "set" && !$body->{"set"}->is_empty) 2 4 6
Condition55%5/9
not $back and $body->{"kind"} eq "char" || $body->{"kind"} eq "set" && !$body->{"set"}->is_empty
!ll&&!rl&&r
042
$body->{"kind"} eq "char" or $body->{"kind"} eq "set" and not $body->{"set"}->is_empty
l!l&&r!l&&!r
204
$body->{"kind"} eq "set" and not $body->{"set"}->is_empty
!ll&&!rl&&r
400
MC/DC25%1/4
not $back and $body->{"kind"} eq "char" || $body->{"kind"} eq "set" && !$body->{"set"}->is_empty
not $back $body->{"kind"} eq "char" $body->{"kind"} eq "set" not $body->{"set"}->is_empty
Truth table40%2/5
not(A) and B or C and not(D)
A= not $backB= $body->{"kind"} eq "char"C= $body->{"kind"} eq "set"D= not $body->{"set"}->is_empty
ABCDresult
0XXX0
100X0
10100
11XX1
10111
240 2 ▶ _add($c, [ $n->{lazy} ? OP_REP_LAZY : OP_REP, 0, 0, 0, 0, $body->{r} // 0, $body->{set}, $min, $max, 0,
Branch: 1 branch
BranchTrueFalseTotal
$n->{'lazy'} ? : 0 2 2
Condition50%1/2
$body->{"r"} // 0
l!l
20
MC/DC0%0/1
$body->{"r"} // 0
$body->{"r"}
Truth table50%1/2
A
A= $body->{"r"}
Aresult
11
00
241 _point($c) ]);
242 2 return;
243 }
244 4 my @clear = _group_range($c, $body);
245 4 ▶ my $emit_body = sub {
Subroutine __ANON__: called CC=2 SCAR=6.9
246 4 ▶ _add($c, [ OP_CLEAR, 0, 0, $clear[0], $clear[1] ]) if @clear;
Branch: 1 branch
BranchTrueFalseTotal
if @clear 2 2 4
247 4 _emit($c, $body, $back);
248 4 };
249 4 ▶ my $split = sub { _add($c, [ OP_SPLIT, 0, 0, 0, 0, 0, undef, 0, 0, 0, _point($c) ]) };
Subroutine __ANON__: called CC=1 SCAR=0.0
250 2 ▶ my $set_split = sub {
Subroutine __ANON__: called CC=2 SCAR=7.1
251 2 my ($at, $enter, $exit) = @_;
252 2 ▶ @{ $c->{insts}[$at] }[ I_X, I_Y ] = $n->{lazy} ? ($exit, $enter) : ($enter, $exit);
Branch: 1 branch
BranchTrueFalseTotal
$n->{'lazy'} ? : 0 2 2
253 4 };
254 # A body that always consumes something needs no check for empty iterations.
255 4 ▶ if (!_nullable($body)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (_nullable($body)) 2 2 4
256 2 ▶ if ($min == 0 && $max == UNBOUNDED) {
Branch: 1 branch
BranchTrueFalseTotal
if ($min == 0 and $max == -1) 0 2 2
Condition33%1/3
$min == 0 and $max == -1
!ll&&!rl&&r
200
MC/DC0%0/2
$min == 0 and $max == -1
$min == 0 $max == -1
Truth table33%1/3
A and B
A= $min == 0B= $max == -1
ABresult
0X0
100
111
257 0 my $at = $split->();
258 0 my $enter = _pc($c);
259 0 $emit_body->();
260 0 _add($c, [ OP_JMP, $at ]);
261 0 $set_split->($at, $enter, _pc($c));
262 0 return;
263 }
264 2 ▶ if ($min == 1 && $max == UNBOUNDED) {
Branch: 1 branch
BranchTrueFalseTotal
if ($min == 1 and $max == -1) 2 0 2
Condition33%1/3
$min == 1 and $max == -1
!ll&&!rl&&r
002
MC/DC0%0/2
$min == 1 and $max == -1
$min == 1 $max == -1
Truth table33%1/3
A and B
A= $min == 1B= $max == -1
ABresult
0X0
100
111
265 2 my $enter = _pc($c);
266 2 $emit_body->();
267 2 my $at = $split->();
268 2 $set_split->($at, $enter, _pc($c));
269 2 return;
270 }
271 0 ▶ if ($min == 0 && $max == 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($min == 0 and $max == 1) 0 0 0
Condition0%0/3
$min == 0 and $max == 1
!ll&&!rl&&r
000
MC/DC0%0/2
$min == 0 and $max == 1
$min == 0 $max == 1
Truth table0%0/3
A and B
A= $min == 0B= $max == 1
ABresult
0X0
100
111
272 0 my $at = $split->();
273 0 my $enter = _pc($c);
274 0 $emit_body->();
275 0 $set_split->($at, $enter, _pc($c));
276 0 return;
277 }
278 }
279 2 my $k = $c->{loops}++;
280 2 _add($c, [ OP_LOOP_INIT, 0, 0, $k ]);
281 2 ▶ my $iter = $back ? 0 : _min_length($body);
Branch: 1 branch
BranchTrueFalseTotal
$back ? : 0 2 2
282 2 ▶ my $simple = $max == UNBOUNDED && $min <= 1;
Condition33%1/3
$max == -1 && $min <= 1
!ll&&!rl&&r
002
MC/DC0%0/2
$max == -1 && $min <= 1
$max == -1 $min <= 1
Truth table33%1/3
A && B
A= $max == -1B= $min <= 1
ABresult
0X0
100
111
283 # The loop is left or entered from here, and what follows either depends on the loops around this one.
284 2 ▶ my $point = $simple ? _point($c) : 0;
Branch: 1 branch
BranchTrueFalseTotal
$simple ? : 2 0 2
285 2 ▶ my $loop = _add($c, [ OP_LOOP, 0, 0, $k, 0, 0, undef, $min, $max, $n->{lazy} ? 1 : 0, $point, 0, $iter ]);
Branch: 1 branch
BranchTrueFalseTotal
$n->{'lazy'} ? : 0 2 2
286 2 _add($c, [ OP_LOOP_ITER, 0, 0, $k ]);
287 2 ▶ push @{ $c->{open} }, [ $k, $min, $simple ? 1 : 0 ];
Branch: 1 branch
BranchTrueFalseTotal
$simple ? : 2 0 2
288 2 $emit_body->();
289 2 pop @{ $c->{open} };
290 2 _add($c, [ OP_JMP, $loop ]);
291 2 $c->{insts}[$loop][I_X] = _pc($c);
292 }
293  
294 # The least number of characters a match of n consumes, capped at NO_MATCH.
295 2 ▶sub _min_length {
Subroutine _min_length: called CC=12 SCAR=38.2
296 2 my ($n) = @_;
297 2 my $k = $n->{kind};
298 2 ▶ return 1 if $k eq 'char';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "char" 0 2 2
299 2 ▶ return $n->{set}->is_empty ? NO_MATCH : 1 if $k eq 'set';
Branch: 2 branches
BranchTrueFalseTotal
if $k eq "set" 0 2 2
$n->{'set'}->is_empty ? : 0 0 0
300 2 ▶ if ($k eq 'cat') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "cat") 0 2 2
301 0 my $total = 0;
302 0 for (@{ $n->{subs} }) {
303 0 $total += _min_length($_);
304 0 ▶ return NO_MATCH if $total >= NO_MATCH;
Branch: 1 branch
BranchTrueFalseTotal
if $total >= 1073741824 0 0 0
305 }
306 0 return $total;
307 }
308 2 ▶ if ($k eq 'alt') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "alt") 0 2 2
309 0 my $least = NO_MATCH;
310 0 ▶ for (@{ $n->{subs} }) { my $l = _min_length($_); $least = $l if $l < $least }
Branch: 1 branch
BranchTrueFalseTotal
if $l < $least 0 0 0
311 0 return $least;
312 }
313 2 ▶ return _min_length($n->{subs}[0]) if $k eq 'group';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "group" 0 2 2
314 2 ▶ return _times_need($n->{min}, _min_length($n->{subs}[0])) if $k eq 'repeat';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "repeat" 0 2 2
315 2 return 0;
316 }
317  
318 4 ▶sub _times_need {
Subroutine _times_need: called CC=5 SCAR=26.5
319 4 my ($count, $need) = @_;
320 4 ▶ return 0 if $count == 0 || $need == 0;
Branch: 1 branch
BranchTrueFalseTotal
if $count == 0 or $need == 0 4 0 4
Condition33%1/3
$count == 0 or $need == 0
l!l&&r!l&&!r
400
MC/DC0%0/2
$count == 0 or $need == 0
$count == 0 $need == 0
Truth table33%1/3
A or B
A= $count == 0B= $need == 0
ABresult
1X1
011
000
321 0 ▶ return NO_MATCH if $need >= NO_MATCH || $count >= NO_MATCH / $need;
Branch: 1 branch
BranchTrueFalseTotal
if $need >= 1073741824 or $count >= 1073741824 / $need 0 0 0
Condition0%0/3
$need >= 1073741824 or $count >= 1073741824 / $need
l!l&&r!l&&!r
000
MC/DC0%0/2
$need >= 1073741824 or $count >= 1073741824 / $need
$need >= 1073741824 $count >= 1073741824 / $need
Truth table0%0/3
A or B
A= $need >= 1073741824B= $count >= 1073741824 / $need
ABresult
1X1
011
000
322 0 return $count * $need;
323 }
324  
325 # Whether n can match without consuming anything (erring towards true).
326 12 ▶sub _nullable {
Subroutine _nullable: called CC=12 SCAR=28.5
327 12 my ($n) = @_;
328 12 my $k = $n->{kind};
329 12 ▶ return 0 if $k eq 'char' || $k eq 'set';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "char" or $k eq "set" 2 10 12
Condition66%2/3
$k eq "char" or $k eq "set"
l!l&&r!l&&!r
2010
MC/DC50%1/2
$k eq "char" or $k eq "set"
$k eq "char" $k eq "set"
Truth table66%2/3
A or B
A= $k eq "char"B= $k eq "set"
ABresult
1X1
011
000
330 10 ▶ if ($k eq 'cat') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "cat") 2 8 10
331 2 ▶ for (@{ $n->{subs} }) { return 0 unless _nullable($_) }
Branch: 1 branch
BranchTrueFalseTotal
unless _nullable($_) 2 0 2
332 0 return 1;
333 }
334 8 ▶ if ($k eq 'alt') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "alt") 0 8 8
335 0 ▶ for (@{ $n->{subs} }) { return 1 if _nullable($_) }
Branch: 1 branch
BranchTrueFalseTotal
if _nullable($_) 0 0 0
336 0 return 0;
337 }
338 8 ▶ return _nullable($n->{subs}[0]) if $k eq 'group';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "group" 4 4 8
339 4 ▶ return $n->{min} == 0 || _nullable($n->{subs}[0]) if $k eq 'repeat';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "repeat" 2 2 4
Condition33%1/3
$n->{'min'} == 0 || _nullable($n->{'subs'}[0])
l!l&&r!l&&!r
002
MC/DC0%0/2
$n->{'min'} == 0 || _nullable($n->{'subs'}[0])
$n->{'min'} == 0 _nullable($n->{'subs'}[0])
Truth table33%1/3
A || B
A= $n->{'min'} == 0B= _nullable($n->{'subs'}[0])
ABresult
1X1
011
000
340 2 return 1;
341 }
342  
343 # For every instruction, the least number of characters any way from it to a match consumes going forward, written
344 # into the counted loops; returns the need of the whole program (setNeeds).
345 2 ▶sub _set_needs {
Subroutine _set_needs: called CC=24 SCAR=34.8
346 2 my ($insts) = @_;
347 2 my @need = (NO_MATCH) x @$insts;
348 2 my $changed = 1;
349 2 ▶ while ($changed) {
Branch: 1 branch
BranchTrueFalseTotal
if ($changed) 4 2 6
350 4 $changed = 0;
351 4 ▶ for (my $pc = $#$insts; $pc >= 0; $pc--) {
Branch: 1 branch
BranchTrueFalseTotal
if ($pc >= 0) 52 4 56
352 52 my $i = $insts->[$pc];
353 52 my $op = $i->[I_OP];
354 52 my $n = NO_MATCH;
355 56 ▶ my $next = sub {
Subroutine __ANON__: called CC=2 SCAR=6.9
356 56 my ($to, $weight) = @_;
357 56 my $v = $need[$to] + $weight;
358 56 ▶ $n = $v if $v < $n;
Branch: 1 branch
BranchTrueFalseTotal
if $v < $n 50 6 56
359 52 };
360 52 ▶ if ($op == OP_MATCH || $op == OP_LOOK_OK || $op == OP_LOOK_FAIL) { $n = 0 }
Branch: 9 branches
BranchTrueFalseTotal
if ($op == 30 or $op == 23 or $op == 24) { } 4 48 52
elsif ($op == 4) { } 0 48 48
elsif ($op == 0 or $op == 2) { } 0 48 48
elsif ($op == 25 or $op == 26) { } 4 44 48
elsif ($op == 13) { } 4 40 44
elsif ($op == 22) { } 0 40 40
elsif ($op == 14) { } 4 36 40
elsif ($op == 28) { } 4 32 36
elsif ($op == 27) { } 4 28 32
Condition66%4/6
$op == 30 or $op == 23 or $op == 24
l!l&&r!l&&!r
4048
$op == 30 or $op == 23
l!l&&r!l&&!r
4048
MC/DC33%1/3
$op == 30 or $op == 23 or $op == 24
$op == 30 $op == 23 $op == 24
Truth table50%2/4
A or B or C
A= $op == 30B= $op == 23C= $op == 24
ABCresult
1XX1
01X1
0011
0000
361 elsif ($op == OP_FAIL) { }
362 0 ▶ elsif ($op == OP_CHAR || $op == OP_SET) { $next->($pc + 1, 1) }
Condition33%1/3
$op == 0 or $op == 2
l!l&&r!l&&!r
0048
MC/DC0%0/2
$op == 0 or $op == 2
$op == 0 $op == 2
Truth table33%1/3
A or B
A= $op == 0B= $op == 2
ABresult
1X1
011
000
363 4 ▶ elsif ($op == OP_REP || $op == OP_REP_LAZY) { $next->($pc + 1, $i->[I_MIN]) }
Condition66%2/3
$op == 25 or $op == 26
l!l&&r!l&&!r
4044
MC/DC50%1/2
$op == 25 or $op == 26
$op == 25 $op == 26
Truth table66%2/3
A or B
A= $op == 25B= $op == 26
ABresult
1X1
011
000
364 elsif ($op == OP_JMP) {
365 4 my $head = $insts->[ $i->[I_X] ];
366 4 ▶ if ($i->[I_X] < $pc && $head->[I_OP] == OP_LOOP) { $next->($head->[I_X], 0) }
Branch: 2 branches
BranchTrueFalseTotal
if ($i->[1] < $pc and $head->[0] == 28) { } 4 0 4
elsif ($i->[1] < $pc and $head->[0] == 14) { } 0 0 0
Condition33%1/3
$i->[1] < $pc and $head->[0] == 28
!ll&&!rl&&r
004
MC/DC0%0/2
$i->[1] < $pc and $head->[0] == 28
$i->[1] < $pc $head->[0] == 28
Truth table33%1/3
A and B
A= $i->[1] < $pcB= $head->[0] == 28
ABresult
0X0
100
111
367 0 ▶ elsif ($i->[I_X] < $pc && $head->[I_OP] == OP_SPLIT) { $next->($head->[I_X], 0); $next->($head->[I_Y], 0) }
Condition0%0/3
$i->[1] < $pc and $head->[0] == 14
!ll&&!rl&&r
000
MC/DC0%0/2
$i->[1] < $pc and $head->[0] == 14
$i->[1] < $pc $head->[0] == 14
Truth table0%0/3
A and B
A= $i->[1] < $pcB= $head->[0] == 14
ABresult
0X0
100
111
368 0 else { $next->($i->[I_X], 0) }
369 }
370 0 elsif ($op == OP_LOOK) { $next->($i->[I_X], 0) }
371 4 elsif ($op == OP_SPLIT) { $next->($i->[I_X], 0); $next->($i->[I_Y], 0) }
372 4 elsif ($op == OP_LOOP) { $next->($pc + 1, 0); $next->($i->[I_X], 0) }
373 elsif ($op == OP_LOOP_INIT) {
374 4 my $loop = $insts->[ $pc + 1 ];
375 4 $next->($pc + 1, _times_need($loop->[I_MIN], $loop->[I_ITER]));
376 }
377 28 else { $next->($pc + 1, 0) }
378 52 ▶ $n = NO_MATCH if $n > NO_MATCH;
Branch: 1 branch
BranchTrueFalseTotal
if $n > 1073741824 0 52 52
379 52 ▶ if ($n < $need[$pc]) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n < $need[$pc]) 26 26 52
380 26 $need[$pc] = $n;
381 26 $changed = 1;
382 }
383 }
384 }
385 2 for my $pc (0 .. $#$insts) {
386 26 ▶ $insts->[$pc][I_NEED] = $need[$pc] if $insts->[$pc][I_OP] == OP_LOOP;
Branch: 1 branch
BranchTrueFalseTotal
if $insts->[$pc][0] == 28 2 24 26
387 }
388 2 return $need[0];
389 }
390  
391 # A quick says what can come next on a way from an instruction to the end of its match: [ascii (128 flags as a string
392 # of bits), other, mid, end]. The matcher looks at it before it takes a way, and a way the next character rules out is
393 # not taken (setQuick).
394 2 ▶sub _set_quick {
Subroutine _set_quick: called CC=46 SCAR=50.4
395 2 my ($insts) = @_;
396 2 my $all_bits = '';
397 2 vec($all_bits, $_, 1) = 1 for 0 .. 127;
398 2 my $none_bits = '';
399 2 vec($none_bits, 127, 1) = 0;
400 2 my $all = [ $all_bits, 1, 1, 1 ];
401 2 my @q = map { [ $none_bits, 0, 0, 0 ] } @$insts;
402 18 ▶ my $union = sub {
Subroutine __ANON__: called CC=4 SCAR=14.6
403 18 my ($a, $b) = @_;
404 18 ▶ return [ $a->[0] | $b->[0], $a->[1] || $b->[1], $a->[2] || $b->[2], $a->[3] || $b->[3] ];
Condition66%6/9
$a->[1] || $b->[1]
l!l&&r!l&&!r
1008
$a->[2] || $b->[2]
l!l&&r!l&&!r
1008
$a->[3] || $b->[3]
l!l&&r!l&&!r
1080
MC/DC50%1/2
$a->[1] || $b->[1]
$a->[1] $b->[1]
MC/DC50%1/2
$a->[2] || $b->[2]
$a->[2] $b->[2]
MC/DC0%0/2
$a->[3] || $b->[3]
$a->[3] $b->[3]
Truth table66%2/3
A || B
A= $a->[1]B= $b->[1]
ABresult
1X1
011
000
Truth table66%2/3
A || B
A= $a->[2]B= $b->[2]
ABresult
1X1
011
000
Truth table66%2/3
A || B
A= $a->[3]B= $b->[3]
ABresult
1X1
011
000
405 2 };
406 0 ▶ my $add_set = sub {
Subroutine __ANON__: not called CC=8 SCAR=42.8
407 0 my ($n, $set) = @_;
408 0 my $bits = $n->[0];
409 0 my $r = $set->{ranges};
410 0 ▶ for (my $i = 0; $i < @$r && $r->[$i] < 128; $i += 2) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < @$r and $r->[$i] < 128) 0 0 0
Condition0%0/3
$i < @$r and $r->[$i] < 128
!ll&&!rl&&r
000
MC/DC0%0/2
$i < @$r and $r->[$i] < 128
$i < @$r $r->[$i] < 128
Truth table0%0/3
A and B
A= $i < @$rB= $r->[$i] < 128
ABresult
0X0
100
111
411 0 ▶ my $hi = $r->[$i + 1] < 127 ? $r->[$i + 1] : 127;
Branch: 1 branch
BranchTrueFalseTotal
$$r[$i + 1] < 127 ? : 0 0 0
412 0 vec($bits, $_, 1) = 1 for $r->[$i] .. $hi;
413 }
414 0 ▶ return [ $bits, $n->[1] || (@$r && $r->[-1] >= 128) ? 1 : 0, $n->[2], $n->[3] ];
Branch: 1 branch
BranchTrueFalseTotal
$n->[1] || @$r && $r->[-1] >= 128 ? : 0 0 0
Condition0%0/6
$n->[1] or @$r and $r->[-1] >= 128
l!l&&r!l&&!r
000
@$r and $r->[-1] >= 128
!ll&&!rl&&r
000
MC/DC0%0/3
$n->[1] or @$r and $r->[-1] >= 128
$n->[1] @$r $r->[-1] >= 128
Truth table0%0/4
A or B and C
A= $n->[1]B= @$rC= $r->[-1] >= 128
ABCresult
1XX1
0111
00X0
0100
415 2 };
416 6 ▶ my $add_rune = sub {
Subroutine __ANON__: called CC=2 SCAR=7.2
417 6 my ($n, $c) = @_;
418 6 my $bits = $n->[0];
419 6 ▶ if ($c < 128) {
Branch: 1 branch
BranchTrueFalseTotal
if ($c < 128) 6 0 6
420 6 vec($bits, $c, 1) = 1;
421 6 return [ $bits, $n->[1], $n->[2], $n->[3] ];
422 }
423 0 return [ $bits, 1, $n->[2], $n->[3] ];
424 2 };
425 2 my $changed = 1;
426 2 ▶ while ($changed) {
Branch: 1 branch
BranchTrueFalseTotal
if ($changed) 6 2 8
427 6 $changed = 0;
428 6 ▶ for (my $pc = $#$insts; $pc >= 0; $pc--) {
Branch: 1 branch
BranchTrueFalseTotal
if ($pc >= 0) 78 6 84
429 78 my $i = $insts->[$pc];
430 78 my $op = $i->[I_OP];
431 78 my $n = [ $none_bits, 0, 0, 0 ];
432 78 ▶ if ($op == OP_MATCH || $op == OP_LOOK_OK || $op == OP_LOOK_FAIL) { $n = $all }
Branch: 11 branches
BranchTrueFalseTotal
if ($op == 30 or $op == 23 or $op == 24) { } 6 72 78
elsif ($op == 4) { } 0 72 72
elsif ($op == 0) { } 0 72 72
elsif ($op == 2) { } 0 72 72
elsif ($op == 25 or $op == 26) { } 6 66 72
elsif ($op == 13) { } 6 60 66
elsif ($op == 14) { } 6 54 60
elsif ($op == 28) { } 6 48 54
elsif ($op == 6) { } 6 42 48
elsif ($op == 22) { } 0 42 42
elsif ($op == 1 or $op == 3 or $op == 18 or $op == 19 or $op == 20 or $op == 21) { } 6 36 42
Condition66%4/6
$op == 30 or $op == 23 or $op == 24
l!l&&r!l&&!r
6072
$op == 30 or $op == 23
l!l&&r!l&&!r
6072
MC/DC33%1/3
$op == 30 or $op == 23 or $op == 24
$op == 30 $op == 23 $op == 24
Truth table50%2/4
A or B or C
A= $op == 30B= $op == 23C= $op == 24
ABCresult
1XX1
01X1
0011
0000
433 elsif ($op == OP_FAIL) { }
434 0 elsif ($op == OP_CHAR) { $n = $add_rune->($n, $i->[I_R]) }
435 0 elsif ($op == OP_SET) { $n = $add_set->($n, $i->[I_SET]) }
436 ▶ elsif ($op == OP_REP || $op == OP_REP_LAZY) {
Condition66%2/3
$op == 25 or $op == 26
l!l&&r!l&&!r
6066
MC/DC50%1/2
$op == 25 or $op == 26
$op == 25 $op == 26
Truth table66%2/3
A or B
A= $op == 25B= $op == 26
ABresult
1X1
011
000
437 6 ▶ $n = $i->[I_SET] ? $add_set->($n, $i->[I_SET]) : $add_rune->($n, $i->[I_R]);
Branch: 1 branch
BranchTrueFalseTotal
$i->[6] ? : 0 6 6
438 6 ▶ $n = $union->($n, $q[ $pc + 1 ]) if $i->[I_MIN] == 0;
Branch: 1 branch
BranchTrueFalseTotal
if $i->[7] == 0 0 6 6
439 }
440 elsif ($op == OP_JMP) {
441 6 $n = $q[ $i->[I_X] ];
442 6 my $head = $insts->[ $i->[I_X] ];
443 6 ▶ if ($i->[I_X] < $pc && $head->[I_OP] == OP_LOOP) { $n = $union->($n, $q[ $head->[I_X] ]) }
Branch: 2 branches
BranchTrueFalseTotal
if ($i->[1] < $pc and $head->[0] == 28) { } 6 0 6
elsif ($i->[1] < $pc and $head->[0] == 14) { } 0 0 0
Condition33%1/3
$i->[1] < $pc and $head->[0] == 28
!ll&&!rl&&r
006
MC/DC0%0/2
$i->[1] < $pc and $head->[0] == 28
$i->[1] < $pc $head->[0] == 28
Truth table33%1/3
A and B
A= $i->[1] < $pcB= $head->[0] == 28
ABresult
0X0
100
111
444 ▶ elsif ($i->[I_X] < $pc && $head->[I_OP] == OP_SPLIT) {
Condition0%0/3
$i->[1] < $pc and $head->[0] == 14
!ll&&!rl&&r
000
MC/DC0%0/2
$i->[1] < $pc and $head->[0] == 14
$i->[1] < $pc $head->[0] == 14
Truth table0%0/3
A and B
A= $i->[1] < $pcB= $head->[0] == 14
ABresult
0X0
100
111
445 0 $n = $union->($union->($n, $q[ $head->[I_X] ]), $q[ $head->[I_Y] ]);
446 }
447 }
448 6 elsif ($op == OP_SPLIT) { $n = $union->($q[ $i->[I_X] ], $q[ $i->[I_Y] ]) }
449 6 elsif ($op == OP_LOOP) { $n = $union->($q[ $pc + 1 ], $q[ $i->[I_X] ]) }
450 6 elsif ($op == OP_EOL) { $n = [ $none_bits, 0, 0, $q[ $pc + 1 ][3] ] }
451 elsif ($op == OP_LOOK) {
452 0 $n = $q[ $i->[I_X] ];
453 0 ▶ if (!$i->[I_FLAG]) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($i->[9]) 0 0 0
454 0 my $b = $q[ $pc + 1 ];
455 0 ▶ $n = [ $n->[0] & $b->[0], $n->[1] && $b->[1], $n->[2] && $b->[2], $n->[3] && $b->[3] ];
Condition0%0/9
$n->[1] && $b->[1]
!ll&&!rl&&r
000
$n->[2] && $b->[2]
!ll&&!rl&&r
000
$n->[3] && $b->[3]
!ll&&!rl&&r
000
MC/DC0%0/2
$n->[1] && $b->[1]
$n->[1] $b->[1]
MC/DC0%0/2
$n->[2] && $b->[2]
$n->[2] $b->[2]
MC/DC0%0/2
$n->[3] && $b->[3]
$n->[3] $b->[3]
Truth table0%0/3
A && B
A= $n->[1]B= $b->[1]
ABresult
0X0
100
111
Truth table0%0/3
A && B
A= $n->[2]B= $b->[2]
ABresult
0X0
100
111
Truth table0%0/3
A && B
A= $n->[3]B= $b->[3]
ABresult
0X0
100
111
456 }
457 }
458 ▶ elsif ($op == OP_CHAR_BACK || $op == OP_SET_BACK || $op == OP_BACKREF || $op == OP_BACKREF_BACK
Condition60%9/15
$op == 1 or $op == 3 or $op == 18 or $op == 19 or $op == 20 or $op == 21
l!l&&r!l&&!r
6036
$op == 1 or $op == 3 or $op == 18 or $op == 19 or $op == 20
l!l&&r!l&&!r
6036
$op == 1 or $op == 3 or $op == 18 or $op == 19
l!l&&r!l&&!r
6036
$op == 1 or $op == 3 or $op == 18
l!l&&r!l&&!r
0636
$op == 1 or $op == 3
l!l&&r!l&&!r
0042
MC/DC16%1/6
$op == 1 or $op == 3 or $op == 18 or $op == 19 or $op == 20 or $op == 21
$op == 1 $op == 3 $op == 18 $op == 19 $op == 20 $op == 21
Truth table28%2/7
A or B or C or D or E or F
A= $op == 1B= $op == 3C= $op == 18D= $op == 19E= $op == 20F= $op == 21
ABCDEFresult
1XXXXX1
01XXXX1
001XXX1
0001XX1
00001X1
0000011
0000000
459 || $op == OP_BACKREF_FOLD || $op == OP_BACKREF_FOLD_BACK) {
460 6 $n = $all;
461 }
462 36 else { $n = $q[ $pc + 1 ] }
463 78 my $old = $q[$pc];
464 78 ▶ if ($n->[0] ne $old->[0] || ($n->[1] ? 1 : 0) != ($old->[1] ? 1 : 0) || ($n->[2] ? 1 : 0) != ($old->[2] ? 1 : 0)
Branch: 7 branches
BranchTrueFalseTotal
if ($n->[0] ne $old->[0] or ($n->[1] ? 1 : 0) != ($old->[1] ? 1 : 0) or ($n->[2] ? 1 : 0) != ($old->[2] ? 1 : 0) or ($n->[3] ? 1 : 0) != ($old->[3] ? 1 : 0)) 30 48 78
$n->[1] ? : 26 28 54
$old->[1] ? : 26 28 54
$n->[2] ? : 26 28 54
$old->[2] ? : 26 28 54
$n->[3] ? : 38 16 54
$old->[3] ? : 32 22 54
Condition77%7/9
$n->[0] ne $old->[0] or ($n->[1] ? 1 : 0) != ($old->[1] ? 1 : 0) or ($n->[2] ? 1 : 0) != ($old->[2] ? 1 : 0) or ($n->[3] ? 1 : 0) != ($old->[3] ? 1 : 0)
l!l&&r!l&&!r
24648
$n->[0] ne $old->[0] or ($n->[1] ? 1 : 0) != ($old->[1] ? 1 : 0) or ($n->[2] ? 1 : 0) != ($old->[2] ? 1 : 0)
l!l&&r!l&&!r
24054
$n->[0] ne $old->[0] or ($n->[1] ? 1 : 0) != ($old->[1] ? 1 : 0)
l!l&&r!l&&!r
24054
MC/DC50%2/4
$n->[0] ne $old->[0] or ($n->[1] ? 1 : 0) != ($old->[1] ? 1 : 0) or ($n->[2] ? 1 : 0) != ($old->[2] ? 1 : 0) or ($n->[3] ? 1 : 0) != ($old->[3] ? 1 : 0)
$n->[0] ne $old->[0] ($n->[1] ? 1 : 0) != ($old->[1] ? 1 : 0) ($n->[2] ? 1 : 0) != ($old->[2] ? 1 : 0) ($n->[3] ? 1 : 0) != ($old->[3] ? 1 : 0)
Truth table60%3/5
A or B or C or D
A= $n->[0] ne $old->[0]B= ($n->[1] ? 1 : 0) != ($old->[1] ? 1 : 0)C= ($n->[2] ? 1 : 0) != ($old->[2] ? 1 : 0)D= ($n->[3] ? 1 : 0) != ($old->[3] ? 1 : 0)
ABCDresult
1XXX1
01XX1
001X1
00011
00000
465 || ($n->[3] ? 1 : 0) != ($old->[3] ? 1 : 0)) {
466 30 ▶ $q[$pc] = [ $n->[0], $n->[1] ? 1 : 0, $n->[2] ? 1 : 0, $n->[3] ? 1 : 0 ];
Branch: 3 branches
BranchTrueFalseTotal
$n->[1] ? : 14 16 30
$n->[2] ? : 14 16 30
$n->[3] ? : 22 8 30
467 30 $changed = 1;
468 }
469 }
470 }
471 2 return \@q;
472 }
473  
474 # Whether every way through n begins with ^.
475 4 ▶sub _starts_at_bol {
Subroutine _starts_at_bol: called CC=9 SCAR=36.2
476 4 my ($n) = @_;
477 4 my $k = $n->{kind};
478 4 ▶ return 1 if $k eq 'bol';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "bol" 2 2 4
479 2 ▶ return _starts_at_bol($n->{subs}[0]) if $k eq 'cat' || $k eq 'group';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "cat" or $k eq "group" 2 0 2
Condition33%1/3
$k eq "cat" or $k eq "group"
l!l&&r!l&&!r
200
MC/DC0%0/2
$k eq "cat" or $k eq "group"
$k eq "cat" $k eq "group"
Truth table33%1/3
A or B
A= $k eq "cat"B= $k eq "group"
ABresult
1X1
011
000
480 0 ▶ if ($k eq 'alt') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "alt") 0 0 0
481 0 ▶ for (@{ $n->{subs} }) { return 0 unless _starts_at_bol($_) }
Branch: 1 branch
BranchTrueFalseTotal
unless _starts_at_bol($_) 0 0 0
482 0 return 1;
483 }
484 0 ▶ return $n->{min} >= 1 && _starts_at_bol($n->{subs}[0]) if $k eq 'repeat';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "repeat" 0 0 0
Condition0%0/3
$n->{'min'} >= 1 && _starts_at_bol($n->{'subs'}[0])
!ll&&!rl&&r
000
MC/DC0%0/2
$n->{'min'} >= 1 && _starts_at_bol($n->{'subs'}[0])
$n->{'min'} >= 1 _starts_at_bol($n->{'subs'}[0])
Truth table0%0/3
A && B
A= $n->{'min'} >= 1B= _starts_at_bol($n->{'subs'}[0])
ABresult
0X0
100
111
485 0 return 0;
486 }
487  
488 # The code points a match of n can start with, as inclusive pairs; whether n can match the empty string; and whether
489 # the set is known. Assertions are taken to match the empty string, which can only make the set too large.
490 0 ▶sub _first_chars {
Subroutine _first_chars: not called CC=16 SCAR=56.1
491 0 my ($n, $pairs) = @_;
492 0 my $k = $n->{kind};
493 0 ▶ return ([ @$pairs, $n->{r}, $n->{r} ], 0, 1) if $k eq 'char';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "char" 0 0 0
494 0 ▶ return ([ @$pairs, @{ $n->{set}{ranges} } ], 0, 1) if $k eq 'set';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "set" 0 0 0
495 0 ▶ if ($k eq 'cat') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "cat") 0 0 0
496 0 for my $sub (@{ $n->{subs} }) {
497 0 my ($p, $empty, $ok) = _first_chars($sub, $pairs);
498 0 ▶ return ([], 0, 0) unless $ok;
Branch: 1 branch
BranchTrueFalseTotal
unless $ok 0 0 0
499 0 $pairs = $p;
500 0 ▶ return ($pairs, 0, 1) unless $empty;
Branch: 1 branch
BranchTrueFalseTotal
unless $empty 0 0 0
501 }
502 0 return ($pairs, 1, 1);
503 }
504 0 ▶ if ($k eq 'alt') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "alt") 0 0 0
505 0 my $any_empty = 0;
506 0 for my $sub (@{ $n->{subs} }) {
507 0 my ($p, $empty, $ok) = _first_chars($sub, $pairs);
508 0 ▶ return ([], 0, 0) unless $ok;
Branch: 1 branch
BranchTrueFalseTotal
unless $ok 0 0 0
509 0 $pairs = $p;
510 0 ▶ $any_empty ||= $empty;
Condition0%0/3
$any_empty ||= $empty
l!l&&r!l&&!r
000
MC/DC0%0/2
$any_empty ||= $empty
$any_empty $empty
Truth table0%0/3
A ||= B
A= $any_emptyB= $empty
ABresult
1X1
011
000
511 }
512 0 return ($pairs, $any_empty, 1);
513 }
514 0 ▶ return _first_chars($n->{subs}[0], $pairs) if $k eq 'group';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "group" 0 0 0
515 0 ▶ if ($k eq 'repeat') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "repeat") 0 0 0
516 0 ▶ return ($pairs, 1, 1) if $n->{max} == 0;
Branch: 1 branch
BranchTrueFalseTotal
if $n->{"max"} == 0 0 0 0
517 0 my ($p, $empty, $ok) = _first_chars($n->{subs}[0], $pairs);
518 0 ▶ return ($p, $empty || $n->{min} == 0, $ok);
Condition0%0/3
$empty || $n->{'min'} == 0
l!l&&r!l&&!r
000
MC/DC0%0/2
$empty || $n->{'min'} == 0
$empty $n->{'min'} == 0
Truth table0%0/3
A || B
A= $emptyB= $n->{'min'} == 0
ABresult
1X1
011
000
519 }
520 0 ▶ return ([], 0, 0) if $k eq 'backref';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "backref" 0 0 0
521 0 return ($pairs, 1, 1);
522 }
523  
524 # --- Matching ---
525  
526 # The text as the program reads it: code points, or UTF-16 code units for a pattern read without the u flag.
527 4 ▶sub text_of {
Subroutine text_of: called CC=4 SCAR=19.4
Pod undocumented
528 4 my ($self, $s) = @_;
529 4 my @in = unpack 'W*', $s;
530 0 ▶ if ($self->{units} && grep { $_ > 0xFFFF } @in) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->{"units"} and grep {$_ > 65535;} @in) 0 4 4
Condition33%1/3
$self->{"units"} and grep {$_ > 65535;} @in
!ll&&!rl&&r
400
MC/DC0%0/2
$self->{"units"} and grep {$_ > 65535;} @in
$self->{"units"} grep {$_ > 65535;} @in
Truth table33%1/3
A and B
A= $self->{"units"}B= grep {$_ > 65535;} @in
ABresult
0X0
100
111
531 0 ▶ @in = map { $_ > 0xFFFF ? (0xD800 + (($_ - 0x10000) >> 10), 0xDC00 + (($_ - 0x10000) & 0x3FF)) : $_ } @in;
Branch: 1 branch
BranchTrueFalseTotal
$_ > 65535 ? : 0 0 0
532 }
533 4 return \@in;
534 }
535  
536 # Whether the program matches anywhere in the text (a Perl string). With a limit (seconds) above zero the match is
537 # abandoned when it runs for longer: it then returns (undef, 'time') or (undef, 'memory').
538 4 ▶sub match {
Subroutine match: called CC=4 SCAR=13.9
Pod undocumented
539 4 my ($self, $s, $limit) = @_;
540 4 my $in = $self->text_of($s);
541 my $st = {
542 caps => [ (-1) x (2 * $self->{groups}) ], tmp => [ (-1) x $self->{groups} ], counts => [ (0) x (2 * $self->{loops}) ],
543 limit => $limit // 0, deadline => undef, stop => undef, checks => 0, memo => undef,
544 4 ▶ memo_off => !@{ $self->{points} }, width => @$in + 1,
Condition100%2/2
$limit // 0
l!l
22
MC/DC100%1/1
$limit // 0
$limit
Truth table100%2/2
A
A= $limit
Aresult
11
00
545 };
546 4 my $ok = $self->_search($st, $in);
547 4 ▶ return (undef, $st->{stop}) if $st->{stop};
Branch: 1 branch
BranchTrueFalseTotal
if $st->{"stop"} 1 3 4
548 3 ▶ return ($ok ? 1 : 0);
Branch: 1 branch
BranchTrueFalseTotal
$ok ? : 1 2 3
549 }
550  
551 4 ▶sub _search {
Subroutine _search: called CC=11 SCAR=43.6
552 4 my ($self, $st, $in) = @_;
553 4 my $len = @$in;
554 4 ▶ return 0 if $len < $self->{need};
Branch: 1 branch
BranchTrueFalseTotal
if $len < $self->{"need"} 0 4 4
555 4 ▶ return $self->_run($st, $in, 0) if $self->{anchored};
Branch: 1 branch
BranchTrueFalseTotal
if $self->{"anchored"} 4 0 4
556 0 my $first = $self->{first};
557 0 for (my $at = 0; ; $at++) {
558 0 ▶ return 0 if $len - $at < $self->{need};
Branch: 1 branch
BranchTrueFalseTotal
if $len - $at < $self->{"need"} 0 0 0
559 0 ▶ if ($at == $len) {
Branch: 1 branch
BranchTrueFalseTotal
if ($at == $len) 0 0 0
560 0 ▶ return !$first && $self->_run($st, $in, $at) ? 1 : 0;
Branch: 1 branch
BranchTrueFalseTotal
!$first && $self->_run($st, $in, $at) ? : 0 0 0
Condition0%0/3
not $first and $self->_run($st, $in, $at)
!ll&&!rl&&r
000
MC/DC0%0/2
not $first and $self->_run($st, $in, $at)
not $first $self->_run($st, $in, $at)
Truth table0%0/3
not(A) and B
A= not $firstB= $self->_run($st, $in, $at)
ABresult
0X0
100
111
561 }
562 0 ▶ next if $first && !$first->contains($in->[$at]);
Branch: 1 branch
BranchTrueFalseTotal
if $first and not $first->contains($in->[$at]) 0 0 0
Condition0%0/3
$first and not $first->contains($in->[$at])
!ll&&!rl&&r
000
MC/DC0%0/2
$first and not $first->contains($in->[$at])
$first not $first->contains($in->[$at])
Truth table0%0/3
A and not(B)
A= $firstB= not $first->contains($in->[$at])
ABresult
0X0
100
111
563 0 ▶ return 1 if $self->_run($st, $in, $at);
Branch: 1 branch
BranchTrueFalseTotal
if $self->_run($st, $in, $at) 0 0 0
564 0 ▶ return 0 if $st->{stop};
Branch: 1 branch
BranchTrueFalseTotal
if $st->{"stop"} 0 0 0
565 }
566 }
567  
568 # Takes the memory of failed places into use when the match has made enough steps to pay for it.
569 0 ▶sub _remember {
Subroutine _remember: not called CC=4 SCAR=30.0
570 0 my ($self, $st) = @_;
571 0 my $bits = @{ $self->{points} } * $st->{width} << MAX_MEMO_LOOPS;
572 0 ▶ if ($bits > MAX_MEMO_BITS) {
Branch: 1 branch
BranchTrueFalseTotal
if ($bits > 67108864) 0 0 0
573 0 $st->{memo_off} = 1;
574 0 return;
575 }
576 0 ▶ return if $st->{checks} * CHECK_EVERY < $bits / 64 + MEMO_STEPS_PER_POSITION * $st->{width};
Branch: 1 branch
BranchTrueFalseTotal
if $st->{"checks"} * 4096 < $bits / 64 + 64 * $st->{"width"} 0 0 0
577 0 my $memo = '';
578 0 ▶ vec($memo, $bits - 1, 1) = 0 if $bits;
Branch: 1 branch
BranchTrueFalseTotal
if $bits 0 0 0
579 0 $st->{memo} = \$memo;
580 }
581  
582 # The bit of the memory for memo point m at a position, with the state of the loops around the point: for each,
583 # whether it would refuse an iteration that ended here as empty.
584 0 ▶sub _memo_index {
Subroutine _memo_index: not called CC=4 SCAR=30.0
585 0 my ($self, $st, $m, $pos) = @_;
586 0 my ($loops, $mins) = @{ $self->{points}[ $m - 1 ] };
587 0 my $idx = (($m - 1) * $st->{width} + $pos) << MAX_MEMO_LOOPS;
588 0 my $counts = $st->{counts};
589 0 for my $k (0 .. $#$loops) {
590 0 my $l = $loops->[$k];
591 0 ▶ $idx |= 1 << $k if $counts->[ 2 * $l ] > $mins->[$k] && $counts->[ 2 * $l + 1 ] == $pos;
Branch: 1 branch
BranchTrueFalseTotal
if $$counts[2 * $l] > $mins->[$k] and $$counts[2 * $l + 1] == $pos 0 0 0
Condition0%0/3
$$counts[2 * $l] > $mins->[$k] and $$counts[2 * $l + 1] == $pos
!ll&&!rl&&r
000
MC/DC0%0/2
$$counts[2 * $l] > $mins->[$k] and $$counts[2 * $l + 1] == $pos
$$counts[2 * $l] > $mins->[$k] $$counts[2 * $l + 1] == $pos
Truth table0%0/3
A and B
A= $$counts[2 * $l] > $mins->[$k]B= $$counts[2 * $l + 1] == $pos
ABresult
0X0
100
111
592 }
593 0 return $idx;
594 }
595  
596 # Called every CHECK_EVERY steps: whether the match may go on.
597 128 ▶sub _check {
Subroutine _check: called CC=7 SCAR=20.8
598 128 my ($self, $st, $depth) = @_;
599 128 ▶ if (!$st->{memo} && !$st->{memo_off}) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($st->{"memo"} or $st->{"memo_off"}) 0 128 128
Condition33%1/3
$st->{"memo"} or $st->{"memo_off"}
l!l&&r!l&&!r
01280
MC/DC0%0/2
$st->{"memo"} or $st->{"memo_off"}
$st->{"memo"} $st->{"memo_off"}
Truth table33%1/3
A or B
A= $st->{"memo"}B= $st->{"memo_off"}
ABresult
1X1
011
000
600 0 $st->{checks}++;
601 0 $self->_remember($st);
602 }
603 128 ▶ return 1 if $st->{limit} <= 0;
Branch: 1 branch
BranchTrueFalseTotal
if $st->{"limit"} <= 0 122 6 128
604 6 ▶ if ($depth > MAX_STACK) {
Branch: 1 branch
BranchTrueFalseTotal
if ($depth > 1048576) 0 6 6
605 0 $st->{stop} = 'memory';
606 0 return 0;
607 }
608 6 my $now = Time::HiRes::time();
609 6 ▶ if (!defined $st->{deadline}) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $st->{"deadline"}) 1 5 6
610 1 $st->{deadline} = $now + $st->{limit};
611 1 return 1;
612 }
613 5 ▶ if ($now > $st->{deadline}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($now > $st->{"deadline"}) 1 4 5
614 1 $st->{stop} = 'time';
615 1 return 0;
616 }
617 4 return 1;
618 }
619  
620 210520 ▶sub _allows {
Subroutine _allows: called CC=4 SCAR=13.9
621 210520 my ($q, $in, $pos) = @_;
622 210520 ▶ return $q->[3] if $pos >= @$in;
Branch: 1 branch
BranchTrueFalseTotal
if $pos >= @$in 4 210516 210520
623 210516 ▶ return 1 if $q->[2];
Branch: 1 branch
BranchTrueFalseTotal
if $q->[2] 57683 152833 210516
624 152833 my $c = $in->[$pos];
625 152833 ▶ return $c < 128 ? vec($q->[0], $c, 1) : $q->[1];
Branch: 1 branch
BranchTrueFalseTotal
$c < 128 ? : 152833 0 152833
626 }
627  
628 268176 ▶sub _undo {
Subroutine _undo: called CC=4 SCAR=13.9
629 268176 my ($st, $e) = @_;
630 268176 my $kind = $e->[0];
631 268176 ▶ if ($kind == E_TMP) { $st->{tmp}[ $e->[1] ] = $e->[2] }
Branch: 3 branches
BranchTrueFalseTotal
if ($kind == 6) { } 34243 233933 268176
elsif ($kind == 7) { } 91918 142015 233933
elsif ($kind == 8) { } 142015 0 142015
632 91918 elsif ($kind == E_CAP) { @{ $st->{caps} }[ 2 * $e->[1], 2 * $e->[1] + 1 ] = ($e->[2], $e->[3]) }
633 142015 elsif ($kind == E_COUNTER) { @{ $st->{counts} }[ 2 * $e->[1], 2 * $e->[1] + 1 ] = ($e->[2], $e->[3]) }
634 }
635  
636 # The width (0 or 1) of the character at a position when a single-character loop's character or class matches it.
637 0 ▶sub _one {
Subroutine _one: not called CC=4 SCAR=30.0
638 0 my ($i, $in, $at) = @_;
639 0 ▶ return 0 if $at >= @$in;
Branch: 1 branch
BranchTrueFalseTotal
if $at >= @$in 0 0 0
640 0 my $c = $in->[$at];
641 0 ▶ return ($i->[I_SET] ? $i->[I_SET]->contains($c) : $c == $i->[I_R]) ? 1 : 0;
Branch: 2 branches
BranchTrueFalseTotal
($i->[6] ? $i->[6]->contains($c) : $c == $i->[5]) ? : 0 0 0
$i->[6] ? : 0 0 0
642 }
643  
644 0 ▶sub _is_word { JSON::Schema::Corvus::Regex::Charset::is_word($_[0]) }
Subroutine _is_word: not called CC=1 SCAR=6.9
645  
646 # Whether the program matches at the position start. Choices are kept on an explicit stack; when the match fails,
647 # every group and counter is back to the value it had on entry.
648 4 ▶sub _run {
Subroutine _run: called CC=154 SCAR=85.0
649 4 my ($self, $st, $in, $start) = @_;
650 4 my $insts = $self->{insts};
651 4 my $quick = $self->{quick};
652 4 my $caps = $st->{caps};
653 4 my $counts = $st->{counts};
654 4 my $tmp = $st->{tmp};
655 4 my $len = @$in;
656 4 my @stack;
657 4 my ($pc, $pos) = (0, $start);
658 4 ▶ my $steps = $st->{steps} // CHECK_EVERY;
Condition50%1/2
$st->{"steps"} // 4096
l!l
04
MC/DC0%0/1
$st->{"steps"} // 4096
$st->{"steps"}
Truth table50%1/2
A
A= $st->{"steps"}
Aresult
11
00
659 4 my $memo = $st->{memo};
660 4 my $unicode_fold;
661 4 while (1) {
662 532054 ▶ if (--$steps < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (--$steps < 0) 128 531926 532054
663 128 ▶ if (!$self->_check($st, scalar @stack)) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($self->_check($st, scalar @stack)) 1 127 128
664 1 $st->{steps} = 0;
665 1 return 0;
666 }
667 127 $steps = CHECK_EVERY;
668 127 $memo = $st->{memo};
669 }
670 532053 my $i = $insts->[$pc];
671 532053 my $op = $i->[I_OP];
672 532053 my $failed = 1;
673 532053 ▶ if ($op == OP_CHAR) {
Branch: 27 branches
BranchTrueFalseTotal
if ($op == 0) { } 0 532053 532053
elsif ($op == 2) { } 0 532053 532053
elsif ($op == 25) { } 34251 497802 532053
elsif ($op == 14) { } 34248 463554 497802
elsif ($op == 13) { } 26656 436898 463554
elsif ($op == 5) { } 4 436894 436898
elsif ($op == 6) { } 1 436893 436894
elsif ($op == 4) { } 0 436893 436893
elsif ($op == 1) { } 0 436893 436893
elsif ($op == 3) { } 0 436893 436893
elsif ($op == 7 or $op == 8) { } 0 436893 436893
elsif ($op == 11 or $op == 12) { } 0 436893 436893
elsif ($op == 9) { } 0 436893 436893
elsif ($op == 10) { } 0 436893 436893
elsif ($op == 15) { } 34251 402642 436893
elsif ($op == 16) { } 57685 344957 402642
elsif ($op == 17) { } 34251 310706 344957
elsif ($op == 18 or $op == 20) { } 84340 226366 310706
elsif ($op == 19 or $op == 21) { } 0 226366 226366
elsif ($op == 22) { } 0 226366 226366
elsif ($op == 23) { } 0 226366 226366
elsif ($op == 24) { } 0 226366 226366
elsif ($op == 26) { } 0 226366 226366
elsif ($op == 27) { } 57685 168681 226366
elsif ($op == 28) { } 84340 84341 168681
elsif ($op == 29) { } 84340 1 84341
elsif ($op == 30) { } 1 0 1
674 0 ▶ if ($pos < $len && $in->[$pos] == $i->[I_R]) { $pos++; $pc++; next }
Branch: 1 branch
BranchTrueFalseTotal
if ($pos < $len and $in->[$pos] == $i->[5]) 0 0 0
Condition0%0/3
$pos < $len and $in->[$pos] == $i->[5]
!ll&&!rl&&r
000
MC/DC0%0/2
$pos < $len and $in->[$pos] == $i->[5]
$pos < $len $in->[$pos] == $i->[5]
Truth table0%0/3
A and B
A= $pos < $lenB= $in->[$pos] == $i->[5]
ABresult
0X0
100
111
675 }
676 elsif ($op == OP_SET) {
677 0 ▶ if ($pos < $len && $i->[I_SET]->contains($in->[$pos])) { $pos++; $pc++; next }
Branch: 1 branch
BranchTrueFalseTotal
if ($pos < $len and $i->[6]->contains($in->[$pos])) 0 0 0
Condition0%0/3
$pos < $len and $i->[6]->contains($in->[$pos])
!ll&&!rl&&r
000
MC/DC0%0/2
$pos < $len and $i->[6]->contains($in->[$pos])
$pos < $len $i->[6]->contains($in->[$pos])
Truth table0%0/3
A and B
A= $pos < $lenB= $i->[6]->contains($in->[$pos])
ABresult
0X0
100
111
678 }
679 elsif ($op == OP_REP) {
680 34251 my ($at, $n, $floor) = ($pos, 0, $pos);
681 34251 my ($max, $min) = ($i->[I_MAX], $i->[I_MIN]);
682 34251 ▶ if (my $set = $i->[I_SET]) {
Branch: 1 branch
BranchTrueFalseTotal
if (my $set = $i->[6]) { } 0 34251 34251
683 0 ▶ while ($n != $max && $at < $len && $set->contains($in->[$at])) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n != $max and $at < $len and $set->contains($in->[$at])) 0 0 0
Condition0%0/6
$n != $max and $at < $len and $set->contains($in->[$at])
!ll&&!rl&&r
000
$n != $max and $at < $len
!ll&&!rl&&r
000
MC/DC0%0/3
$n != $max and $at < $len and $set->contains($in->[$at])
$n != $max $at < $len $set->contains($in->[$at])
Truth table0%0/4
A and B and C
A= $n != $maxB= $at < $lenC= $set->contains($in->[$at])
ABCresult
0XX0
10X0
1100
1111
684 0 $at++;
685 0 $n++;
686 0 ▶ $floor = $at if $n == $min;
Branch: 1 branch
BranchTrueFalseTotal
if $n == $min 0 0 0
687 }
688 }
689 else {
690 34251 my $r = $i->[I_R];
691 34251 ▶ while ($n != $max && $at < $len && $in->[$at] == $r) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n != $max and $at < $len and $in->[$at] == $r) 57739 34251 91990
Condition83%5/6
$n != $max and $at < $len and $in->[$at] == $r
!ll&&!rl&&r
13425057739
$n != $max and $at < $len
!ll&&!rl&&r
0191989
MC/DC66%2/3
$n != $max and $at < $len and $in->[$at] == $r
$n != $max $at < $len $in->[$at] == $r
Truth table75%3/4
A and B and C
A= $n != $maxB= $at < $lenC= $in->[$at] == $r
ABCresult
0XX0
10X0
1100
1111
692 57739 $at++;
693 57739 $n++;
694 57739 ▶ $floor = $at if $n == $min;
Branch: 1 branch
BranchTrueFalseTotal
if $n == $min 34251 23488 57739
695 }
696 }
697 34251 $steps -= ($at - $pos) >> 3;
698 34251 ▶ if ($n >= $min) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n >= $min) 34251 0 34251
699 34251 ▶ if ($memo && $i->[I_M]) {
Branch: 1 branch
BranchTrueFalseTotal
if ($memo and $i->[10]) 0 34251 34251
Condition33%1/3
$memo and $i->[10]
!ll&&!rl&&r
3425100
MC/DC0%0/2
$memo and $i->[10]
$memo $i->[10]
Truth table33%1/3
A and B
A= $memoB= $i->[10]
ABresult
0X0
100
111
700 0 my $idx = $self->_memo_index($st, $i->[I_M], $at);
701 0 ▶ if (vec($$memo, $idx, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (vec $$memo, $idx, 1) 0 0 0
702 # What follows the loop has failed from here before. The loop gives a character back.
703 0 ▶ push @stack, [ E_REP, $pc + 1, $at, $floor ] if $at > $floor;
Branch: 1 branch
BranchTrueFalseTotal
if $at > $floor 0 0 0
704 0 goto BACKTRACK;
705 }
706 0 ▶ push @stack, [ E_MARK, 0, $idx ] if $at == $floor && @stack < MAX_MARK_DEPTH;
Branch: 1 branch
BranchTrueFalseTotal
if $at == $floor and @stack < 524288 0 0 0
Condition0%0/3
$at == $floor and @stack < 524288
!ll&&!rl&&r
000
MC/DC0%0/2
$at == $floor and @stack < 524288
$at == $floor @stack < 524288
Truth table0%0/3
A and B
A= $at == $floorB= @stack < 524288
ABresult
0X0
100
111
707 }
708 34251 ▶ push @stack, [ E_REP, $pc + 1, $at, $floor ] if $at > $floor;
Branch: 1 branch
BranchTrueFalseTotal
if $at > $floor 13916 20335 34251
709 34251 $pos = $at;
710 34251 $pc++;
711 34251 next;
712 }
713 }
714 elsif ($op == OP_SPLIT) {
715 # A place from which every way has failed before fails at once. The mark is under whatever comes of this place,
716 # so that the place is remembered when it has all failed.
717 34248 ▶ if ($memo && $i->[I_M]) {
Branch: 1 branch
BranchTrueFalseTotal
if ($memo and $i->[10]) 0 34248 34248
Condition33%1/3
$memo and $i->[10]
!ll&&!rl&&r
3424800
MC/DC0%0/2
$memo and $i->[10]
$memo $i->[10]
Truth table33%1/3
A and B
A= $memoB= $i->[10]
ABresult
0X0
100
111
718 0 my $idx = $self->_memo_index($st, $i->[I_M], $pos);
719 0 ▶ goto BACKTRACK if vec($$memo, $idx, 1);
Branch: 1 branch
BranchTrueFalseTotal
if vec $$memo, $idx, 1 0 0 0
720 0 ▶ push @stack, [ E_MARK, 0, $idx ] if @stack < MAX_MARK_DEPTH;
Branch: 1 branch
BranchTrueFalseTotal
if @stack < 524288 0 0 0
721 }
722 # A way the next character rules out is not taken, and no choice is kept for it.
723 34248 my $x_ok = _allows($quick->[ $i->[I_X] ], $in, $pos);
724 34248 ▶ if (!_allows($quick->[ $i->[I_Y] ], $in, $pos)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (_allows($$quick[$i->[2]], $in, $pos)) 34247 1 34248
725 34247 ▶ goto BACKTRACK unless $x_ok;
Branch: 1 branch
BranchTrueFalseTotal
unless $x_ok 0 34247 34247
726 34247 $pc = $i->[I_X];
727 34247 next;
728 }
729 1 ▶ if (!$x_ok) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($x_ok) 1 0 1
730 1 $pc = $i->[I_Y];
731 1 next;
732 }
733 0 push @stack, [ E_CHOICE, $i->[I_Y], $pos ];
734 0 $pc = $i->[I_X];
735 0 next;
736 }
737 26656 elsif ($op == OP_JMP) { $pc = $i->[I_X]; next }
738 4 ▶ elsif ($op == OP_BOL) { if ($pos == 0) { $pc++; next } }
Branch: 1 branch
BranchTrueFalseTotal
if ($pos == 0) 4 0 4
739 1 ▶ elsif ($op == OP_EOL) { if ($pos == $len) { $pc++; next } }
Branch: 1 branch
BranchTrueFalseTotal
if ($pos == $len) 1 0 1
740 elsif ($op == OP_FAIL) { }
741 elsif ($op == OP_CHAR_BACK) {
742 0 ▶ if ($pos > 0 && $in->[ $pos - 1 ] == $i->[I_R]) { $pos--; $pc++; next }
Branch: 1 branch
BranchTrueFalseTotal
if ($pos > 0 and $$in[$pos - 1] == $i->[5]) 0 0 0
Condition0%0/3
$pos > 0 and $$in[$pos - 1] == $i->[5]
!ll&&!rl&&r
000
MC/DC0%0/2
$pos > 0 and $$in[$pos - 1] == $i->[5]
$pos > 0 $$in[$pos - 1] == $i->[5]
Truth table0%0/3
A and B
A= $pos > 0B= $$in[$pos - 1] == $i->[5]
ABresult
0X0
100
111
743 }
744 elsif ($op == OP_SET_BACK) {
745 0 ▶ if ($pos > 0 && $i->[I_SET]->contains($in->[ $pos - 1 ])) { $pos--; $pc++; next }
Branch: 1 branch
BranchTrueFalseTotal
if ($pos > 0 and $i->[6]->contains($$in[$pos - 1])) 0 0 0
Condition0%0/3
$pos > 0 and $i->[6]->contains($$in[$pos - 1])
!ll&&!rl&&r
000
MC/DC0%0/2
$pos > 0 and $i->[6]->contains($$in[$pos - 1])
$pos > 0 $i->[6]->contains($$in[$pos - 1])
Truth table0%0/3
A and B
A= $pos > 0B= $i->[6]->contains($$in[$pos - 1])
ABresult
0X0
100
111
746 }
747 ▶ elsif ($op == OP_WB || $op == OP_NWB) {
Condition33%1/3
$op == 7 or $op == 8
l!l&&r!l&&!r
00436893
MC/DC0%0/2
$op == 7 or $op == 8
$op == 7 $op == 8
Truth table33%1/3
A or B
A= $op == 7B= $op == 8
ABresult
1X1
011
000
748 0 ▶ my $before = $pos > 0 && _is_word($in->[ $pos - 1 ]) ? 1 : 0;
Branch: 1 branch
BranchTrueFalseTotal
$pos > 0 && _is_word($$in[$pos - 1]) ? : 0 0 0
Condition0%0/3
$pos > 0 and _is_word($$in[$pos - 1])
!ll&&!rl&&r
000
MC/DC0%0/2
$pos > 0 and _is_word($$in[$pos - 1])
$pos > 0 _is_word($$in[$pos - 1])
Truth table0%0/3
A and B
A= $pos > 0B= _is_word($$in[$pos - 1])
ABresult
0X0
100
111
749 0 ▶ my $after = $pos < $len && _is_word($in->[$pos]) ? 1 : 0;
Branch: 1 branch
BranchTrueFalseTotal
$pos < $len && _is_word($in->[$pos]) ? : 0 0 0
Condition0%0/3
$pos < $len and _is_word($in->[$pos])
!ll&&!rl&&r
000
MC/DC0%0/2
$pos < $len and _is_word($in->[$pos])
$pos < $len _is_word($in->[$pos])
Truth table0%0/3
A and B
A= $pos < $lenB= _is_word($in->[$pos])
ABresult
0X0
100
111
750 0 ▶ if (($before != $after) == ($op == OP_WB)) { $pc++; next }
Branch: 1 branch
BranchTrueFalseTotal
if (($before != $after) == ($op == 7)) 0 0 0
751 }
752 ▶ elsif ($op == OP_WB_FOLD || $op == OP_NWB_FOLD) {
Condition33%1/3
$op == 11 or $op == 12
l!l&&r!l&&!r
00436893
MC/DC0%0/2
$op == 11 or $op == 12
$op == 11 $op == 12
Truth table33%1/3
A or B
A= $op == 11B= $op == 12
ABresult
1X1
011
000
753 0 ▶ my $before = $pos > 0 && JSON::Schema::Corvus::Regex::Charset::is_fold_word($in->[ $pos - 1 ]) ? 1 : 0;
Branch: 1 branch
BranchTrueFalseTotal
$pos > 0 && JSON::Schema::Corvus::Regex::Charset::is_fold_word($$in[$pos - 1]) ? : 0 0 0
Condition0%0/3
$pos > 0 and JSON::Schema::Corvus::Regex::Charset::is_fold_word($$in[$pos - 1])
!ll&&!rl&&r
000
MC/DC0%0/2
$pos > 0 and JSON::Schema::Corvus::Regex::Charset::is_fold_word($$in[$pos - 1])
$pos > 0 JSON::Schema::Corvus::Regex::Charset::is_fold_word($$in[$pos - 1])
Truth table0%0/3
A and B
A= $pos > 0B= JSON::Schema::Corvus::Regex::Charset::is_fold_word($$in[$pos - 1])
ABresult
0X0
100
111
754 0 ▶ my $after = $pos < $len && JSON::Schema::Corvus::Regex::Charset::is_fold_word($in->[$pos]) ? 1 : 0;
Branch: 1 branch
BranchTrueFalseTotal
$pos < $len && JSON::Schema::Corvus::Regex::Charset::is_fold_word($in->[$pos]) ? : 0 0 0
Condition0%0/3
$pos < $len and JSON::Schema::Corvus::Regex::Charset::is_fold_word($in->[$pos])
!ll&&!rl&&r
000
MC/DC0%0/2
$pos < $len and JSON::Schema::Corvus::Regex::Charset::is_fold_word($in->[$pos])
$pos < $len JSON::Schema::Corvus::Regex::Charset::is_fold_word($in->[$pos])
Truth table0%0/3
A and B
A= $pos < $lenB= JSON::Schema::Corvus::Regex::Charset::is_fold_word($in->[$pos])
ABresult
0X0
100
111
755 0 ▶ if (($before != $after) == ($op == OP_WB_FOLD)) { $pc++; next }
Branch: 1 branch
BranchTrueFalseTotal
if (($before != $after) == ($op == 11)) 0 0 0
756 }
757 elsif ($op == OP_LINE_START) {
758 0 ▶ if ($pos == 0 || JSON::Schema::Corvus::Regex::Charset::is_line_terminator($in->[ $pos - 1 ])) { $pc++; next }
Branch: 1 branch
BranchTrueFalseTotal
if ($pos == 0 or JSON::Schema::Corvus::Regex::Charset::is_line_terminator($$in[$pos - 1])) 0 0 0
Condition0%0/3
$pos == 0 or JSON::Schema::Corvus::Regex::Charset::is_line_terminator($$in[$pos - 1])
l!l&&r!l&&!r
000
MC/DC0%0/2
$pos == 0 or JSON::Schema::Corvus::Regex::Charset::is_line_terminator($$in[$pos - 1])
$pos == 0 JSON::Schema::Corvus::Regex::Charset::is_line_terminator($$in[$pos - 1])
Truth table0%0/3
A or B
A= $pos == 0B= JSON::Schema::Corvus::Regex::Charset::is_line_terminator($$in[$pos - 1])
ABresult
1X1
011
000
759 }
760 elsif ($op == OP_LINE_END) {
761 0 ▶ if ($pos == $len || JSON::Schema::Corvus::Regex::Charset::is_line_terminator($in->[$pos])) { $pc++; next }
Branch: 1 branch
BranchTrueFalseTotal
if ($pos == $len or JSON::Schema::Corvus::Regex::Charset::is_line_terminator($in->[$pos])) 0 0 0
Condition0%0/3
$pos == $len or JSON::Schema::Corvus::Regex::Charset::is_line_terminator($in->[$pos])
l!l&&r!l&&!r
000
MC/DC0%0/2
$pos == $len or JSON::Schema::Corvus::Regex::Charset::is_line_terminator($in->[$pos])
$pos == $len JSON::Schema::Corvus::Regex::Charset::is_line_terminator($in->[$pos])
Truth table0%0/3
A or B
A= $pos == $lenB= JSON::Schema::Corvus::Regex::Charset::is_line_terminator($in->[$pos])
ABresult
1X1
011
000
762 }
763 elsif ($op == OP_SAVE_TMP) {
764 34251 push @stack, [ E_TMP, $i->[I_A], $tmp->[ $i->[I_A] ] ];
765 34251 $tmp->[ $i->[I_A] ] = $pos;
766 34251 $pc++;
767 34251 next;
768 }
769 elsif ($op == OP_CAPTURE) {
770 57685 my $g = $i->[I_A];
771 57685 push @stack, [ E_CAP, $g, $caps->[ 2 * $g ], $caps->[ 2 * $g + 1 ] ];
772 0 ▶ if ($i->[I_FLAG]) { @$caps[ 2 * $g, 2 * $g + 1 ] = ($pos, $tmp->[$g]) }
Branch: 1 branch
BranchTrueFalseTotal
if ($i->[9]) { } 0 57685 57685
773 57685 else { @$caps[ 2 * $g, 2 * $g + 1 ] = ($tmp->[$g], $pos) }
774 57685 $pc++;
775 57685 next;
776 }
777 elsif ($op == OP_CLEAR) {
778 34251 $steps -= $i->[I_B] - $i->[I_A];
779 34251 for my $g ($i->[I_A] .. $i->[I_B]) {
780 34251 ▶ if ($caps->[ 2 * $g ] >= 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($$caps[2 * $g] >= 0) 34247 4 34251
781 34247 push @stack, [ E_CAP, $g, $caps->[ 2 * $g ], $caps->[ 2 * $g + 1 ] ];
782 34247 @$caps[ 2 * $g, 2 * $g + 1 ] = (-1, -1);
783 }
784 }
785 34251 $pc++;
786 34251 next;
787 }
788 ▶ elsif ($op == OP_BACKREF || $op == OP_BACKREF_FOLD) {
Condition66%2/3
$op == 18 or $op == 20
l!l&&r!l&&!r
843400226366
MC/DC50%1/2
$op == 18 or $op == 20
$op == 18 $op == 20
Truth table66%2/3
A or B
A= $op == 18B= $op == 20
ABresult
1X1
011
000
789 # A group that has not taken part matches the empty string.
790 84340 my ($from, $to) = @$caps[ 2 * $i->[I_A], 2 * $i->[I_A] + 1 ];
791 0 ▶ if ($from < 0) { $pc++; next }
Branch: 1 branch
BranchTrueFalseTotal
if ($from < 0) 0 84340 84340
792 84340 my $n = $to - $from;
793 84340 ▶ if ($len - $pos >= $n) {
Branch: 1 branch
BranchTrueFalseTotal
if ($len - $pos >= $n) 65616 18724 84340
794 65616 my $ok = 1;
795 65616 for my $k (0 .. $n - 1) {
796 74965 my ($got, $want) = ($in->[ $pos + $k ], $in->[ $from + $k ]);
797 74965 ▶ next if $got == $want;
Branch: 1 branch
BranchTrueFalseTotal
if $got == $want 36005 38960 74965
798 38960 ▶ if ($op == OP_BACKREF_FOLD
Branch: 1 branch
BranchTrueFalseTotal
if ($op == 20 and JSON::Schema::Corvus::Regex::Charset::canonicalize($got, $i->[9]) == JSON::Schema::Corvus::Regex::Charset::canonicalize($want, $i->[9])) 0 38960 38960
Condition33%1/3
$op == 20 and JSON::Schema::Corvus::Regex::Charset::canonicalize($got, $i->[9]) == JSON::Schema::Corvus::Regex::Charset::canonicalize($want, $i->[9])
!ll&&!rl&&r
3896000
MC/DC0%0/2
$op == 20 and JSON::Schema::Corvus::Regex::Charset::canonicalize($got, $i->[9]) == JSON::Schema::Corvus::Regex::Charset::canonicalize($want, $i->[9])
$op == 20 JSON::Schema::Corvus::Regex::Charset::canonicalize($got, $i->[9]) == JSON::Schema::Corvus::Regex::Charset::canonicalize($want, $i->[9])
Truth table33%1/3
A and B
A= $op == 20B= JSON::Schema::Corvus::Regex::Charset::canonicalize($got, $i->[9]) == JSON::Schema::Corvus::Regex::Charset::canonicalize($want, $i->[9])
ABresult
0X0
100
111
799 && JSON::Schema::Corvus::Regex::Charset::canonicalize($got, $i->[I_FLAG])
800 == JSON::Schema::Corvus::Regex::Charset::canonicalize($want, $i->[I_FLAG])) {
801 0 next;
802 }
803 38960 $ok = 0;
804 38960 last;
805 }
806 65616 ▶ if ($ok) {
Branch: 1 branch
BranchTrueFalseTotal
if ($ok) 26656 38960 65616
807 26656 $steps -= $n >> 3;
808 26656 $pos += $n;
809 26656 $pc++;
810 26656 next;
811 }
812 }
813 }
814 ▶ elsif ($op == OP_BACKREF_BACK || $op == OP_BACKREF_FOLD_BACK) {
Condition33%1/3
$op == 19 or $op == 21
l!l&&r!l&&!r
00226366
MC/DC0%0/2
$op == 19 or $op == 21
$op == 19 $op == 21
Truth table33%1/3
A or B
A= $op == 19B= $op == 21
ABresult
1X1
011
000
815 0 my ($from, $to) = @$caps[ 2 * $i->[I_A], 2 * $i->[I_A] + 1 ];
816 0 ▶ if ($from < 0) { $pc++; next }
Branch: 1 branch
BranchTrueFalseTotal
if ($from < 0) 0 0 0
817 0 my $n = $to - $from;
818 0 ▶ if ($pos >= $n) {
Branch: 1 branch
BranchTrueFalseTotal
if ($pos >= $n) 0 0 0
819 0 my $ok = 1;
820 0 for my $k (1 .. $n) {
821 0 my ($got, $want) = ($in->[ $pos - $k ], $in->[ $to - $k ]);
822 0 ▶ next if $got == $want;
Branch: 1 branch
BranchTrueFalseTotal
if $got == $want 0 0 0
823 0 ▶ if ($op == OP_BACKREF_FOLD_BACK
Branch: 1 branch
BranchTrueFalseTotal
if ($op == 21 and JSON::Schema::Corvus::Regex::Charset::canonicalize($got, $i->[9]) == JSON::Schema::Corvus::Regex::Charset::canonicalize($want, $i->[9])) 0 0 0
Condition0%0/3
$op == 21 and JSON::Schema::Corvus::Regex::Charset::canonicalize($got, $i->[9]) == JSON::Schema::Corvus::Regex::Charset::canonicalize($want, $i->[9])
!ll&&!rl&&r
000
MC/DC0%0/2
$op == 21 and JSON::Schema::Corvus::Regex::Charset::canonicalize($got, $i->[9]) == JSON::Schema::Corvus::Regex::Charset::canonicalize($want, $i->[9])
$op == 21 JSON::Schema::Corvus::Regex::Charset::canonicalize($got, $i->[9]) == JSON::Schema::Corvus::Regex::Charset::canonicalize($want, $i->[9])
Truth table0%0/3
A and B
A= $op == 21B= JSON::Schema::Corvus::Regex::Charset::canonicalize($got, $i->[9]) == JSON::Schema::Corvus::Regex::Charset::canonicalize($want, $i->[9])
ABresult
0X0
100
111
824 && JSON::Schema::Corvus::Regex::Charset::canonicalize($got, $i->[I_FLAG])
825 == JSON::Schema::Corvus::Regex::Charset::canonicalize($want, $i->[I_FLAG])) {
826 0 next;
827 }
828 0 $ok = 0;
829 0 last;
830 }
831 0 ▶ if ($ok) {
Branch: 1 branch
BranchTrueFalseTotal
if ($ok) 0 0 0
832 0 $steps -= $n >> 3;
833 0 $pos -= $n;
834 0 $pc++;
835 0 next;
836 }
837 }
838 }
839 elsif ($op == OP_LOOK) {
840 # What follows a lookaround starts where the lookaround does, and so does the body of a lookahead.
841 0 ▶ if (_allows($quick->[$pc], $in, $pos)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_allows($quick->[$pc], $in, $pos)) 0 0 0
842 0 ▶ push @stack, [ $i->[I_FLAG] ? E_LOOK_NEG : E_LOOK, $i->[I_X], $pos ];
Branch: 1 branch
BranchTrueFalseTotal
$i->[9] ? : 0 0 0
843 0 $pc++;
844 0 next;
845 }
846 }
847 elsif ($op == OP_LOOK_OK) {
848 # The body matched. A lookaround is atomic, so the choices made inside it are dropped; the undo entries stay,
849 # because the groups it set remain set until something below this point is retried.
850 0 my $f = $#stack;
851 0 ▶ $f-- while $stack[$f][0] != E_LOOK;
Branch: 1 branch
BranchTrueFalseTotal
$stack[$f][0] != 3 and do { --$f } 0 0 0
852 0 $pos = $stack[$f][2];
853 0 my @kept = grep { $_->[0] >= E_TMP } @stack[ $f + 1 .. $#stack ];
854 0 splice @stack, $f, @stack - $f, @kept;
855 0 $pc++;
856 0 next;
857 }
858 elsif ($op == OP_LOOK_FAIL) {
859 # The body of a negative lookaround matched, so the lookaround fails and everything it did is undone.
860 0 while (1) {
861 0 my $e = pop @stack;
862 0 ▶ last if $e->[0] == E_LOOK_NEG;
Branch: 1 branch
BranchTrueFalseTotal
if $e->[0] == 4 0 0 0
863 0 _undo($st, $e);
864 }
865 }
866 elsif ($op == OP_REP_LAZY) {
867 0 my ($at, $n) = ($pos, 0);
868 0 ▶ while ($n < $i->[I_MIN]) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n < $i->[7]) 0 0 0
869 0 ▶ my $w = _one($i, $in, $at) or last;
Branch: 1 branch
BranchTrueFalseTotal
my $w = _one($i, $in, $at) or last 0 0 0
870 0 $at += $w;
871 0 $n++;
872 }
873 0 $steps -= $n >> 3;
874 0 ▶ if ($n == $i->[I_MIN]) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n == $i->[7]) 0 0 0
875 0 ▶ if ($memo && $i->[I_M]) {
Branch: 1 branch
BranchTrueFalseTotal
if ($memo and $i->[10]) 0 0 0
Condition0%0/3
$memo and $i->[10]
!ll&&!rl&&r
000
MC/DC0%0/2
$memo and $i->[10]
$memo $i->[10]
Truth table0%0/3
A and B
A= $memoB= $i->[10]
ABresult
0X0
100
111
876 0 my $idx = $self->_memo_index($st, $i->[I_M], $at);
877 0 ▶ if (vec($$memo, $idx, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (vec $$memo, $idx, 1) 0 0 0
878 # What follows the loop has failed from here before. The loop takes one more character.
879 0 ▶ push @stack, [ E_REP_LAZY, $pc, $at, $n ] if $n != $i->[I_MAX];
Branch: 1 branch
BranchTrueFalseTotal
if $n != $i->[8] 0 0 0
880 0 goto BACKTRACK;
881 }
882 0 ▶ push @stack, [ E_MARK, 0, $idx ] if $n == $i->[I_MAX] && @stack < MAX_MARK_DEPTH;
Branch: 1 branch
BranchTrueFalseTotal
if $n == $i->[8] and @stack < 524288 0 0 0
Condition0%0/3
$n == $i->[8] and @stack < 524288
!ll&&!rl&&r
000
MC/DC0%0/2
$n == $i->[8] and @stack < 524288
$n == $i->[8] @stack < 524288
Truth table0%0/3
A and B
A= $n == $i->[8]B= @stack < 524288
ABresult
0X0
100
111
883 }
884 0 ▶ push @stack, [ E_REP_LAZY, $pc, $at, $n ] if $n != $i->[I_MAX];
Branch: 1 branch
BranchTrueFalseTotal
if $n != $i->[8] 0 0 0
885 0 $pos = $at;
886 0 $pc++;
887 0 next;
888 }
889 }
890 elsif ($op == OP_LOOP_INIT) {
891 57685 my $k = $i->[I_A];
892 57685 push @stack, [ E_COUNTER, $k, $counts->[ 2 * $k ], $counts->[ 2 * $k + 1 ] ];
893 57685 @$counts[ 2 * $k, 2 * $k + 1 ] = (0, -1);
894 57685 $pc++;
895 57685 next;
896 }
897 elsif ($op == OP_LOOP) {
898 84340 my $k = $i->[I_A];
899 84340 my $n = $counts->[ 2 * $k ];
900 84340 my $left = $len - $pos;
901 # Fewer characters are left than any way from here to a match consumes.
902 84340 ▶ goto BACKTRACK if $left < $i->[I_NEED]
Branch: 1 branch
BranchTrueFalseTotal
if $left < $i->[11] or $n < $i->[7] and $i->[12] and $left - $i->[11] < ($i->[7] - $n) * $i->[12] 0 84340 84340
Condition33%3/9
$left < $i->[11] or $n < $i->[7] and $i->[12] and $left - $i->[11] < ($i->[7] - $n) * $i->[12]
l!l&&r!l&&!r
0084340
$n < $i->[7] and $i->[12] and $left - $i->[11] < ($i->[7] - $n) * $i->[12]
!ll&&!rl&&r
8434000
$n < $i->[7] and $i->[12]
!ll&&!rl&&r
8434000
MC/DC0%0/4
$left < $i->[11] or $n < $i->[7] and $i->[12] and $left - $i->[11] < ($i->[7] - $n) * $i->[12]
$left < $i->[11] $n < $i->[7] $i->[12] $left - $i->[11] < ($i->[7] - $n) * $i->[12]
Truth table20%1/5
A or B and C and D
A= $left < $i->[11]B= $n < $i->[7]C= $i->[12]D= $left - $i->[11] < ($i->[7] - $n) * $i->[12]
ABCDresult
1XXX1
01111
00XX0
010X0
01100
903 || ($n < $i->[I_MIN] && $i->[I_ITER] && $left - $i->[I_NEED] < ($i->[I_MIN] - $n) * $i->[I_ITER]);
904 # Once the minimum is met, ECMA-262 rejects an iteration that consumed nothing.
905 84340 ▶ goto BACKTRACK if $n > $i->[I_MIN] && $pos == $counts->[ 2 * $k + 1 ];
Branch: 1 branch
BranchTrueFalseTotal
if $n > $i->[7] and $pos == $$counts[2 * $k + 1] 0 84340 84340
Condition66%2/3
$n > $i->[7] and $pos == $$counts[2 * $k + 1]
!ll&&!rl&&r
57684266560
MC/DC0%0/2
$n > $i->[7] and $pos == $$counts[2 * $k + 1]
$n > $i->[7] $pos == $$counts[2 * $k + 1]
Truth table66%2/3
A and B
A= $n > $i->[7]B= $pos == $$counts[2 * $k + 1]
ABresult
0X0
100
111
906 0 ▶ if ($n < $i->[I_MIN]) { $pc++; next }
Branch: 1 branch
BranchTrueFalseTotal
if ($n < $i->[7]) 0 84340 84340
907 0 ▶ if ($i->[I_MAX] >= 0 && $n >= $i->[I_MAX]) { $pc = $i->[I_X]; next }
Branch: 1 branch
BranchTrueFalseTotal
if ($i->[8] >= 0 and $n >= $i->[8]) 0 84340 84340
Condition33%1/3
$i->[8] >= 0 and $n >= $i->[8]
!ll&&!rl&&r
8434000
MC/DC0%0/2
$i->[8] >= 0 and $n >= $i->[8]
$i->[8] >= 0 $n >= $i->[8]
Truth table33%1/3
A and B
A= $i->[8] >= 0B= $n >= $i->[8]
ABresult
0X0
100
111
908 # The loop may be left or entered from here. A place from which both have failed before fails at once.
909 84340 ▶ if ($memo && $i->[I_M]) {
Branch: 1 branch
BranchTrueFalseTotal
if ($memo and $i->[10]) 0 84340 84340
Condition33%1/3
$memo and $i->[10]
!ll&&!rl&&r
8434000
MC/DC0%0/2
$memo and $i->[10]
$memo $i->[10]
Truth table33%1/3
A and B
A= $memoB= $i->[10]
ABresult
0X0
100
111
910 0 my $idx = $self->_memo_index($st, $i->[I_M], $pos);
911 0 ▶ goto BACKTRACK if vec($$memo, $idx, 1);
Branch: 1 branch
BranchTrueFalseTotal
if vec $$memo, $idx, 1 0 0 0
912 0 ▶ push @stack, [ E_MARK, 0, $idx ] if @stack < MAX_MARK_DEPTH;
Branch: 1 branch
BranchTrueFalseTotal
if @stack < 524288 0 0 0
913 }
914 84340 ▶ if (!_allows($quick->[ $i->[I_X] ], $in, $pos)) { $pc++ }
Branch: 3 branches
BranchTrueFalseTotal
if (not _allows($$quick[$i->[1]], $in, $pos)) { } 50090 34250 84340
elsif (not _allows($$quick[$pc + 1], $in, $pos)) { } 0 34250 34250
elsif ($i->[9]) { } 0 34250 34250
915 0 elsif (!_allows($quick->[ $pc + 1 ], $in, $pos)) { $pc = $i->[I_X] }
916 0 elsif ($i->[I_FLAG]) { push @stack, [ E_CHOICE, $pc + 1, $pos ]; $pc = $i->[I_X] }
917 34250 else { push @stack, [ E_CHOICE, $i->[I_X], $pos ]; $pc++ }
918 84340 next;
919 }
920 elsif ($op == OP_LOOP_ITER) {
921 84340 my $k = $i->[I_A];
922 84340 push @stack, [ E_COUNTER, $k, $counts->[ 2 * $k ], $counts->[ 2 * $k + 1 ] ];
923 84340 $counts->[ 2 * $k ]++;
924 84340 $counts->[ 2 * $k + 1 ] = $pos;
925 84340 $pc++;
926 84340 next;
927 }
928 elsif ($op == OP_MATCH) {
929 1 $st->{steps} = $steps;
930 1 return 1;
931 }
932  
933 # The instruction failed. Take up the most recent choice, undoing what was recorded since.
934 BACKTRACK:
935 57684 while (1) {
936 325860 ▶ if (!@stack) {
Branch: 1 branch
BranchTrueFalseTotal
unless (@stack) 2 325858 325860
937 2 $st->{steps} = $steps;
938 2 return 0;
939 }
940 325858 my $e = $stack[-1];
941 325858 my $kind = $e->[0];
942 325858 ▶ if ($kind == E_CHOICE) {
Branch: 1 branch
BranchTrueFalseTotal
if ($kind == 0) 34248 291610 325858
943 34248 ($pc, $pos) = ($e->[1], $e->[2]);
944 34248 pop @stack;
945 34248 last;
946 }
947 291610 ▶ if ($kind == E_REP) {
Branch: 1 branch
BranchTrueFalseTotal
if ($kind == 1) 23434 268176 291610
948 # What followed the loop from the position it stood at has failed.
949 23434 my $rep = $insts->[ $e->[1] - 1 ];
950 23434 ▶ my $marked = $memo && $rep->[I_M];
Condition33%1/3
$memo && $rep->[10]
!ll&&!rl&&r
2343400
MC/DC0%0/2
$memo && $rep->[10]
$memo $rep->[10]
Truth table33%1/3
A && B
A= $memoB= $rep->[10]
ABresult
0X0
100
111
951 23434 ▶ vec($$memo, $self->_memo_index($st, $rep->[I_M], $e->[2]), 1) = 1 if $marked;
Branch: 1 branch
BranchTrueFalseTotal
if $marked 0 23434 23434
952 # Give back the last character taken.
953 23434 $e->[2]--;
954 23434 ($pc, $pos) = ($e->[1], $e->[2]);
955 23434 my $last = $e->[2] <= $e->[3];
956 # A position from which what follows the loop cannot go on is passed over, and so is one from which it has
957 # failed before.
958 23434 my $pass = !_allows($quick->[$pc], $in, $pos);
959 23434 ▶ if ($marked && !$pass) {
Branch: 1 branch
BranchTrueFalseTotal
if ($marked and not $pass) 0 23434 23434
Condition33%1/3
$marked and not $pass
!ll&&!rl&&r
2343400
MC/DC0%0/2
$marked and not $pass
$marked not $pass
Truth table33%1/3
A and not(B)
A= $markedB= not $pass
ABresult
0X0
100
111
960 0 my $idx = $self->_memo_index($st, $rep->[I_M], $pos);
961 0 ▶ if (vec($$memo, $idx, 1)) {
Branch: 2 branches
BranchTrueFalseTotal
if (vec $$memo, $idx, 1) { } 0 0 0
elsif ($last) { } 0 0 0
962 0 $pass = 1;
963 }
964 elsif ($last) {
965 # The loop has nothing more to give back. The entry stays to note this last way.
966 0 $stack[-1] = [ E_MARK, 0, $idx ];
967 0 last;
968 }
969 }
970 23434 ▶ pop @stack if $last;
Branch: 1 branch
BranchTrueFalseTotal
if $last 13913 9521 23434
971 23434 ▶ if ($pass) {
Branch: 1 branch
BranchTrueFalseTotal
if ($pass) 0 23434 23434
972 0 $steps--;
973 0 next;
974 }
975 23434 last;
976 }
977 268176 ▶ if ($kind == E_REP_LAZY) {
Branch: 1 branch
BranchTrueFalseTotal
if ($kind == 2) 0 268176 268176
978 0 my $rep = $insts->[ $e->[1] ];
979 0 ▶ my $marked = $memo && $rep->[I_M];
Condition0%0/3
$memo && $rep->[10]
!ll&&!rl&&r
000
MC/DC0%0/2
$memo && $rep->[10]
$memo $rep->[10]
Truth table0%0/3
A && B
A= $memoB= $rep->[10]
ABresult
0X0
100
111
980 0 ▶ vec($$memo, $self->_memo_index($st, $rep->[I_M], $e->[2]), 1) = 1 if $marked;
Branch: 1 branch
BranchTrueFalseTotal
if $marked 0 0 0
981 0 my $w = _one($rep, $in, $e->[2]);
982 0 ▶ if (!$w) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($w) 0 0 0
983 0 pop @stack;
984 0 next;
985 }
986 0 $e->[2] += $w;
987 0 $e->[3]++;
988 0 ($pc, $pos) = ($e->[1] + 1, $e->[2]);
989 0 my $last = $e->[3] == $rep->[I_MAX];
990 0 ▶ if ($marked) {
Branch: 1 branch
BranchTrueFalseTotal
if ($marked) 0 0 0
991 0 my $idx = $self->_memo_index($st, $rep->[I_M], $pos);
992 0 ▶ if (vec($$memo, $idx, 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (vec $$memo, $idx, 1) 0 0 0
993 0 ▶ pop @stack if $last;
Branch: 1 branch
BranchTrueFalseTotal
if $last 0 0 0
994 0 $steps--;
995 0 next;
996 }
997 0 ▶ if ($last) {
Branch: 1 branch
BranchTrueFalseTotal
if ($last) 0 0 0
998 0 $stack[-1] = [ E_MARK, 0, $idx ];
999 0 last;
1000 }
1001 }
1002 0 ▶ pop @stack if $last;
Branch: 1 branch
BranchTrueFalseTotal
if $last 0 0 0
1003 0 last;
1004 }
1005 268176 ▶ if ($kind == E_MARK) {
Branch: 1 branch
BranchTrueFalseTotal
if ($kind == 5) 0 268176 268176
1006 # Every way from a memo point has failed.
1007 0 ▶ vec($$memo, $e->[2], 1) = 1 if $memo;
Branch: 1 branch
BranchTrueFalseTotal
if $memo 0 0 0
1008 0 pop @stack;
1009 0 next;
1010 }
1011 268176 ▶ if ($kind == E_LOOK) {
Branch: 1 branch
BranchTrueFalseTotal
if ($kind == 3) 0 268176 268176
1012 # The body of a positive lookaround has no way left to match.
1013 0 pop @stack;
1014 0 next;
1015 }
1016 268176 ▶ if ($kind == E_LOOK_NEG) {
Branch: 1 branch
BranchTrueFalseTotal
if ($kind == 4) 0 268176 268176
1017 # The body of a negative lookaround has no way to match, so the lookaround holds.
1018 0 ($pc, $pos) = ($e->[1], $e->[2]);
1019 0 pop @stack;
1020 0 last;
1021 }
1022 268176 _undo($st, $e);
1023 268176 pop @stack;
1024 }
1025 }
1026 }
1027  
1028 4 1;
↑ Summary Corvus/Collecting.pm »