blib/lib/Parse/BooleanLogic.pm

filter: Statementstmt 81.6% 222 / 272 Branchbran 71.9% 105 / 146 Conditioncond 73.2% 71 / 97 MC/DCmcdc 48.0% 25 / 52 Subroutinesub 71.4% 20 / 28 Podpod 92.8% 13 / 14 totaltotal 74.8% 456 / 609 CC 111 SCAR 29.3
CC
111
Cov
77%
walk
72.0
as_array
30.0
parse
27.9
CRAP 18.8
↑ Summary
1 =head1 NAME
2  
3 Parse::BooleanLogic - parser of boolean expressions
4  
5 =head1 SYNOPSIS
6  
7 use Parse::BooleanLogic;
8 use Data::Dumper;
9  
10 my $parser = Parse::BooleanLogic->new( operators => ['', 'OR'] );
11 my $tree = $parser->as_array( 'label:parser subject:"boolean logic"' );
12 print Dumper($tree);
13  
14 $parser = new Parse::BooleanLogic;
15 $tree = $parser->as_array( 'x = 10' );
16 print Dumper($tree);
17  
18 $tree = $parser->as_array( 'x = 10 OR (x > 20 AND x < 30)' );
19 print Dumper($tree);
20  
21 # custom parsing using callbacks
22 $parser->parse(
23 string => 'x = 10 OR (x > 20 AND x < 30)',
24 callback => {
25 open_paren => sub { ... },
26 operator => sub { ... },
27 operand => sub { ... },
28 close_paren => sub { ... },
29 error => sub { ... },
30 },
31 );
32  
33 =head1 DESCRIPTION
34  
35 This module is quite fast parser for boolean expressions. Originally it's been writen for
36 Request Tracker to parse SQL like expressions and it's still capable, but
37 it can be used to parse other boolean logic sentences with OPERANDs joined using
38 binary OPERATORs and grouped and nested using parentheses (OPEN_PAREN and CLOSE_PAREN).
39  
40 Operand is not qualified strictly what makes parser flexible enough to parse different
41 things, for example:
42  
43 # SQL like expressions
44 (task.status = "new" OR task.status = "open") AND task.owner_id = 123
45  
46 # Google like search syntax used in Gmail and other service
47 subject:"some text" (from:me OR to:me) label:todo !label:done
48  
49 # Binary boolean logic expressions
50 (a | b) & (c | d)
51  
52 You can change literals used for boolean operators and parens. Read more
53 about this in description of constructor's arguments.
54  
55 As you can see quoted strings are supported. Read about that below in
56 L<Quoting and dequoting>.
57  
58 =cut
59  
60 10 ▶use 5.008;
Subroutine BEGIN: called CC=1 SCAR=0.0
61 10 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
62 10 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
63  
64 package Parse::BooleanLogic;
65  
66 10 our $VERSION = '0.10';
67  
68 10 ▶use constant OPERAND => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
69 10 ▶use constant OPERATOR => 2;
Subroutine BEGIN: called CC=1 SCAR=0.0
70 10 ▶use constant OPEN_PAREN => 4;
Subroutine BEGIN: called CC=1 SCAR=0.0
71 10 ▶use constant CLOSE_PAREN => 8;
Subroutine BEGIN: called CC=1 SCAR=0.0
72 10 ▶use constant STOP => 16;
Subroutine BEGIN: called CC=1 SCAR=0.0
73 10 my @tokens = qw[OPERAND OPERATOR OPEN_PAREN CLOSE_PAREN STOP];
74  
75 10 ▶use Regexp::Common qw(delimited);
Subroutine BEGIN: called CC=1 SCAR=0.0
76 10 my $re_delim = qr{$RE{delimited}{-delim=>qq{\'\"}}{-esc=>'\\'}};
77  
78 =head1 METHODS
79  
80 =head2 Building parser
81  
82 =head3 new
83  
84 A constuctor, takes the following named arguments:
85  
86 =over 4
87  
88 =item operators, default is ['AND' 'OR']
89  
90 Pair of literal strings representing boolean operators AND and OR,
91 pass it as array reference. For example:
92  
93 # from t/custom_ops.t
94 my $parser = Parse::BooleanLogic->new( operators => [qw(& |)] );
95  
96 # from t/custom_googlish.t
97 my $parser = Parse::BooleanLogic->new( operators => ['', 'OR'] );
98  
99 It's ok to have any operators and even empty.
100  
101 =item parens, default is ['(', ')']
102  
103 Pair of literal strings representing parentheses, for example it's
104 possible to use curly braces:
105  
106 # from t/custom_parens.t
107 my $parser = Parse::BooleanLogic->new( parens => [qw({ })] );
108  
109 No matter which pair is used parens must be balanced in expression.
110  
111 =back
112  
113 This constructor compiles several heavy weight regular expressions
114 so it's better avoid building object each time right before parsing,
115 but instead use global or cached one.
116  
117 =cut
118  
119 9 ▶sub new {
Subroutine new: called CC=2 SCAR=7.6
Pod documented
120 9 my $proto = shift;
121 9 ▶ my $self = bless {}, ref($proto) || $proto;
Condition33%1/3
ref $proto || $proto
l!l&&r!l&&!r
090
MC/DC0%0/2
ref $proto || $proto
ref $proto $proto
Truth table33%1/3
A || B
A= ref $protoB= $proto
ABresult
1X1
011
000
122 9 return $self->init( @_ );
123 }
124  
125 =head3 init
126  
127 An initializer, called from the constructor. Compiles regular expressions
128 and do other things with constructor's arguments. Returns this object back.
129  
130 =cut
131  
132 9 ▶sub init {
Subroutine init: called CC=9 SCAR=22.0
Pod documented
133 9 my $self = shift;
134 9 my %args = @_;
135 9 ▶ if ( $args{'operators'} ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($args{'operators'}) { } 2 7 9
136 2 my @ops = map lc $_, @{ $args{'operators'} };
137 2 $self->{'operators'} = [ @ops ];
138 2 ▶ @ops = reverse @ops if length $ops[1] > length $ops[0];
Branch: 1 branch
BranchTrueFalseTotal
if length $ops[1] > length $ops[0] 1 1 2
139 2 foreach ( @ops ) {
140 4 ▶ unless ( length ) {
Branch: 1 branch
BranchTrueFalseTotal
if (length $_) { } 3 1 4
141 1 $_ = "(?<=\\s)";
142 }
143 else {
144 3 ▶ if ( /^\w/ ) {
Branch: 1 branch
BranchTrueFalseTotal
if (/^\w/) { } 1 2 3
145 1 $_ = '\b'. "\Q$_\E";
146 }
147 else {
148 2 $_ = "\Q$_\E";
149 }
150 3 ▶ if ( /\w$/ ) {
Branch: 1 branch
BranchTrueFalseTotal
if (/\w$/) 1 2 3
151 1 $_ .= '\b';
152 }
153 }
154 4 $self->{'re_operator'} = qr{(?:$ops[0]|$ops[1])}i;
155 }
156 } else {
157 7 $self->{'operators'} = [qw(and or)];
158 7 $self->{'re_operator'} = qr{\b(?:AND|OR)\b}i;
159 }
160  
161 9 ▶ if ( $args{'parens'} ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($args{'parens'}) { } 1 8 9
162 1 $self->{'parens'} = $args{'parens'};
163 1 $self->{'re_open_paren'} = qr{\Q$args{'parens'}[0]\E};
164 1 $self->{'re_close_paren'} = qr{\Q$args{'parens'}[1]\E};
165 } else {
166 8 $self->{'re_open_paren'} = qr{\(};
167 8 $self->{'re_close_paren'} = qr{\)};
168 }
169 9 $self->{'re_tokens'} = qr{(?:$self->{'re_operator'}|$self->{'re_open_paren'}|$self->{'re_close_paren'})};
170 # the following need some explanation
171 # operand is something consisting of delimited strings and other strings that are not our major tokens
172 # so it's a (delim string or anything until a token, ['"](start of a delim) or \Z) - this is required part
173 # then you can have zero or more ocurences of above group, but with one exception - "anything" can not start with a token or ["']
174 9 $self->{'re_operand'} = qr{(?:$re_delim|.+?(?=$self->{re_tokens}|["']|\Z))(?:$re_delim|(?!$self->{re_tokens}|["']).+?(?=$self->{re_tokens}|["']|\Z))*};
175  
176 9 foreach my $re (qw(re_operator re_operand re_open_paren re_close_paren)) {
177 36 $self->{"m$re"} = qr{\G($self->{$re})};
178 }
179  
180 9 return $self;
181 }
182  
183  
184 =head2 Parsing expressions
185  
186 =head3 as_array $string [ %options ]
187  
188 Takes a string and parses it into perl structure, where parentheses represented using
189 array references, operands are hash references with one key/value pair: operand,
190 when binary operators are simple scalars. So string C<x = 10 OR (x > 20 AND x < 30)>
191 is parsed into the following structure:
192  
193 [
194 { operand => 'x = 10' },
195 'OR',
196 [
197 { operand => 'x > 20' },
198 'AND',
199 { operand => 'x < 30' },
200 ]
201 ]
202  
203 Aditional options:
204  
205 =over 4
206  
207 =item operand_cb - custom operands handler, for example:
208  
209 my $tree = $parser->as_array(
210 "some string",
211 operand_cb => sub {
212 my $op = shift;
213 if ( $op =~ m/^(!?)(label|subject|from|to):(.*)/ ) {
214 ...
215 } else {
216 die "You have an error in your query, in '$op'";
217 }
218 },
219 );
220  
221  
222 =item error_cb - custom errors handler
223  
224 my $tree = $parser->as_array(
225 "some string",
226 error_cb => sub {
227 my $msg = shift;
228 MyParseException->throw($msg);
229 },
230 );
231  
232 =back
233  
234 =cut
235  
236 { # static variables
237  
238 10 my ($tree, $node, @pnodes);
239 10 my %callback;
240 0 ▶$callback{'open_paren'} = sub {
Subroutine __ANON__: not called CC=1 SCAR=6.9
241 0 push @pnodes, $node;
242 0 push @{ $pnodes[-1] }, $node = []
243 10 };
244 0 ▶$callback{'close_paren'} = sub { $node = pop @pnodes };
Subroutine __ANON__: not called CC=1 SCAR=1.2
245 0 ▶$callback{'operator'} = sub { push @$node, $_[0] };
Subroutine __ANON__: not called CC=1 SCAR=1.2
246 0 ▶$callback{'operand'} = sub { push @$node, { operand => $_[0] } };
Subroutine __ANON__: not called CC=1 SCAR=1.2
247  
248 0 ▶sub as_array {
Subroutine as_array: not called CC=5 SCAR=34.0
Pod documented
249 0 my $self = shift;
250 0 my $string = shift;
251 0 my %arg = (@_);
252  
253 0 $node = $tree = [];
254 0 @pnodes = ();
255  
256 0 ▶ unless ( $arg{'operand_cb'} || $arg{'error_cb'} ) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($arg{"operand_cb"} or $arg{"error_cb"}) 0 0 0
Condition0%0/3
$arg{"operand_cb"} or $arg{"error_cb"}
l!l&&r!l&&!r
000
MC/DC0%0/2
$arg{"operand_cb"} or $arg{"error_cb"}
$arg{"operand_cb"} $arg{"error_cb"}
Truth table0%0/3
A or B
A= $arg{"operand_cb"}B= $arg{"error_cb"}
ABresult
1X1
011
000
257 0 $self->parse(string => $string, callback => \%callback);
258 0 return $tree;
259 }
260  
261 0 my %cb = %callback;
262 0 ▶ if ( $arg{'operand_cb'} ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($arg{"operand_cb"}) 0 0 0
263 0 ▶ $cb{'operand'} = sub { push @$node, $arg{'operand_cb'}->( $_[0] ) };
Subroutine __ANON__: not called CC=1 SCAR=6.9
264 }
265 0 ▶ $cb{'error'} = $arg{'error_cb'} if $arg{'error_cb'};
Branch: 1 branch
BranchTrueFalseTotal
if $arg{"error_cb"} 0 0 0
266 0 $self->parse(string => $string, callback => \%cb);
267 0 return $tree;
268 } }
269  
270 =head3 parse
271  
272 Takes named arguments: string and callback. Where the first one is scalar with
273 expression, the latter is a reference to hash with callbacks: open_paren, operator
274 operand, close_paren and error. Callback for errors is optional and parser dies if
275 it's omitted. Each callback is called when parser finds corresponding element in the
276 string. In all cases the current match is passed as argument into the callback.
277  
278 Here is simple example based on L</as_array> method:
279  
280 # result tree and the current group
281 my ($tree, $node);
282 $tree = $node = [];
283  
284 # stack with nested groups, outer most in the bottom, inner on the top
285 my @pnodes = ();
286  
287 my %callback;
288 # on open_paren put the current group on top of the stack,
289 # create new empty group and at the same time put it into
290 # the end of previous one
291 $callback{'open_paren'} = sub {
292 push @pnodes, $node;
293 push @{ $pnodes[-1] }, $node = []
294 };
295  
296 # on close_paren just switch to previous group by taking it
297 # from the top of the stack
298 $callback{'close_paren'} = sub { $node = pop @pnodes };
299  
300 # push binary operators as is and operands as hash references
301 $callback{'operator'} = sub { push @$node, $_[0] };
302 $callback{'operand'} = sub { push @$node, { operand => $_[0] } };
303  
304 # run parser
305 $parser->parse( string => $string, callback => \%callback );
306  
307 return $tree;
308  
309 Using this method you can build other representations of an expression.
310  
311 =cut
312  
313 10 ▶sub parse {
Subroutine parse: called CC=20 SCAR=33.3
Pod documented
314 33 my $self = shift;
315 33 my %args = (
316 string => '',
317 callback => {},
318 @_
319 );
320 33 my ($string, $cb) = @args{qw(string callback)};
321 33 ▶ $string = '' unless defined $string;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $string 0 33 33
322  
323 # States
324 33 my $want = OPERAND | OPEN_PAREN | STOP;
325 33 my $last = 0;
326 33 my $depth = 0;
327  
328 33 while (1) {
329 # State Machine
330 143 ▶ if ( $string =~ /\G\s+/gc ) {
Branch: 6 branches
BranchTrueFalseTotal
if ($string =~ /\G\s+/cg) { } 17 126 143
elsif ($want & 2 and $string =~ /$self->{'mre_operator'}/cg) { } 17 109 126
elsif ($want & 4 and $string =~ /$self->{'mre_open_paren'}/cg) { } 14 95 109
elsif ($want & 8 and $string =~ /$self->{'mre_close_paren'}/cg) { } 14 81 95
elsif ($want & 1 and $string =~ /$self->{'mre_operand'}/cg) { } 48 33 81
elsif ($want & 16 and $string =~ /\G\s*$/cig) { } 33 0 33
331 }
332 ▶ elsif ( ($want & OPERATOR ) && $string =~ /$self->{'mre_operator'}/gc ) {
Condition100%3/3
$want & 2 and $string =~ /$self->{"mre_operator"}/cg
!ll&&!rl&&r
644517
MC/DC100%2/2
$want & 2 and $string =~ /$self->{"mre_operator"}/cg
$want & 2 $string =~ /$self->{"mre_operator"}/cg
Truth table100%3/3
A and B
A= $want & 2B= $string =~ /$self->{"mre_operator"}/cg
ABresult
0X0
100
111
333 17 $cb->{'operator'}->( $1 );
334 17 $last = OPERATOR;
335 17 $want = OPERAND | OPEN_PAREN;
336 }
337 ▶ elsif ( ($want & OPEN_PAREN ) && $string =~ /$self->{'mre_open_paren'}/gc ) {
Condition100%3/3
$want & 4 and $string =~ /$self->{"mre_open_paren"}/cg
!ll&&!rl&&r
455014
MC/DC100%2/2
$want & 4 and $string =~ /$self->{"mre_open_paren"}/cg
$want & 4 $string =~ /$self->{"mre_open_paren"}/cg
Truth table100%3/3
A and B
A= $want & 4B= $string =~ /$self->{"mre_open_paren"}/cg
ABresult
0X0
100
111
338 14 $cb->{'open_paren'}->( $1 );
339 14 $depth++;
340 14 $last = OPEN_PAREN;
341 14 $want = OPERAND | OPEN_PAREN;
342 }
343 ▶ elsif ( ($want & CLOSE_PAREN) && $string =~ /$self->{'mre_close_paren'}/gc ) {
Condition66%2/3
$want & 8 and $string =~ /$self->{"mre_close_paren"}/cg
!ll&&!rl&&r
81014
MC/DC50%1/2
$want & 8 and $string =~ /$self->{"mre_close_paren"}/cg
$want & 8 $string =~ /$self->{"mre_close_paren"}/cg
Truth table66%2/3
A and B
A= $want & 8B= $string =~ /$self->{"mre_close_paren"}/cg
ABresult
0X0
100
111
344 14 $cb->{'close_paren'}->( $1 );
345 14 $depth--;
346 14 $last = CLOSE_PAREN;
347 14 $want = OPERATOR;
348 14 ▶ $want |= $depth? CLOSE_PAREN : STOP;
Branch: 1 branch
BranchTrueFalseTotal
$depth ? : 0 14 14
349 }
350 ▶ elsif ( ($want & OPERAND ) && $string =~ /$self->{'mre_operand'}/gc ) {
Condition100%3/3
$want & 1 and $string =~ /$self->{"mre_operand"}/cg
!ll&&!rl&&r
31248
MC/DC100%2/2
$want & 1 and $string =~ /$self->{"mre_operand"}/cg
$want & 1 $string =~ /$self->{"mre_operand"}/cg
Truth table100%3/3
A and B
A= $want & 1B= $string =~ /$self->{"mre_operand"}/cg
ABresult
0X0
100
111
351 48 my $m = $1;
352 48 $m=~ s/\s+$//;
353 48 $cb->{'operand'}->( $m );
354 48 $last = OPERAND;
355 48 $want = OPERATOR;
356 48 ▶ $want |= $depth? CLOSE_PAREN : STOP;
Branch: 1 branch
BranchTrueFalseTotal
$depth ? : 15 33 48
357 }
358 ▶ elsif ( ($want & STOP) && $string =~ /\G\s*$/igc ) {
Condition33%1/3
$want & 16 and $string =~ /\G\s*$/cig
!ll&&!rl&&r
0033
MC/DC0%0/2
$want & 16 and $string =~ /\G\s*$/cig
$want & 16 $string =~ /\G\s*$/cig
Truth table33%1/3
A and B
A= $want & 16B= $string =~ /\G\s*$/cig
ABresult
0X0
100
111
359 33 $last = STOP;
360 33 last;
361 }
362 else {
363 0 last;
364 }
365 }
366  
367 33 ▶ if (!$last || !($want & $last)) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($last and $want & $last) 0 33 33
Condition33%1/3
$last and $want & $last
!ll&&!rl&&r
0033
MC/DC0%0/2
$last and $want & $last
$last $want & $last
Truth table33%1/3
A and B
A= $lastB= $want & $last
ABresult
0X0
100
111
368 0 my $tmp = substr( $string, 0, pos($string) );
369 0 $tmp .= '>>>here<<<'. substr($string, pos($string));
370 0 my $msg = "Incomplete or incorrect expression, expecting a ". $self->bitmask_to_string($want) ." in '$tmp'";
371 0 ▶ $cb->{'error'}? $cb->{'error'}->($msg): die $msg;
Branch: 1 branch
BranchTrueFalseTotal
$cb->{'error'} ? : 0 0 0
372 0 return;
373 }
374  
375 33 ▶ if ( $depth ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($depth) 0 33 33
376 0 my $msg = "Incomplete query, $depth paren(s) isn't closed in '$string'";
377 0 ▶ $cb->{'error'}? $cb->{'error'}->($msg): die $msg;
Branch: 1 branch
BranchTrueFalseTotal
$cb->{'error'} ? : 0 0 0
378 0 return;
379 }
380 }
381  
382 0 ▶sub bitmask_to_string {
Subroutine bitmask_to_string: not called CC=4 SCAR=30.0
Pod undocumented
383 0 my $self = shift;
384 0 my $mask = shift;
385  
386 0 my @res;
387 0 ▶ for( my $i = 0; $i < @tokens; $i++ ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < @tokens) 0 0 0
388 0 ▶ next unless $mask & (1<<$i);
Branch: 1 branch
BranchTrueFalseTotal
unless $mask & 1 << $i 0 0 0
389 0 push @res, $tokens[$i];
390 }
391  
392 0 my $tmp = join ', ', splice @res, 0, -1;
393 0 ▶ unshift @res, $tmp if $tmp;
Branch: 1 branch
BranchTrueFalseTotal
if $tmp 0 0 0
394 0 return join ' or ', @res;
395 }
396  
397 =head2 Quoting and dequoting
398  
399 This module supports quoting with single quote ' and double ",
400 literal quotes escaped with \.
401  
402 from L<Regexp::Common::delimited> with ' and " as delimiters.
403  
404 =head3 q, qq, fq and dq
405  
406 Four methods to work with quotes:
407  
408 =over 4
409  
410 =item q - quote a string with single quote character.
411  
412 =item qq - quote a string with double quote character.
413  
414 =item fq - quote with single if string has no single quote character, otherwisee use double quotes.
415  
416 =item dq - delete either single or double quotes from a string if it's quoted.
417  
418 =back
419  
420 All four works either in place or return result, for example:
421  
422 $parser->q($str); # inplace
423  
424 my $q = $parser->q($s); # $s is untouched
425  
426 =cut
427  
428 8 ▶sub q {
Subroutine q: called CC=2 SCAR=6.9
Pod documented
429 8 ▶ if ( defined wantarray ) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined wantarray) { } 4 4 8
430 4 my $s = $_[1];
431 4 $s =~ s/(?=['\\])/\\/g;
432 4 return "'$s'";
433 } else {
434 4 $_[1] =~ s/(?=['\\])/\\/g;
435 4 substr($_[1], 0, 0) = "'";
436 4 $_[1] .= "'";
437 4 return;
438 }
439 }
440  
441 8 ▶sub qq {
Subroutine qq: called CC=2 SCAR=6.9
Pod documented
442 8 ▶ if ( defined wantarray ) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined wantarray) { } 4 4 8
443 4 my $s = $_[1];
444 4 $s =~ s/(?=["\\])/\\/g;
445 4 return "\"$s\"";
446 } else {
447 4 $_[1] =~ s/(?=["\\])/\\/g;
448 4 substr($_[1], 0, 0) = '"';
449 4 $_[1] .= '"';
450 4 return;
451 }
452 }
453  
454 6 ▶sub fq {
Subroutine fq: called CC=4 SCAR=13.9
Pod documented
455 6 ▶ if ( index( $_[1], "'" ) >= 0 ) {
Branch: 1 branch
BranchTrueFalseTotal
if (index($_[1], q[']) != -1) { } 2 4 6
456 2 ▶ if ( defined wantarray ) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined wantarray) { } 1 1 2
457 1 my $s = $_[1];
458 1 $s =~ s/(?=["\\])/\\/g;
459 1 return "\"$s\"";
460 } else {
461 1 $_[1] =~ s/(?=["\\])/\\/g;
462 1 substr($_[1], 0, 0) = '"';
463 1 $_[1] .= '"';
464 1 return;
465 }
466 } else {
467 4 ▶ if ( defined wantarray ) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined wantarray) { } 2 2 4
468 2 my $s = $_[1];
469 2 $s =~ s/(?=\\)/\\/g;
470 2 return "'$s'";
471 } else {
472 2 $_[1] =~ s/(?=\\)/\\/g;
473 2 substr($_[1], 0, 0) = "'";
474 2 $_[1] .= "'";
475 2 return;
476 }
477 }
478 }
479  
480 22 ▶sub dq {
Subroutine dq: called CC=4 SCAR=14.1
Pod documented
481 22 ▶ return defined wantarray? $_[1] : ()
Branch: 2 branches
BranchTrueFalseTotal
unless $_[1] =~ /^$re_delim$/o 0 22 22
defined wantarray ? : 0 0 0
482 unless $_[1] =~ /^$re_delim$/o;
483  
484 22 ▶ if ( defined wantarray ) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined wantarray) { } 11 11 22
485 11 my $s = $_[1];
486 11 my $q = substr( $s, 0, 1, '' );
487 11 substr( $s, -1 ) = '';
488 11 $s =~ s/\\([$q\\])/$1/g;
489 11 return $s;
490 } else {
491 11 my $q = substr( $_[1], 0, 1, '' );
492 11 substr( $_[1], -1 ) = '';
493 11 $_[1] =~ s/\\([$q\\])/$1/g;
494 11 return;
495 }
496 }
497  
498 =head2 Tree evaluation and modification
499  
500 Several functions taking a tree of boolean expressions as returned by
501 L<as_array> method and evaluating or changing it using a callback.
502  
503 =head3 walk $tree $callbacks @rest
504  
505 A simple method for walking a $tree using four callbacks: open_paren,
506 close_paren, operand and operator. All callbacks are optional.
507  
508 Example:
509  
510 $parser->walk(
511 $tree,
512 {
513 open_paren => sub { ... },
514 close_paren => sub { ... },
515 ...
516 },
517 $some_context_argument, $another, ...
518 );
519  
520 Any additional arguments (@rest) are passed all the time into callbacks.
521  
522 =cut
523  
524 0 ▶sub walk {
Subroutine walk: not called CC=8 SCAR=42.8
Pod documented
525 0 my ($self, $tree, $cb, @rest) = @_;
526  
527 0 foreach my $entry ( @$tree ) {
528 0 ▶ if ( ref $entry eq 'ARRAY' ) {
Branch: 2 branches
BranchTrueFalseTotal
if (ref $entry eq 'ARRAY') { } 0 0 0
elsif (ref $entry) { } 0 0 0
529 0 ▶ $cb->{'open_paren'}->( @rest ) if $cb->{'open_paren'};
Branch: 1 branch
BranchTrueFalseTotal
if $cb->{"open_paren"} 0 0 0
530 0 $self->walk( $entry, $cb, @rest );
531 0 ▶ $cb->{'close_paren'}->( @rest ) if $cb->{'close_paren'};
Branch: 1 branch
BranchTrueFalseTotal
if $cb->{"close_paren"} 0 0 0
532 } elsif ( ref $entry ) {
533 0 ▶ $cb->{'operand'}->( $entry, @rest ) if $cb->{'operand'};
Branch: 1 branch
BranchTrueFalseTotal
if $cb->{"operand"} 0 0 0
534 } else {
535 0 ▶ $cb->{'operator'}->( $entry, @rest ) if $cb->{'operator'};
Branch: 1 branch
BranchTrueFalseTotal
if $cb->{"operator"} 0 0 0
536 }
537 }
538 }
539  
540 =head3 filter $tree $callback @rest
541  
542 Filters a $tree using provided $callback. The callback is called for each operand
543 in the tree and operand is left when it returns true value.
544  
545 Any additional arguments (@rest) are passed all the time into the callback.
546 See example below.
547  
548 Boolean operators (AND/OR) are skipped according to parens and left first rule,
549 for example:
550  
551 X OR Y AND Z -> X AND Z
552 X OR (Y AND Z) -> X OR Z
553 X OR Y AND Z -> Y AND Z
554 X OR (Y AND Z) -> Y AND Z
555 X OR Y AND Z -> X OR Y
556 X OR (Y AND Z) -> X OR Y
557  
558 Returns new sub-tree. Original tree is not changed, but operands in new tree
559 still refer to the same hashes in the original.
560  
561 Example:
562  
563 my $filter = sub {
564 my ($condition, $some) = @_;
565 return 1 if $condition->{'operand'} eq $some;
566 return 0;
567 };
568 my $new_tree = $parser->filter( $tree, $filter, $some );
569  
570 See also L<solve|/"solve $tree $callback @rest">
571  
572 =cut
573  
574 34 ▶sub filter {
Subroutine filter: called CC=15 SCAR=27.1
Pod documented
575 34 my ($self, $tree, $cb, @rest) = @_;
576  
577 34 my $skip_next = 0;
578  
579 34 my @res;
580 34 foreach my $entry ( @$tree ) {
581 114 ▶ $skip_next-- and next if $skip_next > 0;
Branch: 1 branch
BranchTrueFalseTotal
if $skip_next > 0 18 96 114
Condition60%3/5
$skip_next > 0 && ($skip_next-- && (next))
!ll&&!rl&&r
96180
$skip_next-- and next
!ll
018
MC/DC0%0/2
$skip_next > 0 && ($skip_next-- && (next))
$skip_next > 0 $skip_next--
Truth table33%1/3
A && B
A= $skip_next > 0B= $skip_next--
ABresult
0X0
100
111
582  
583 96 ▶ if ( ref $entry eq 'ARRAY' ) {
Branch: 2 branches
BranchTrueFalseTotal
if (ref $entry eq 'ARRAY') { } 8 88 96
elsif (ref $entry) { } 66 22 88
584 8 my $tmp = $self->filter( $entry, $cb, @rest );
585 8 ▶ $tmp = $tmp->[0] if @$tmp == 1;
Branch: 1 branch
BranchTrueFalseTotal
if @$tmp == 1 4 4 8
586 8 ▶ if ( !$tmp || (ref $tmp eq 'ARRAY' && !@$tmp) ) {
Branch: 1 branch
BranchTrueFalseTotal
if (not $tmp or ref $tmp eq 'ARRAY' and not @$tmp) { } 2 6 8
Condition83%5/6
not $tmp or ref $tmp eq "ARRAY" and not @$tmp
l!l&&r!l&&!r
026
ref $tmp eq "ARRAY" and not @$tmp
!ll&&!rl&&r
422
MC/DC66%2/3
not $tmp or ref $tmp eq "ARRAY" and not @$tmp
not $tmp ref $tmp eq "ARRAY" not @$tmp
Truth table75%3/4
not(A) or B and not(C)
A= not $tmpB= ref $tmp eq "ARRAY"C= not @$tmp
ABCresult
1XX1
0111
00X0
0100
587 2 pop @res;
588 2 ▶ $skip_next++ unless @res;
Branch: 1 branch
BranchTrueFalseTotal
unless @res 1 1 2
589 } else {
590 6 push @res, $tmp;
591 }
592 } elsif ( ref $entry ) {
593 66 ▶ if ( $cb->( $entry, @rest ) ) {
Branch: 1 branch
BranchTrueFalseTotal
if (&$cb($entry, @rest)) { } 33 33 66
594 33 push @res, $entry;
595 } else {
596 33 pop @res;
597 33 ▶ $skip_next++ unless @res;
Branch: 1 branch
BranchTrueFalseTotal
unless @res 24 9 33
598 }
599 } else {
600 22 push @res, $entry;
601 }
602 }
603 34 ▶ return $res[0] if @res == 1 && ref $res[0] eq 'ARRAY';
Branch: 1 branch
BranchTrueFalseTotal
if @res == 1 and ref $res[0] eq "ARRAY" 1 33 34
Condition100%3/3
@res == 1 and ref $res[0] eq "ARRAY"
!ll&&!rl&&r
18151
MC/DC100%2/2
@res == 1 and ref $res[0] eq "ARRAY"
@res == 1 ref $res[0] eq "ARRAY"
Truth table100%3/3
A and B
A= @res == 1B= ref $res[0] eq "ARRAY"
ABresult
0X0
100
111
604 33 return \@res;
605 }
606  
607 =head3 solve $tree $callback @rest
608  
609 Solves a boolean expression represented by a $tree using provided $callback.
610 The callback is called for operands and should return a boolean value
611 (0 or 1 will work).
612  
613 Any additional arguments (@rest) are passed all the time into the callback.
614 See example below.
615  
616 Functions matrixes:
617  
618 A B AND OR
619 0 0 0 0
620 0 1 0 1
621 1 0 0 1
622 1 1 1 1
623  
624 Whole branches of the tree can be skipped when result is obvious, for example:
625  
626 1 OR (...)
627 0 AND (...)
628  
629 Returns result of the expression.
630  
631 Example:
632  
633 my $solver = sub {
634 my ($condition, $some) = @_;
635 return 1 if $condition->{'operand'} eq $some;
636 return 0;
637 };
638 my $result = $parser->solve( $tree, $filter, $some );
639  
640 See also L<filter|/"filter $tree $callback @rest">.
641  
642 =cut
643  
644 50 ▶sub solve {
Subroutine solve: called CC=13 SCAR=25.7
Pod documented
645 50 my ($self, $tree, $cb, @rest) = @_;
646  
647 50 my ($res, $ea, $skip_next) = (0, $self->{'operators'}[1], 0);
648 50 foreach my $entry ( @$tree ) {
649 178 ▶ $skip_next-- and next if $skip_next > 0;
Branch: 1 branch
BranchTrueFalseTotal
if $skip_next > 0 28 150 178
Condition60%3/5
$skip_next > 0 && ($skip_next-- && (next))
!ll&&!rl&&r
150280
$skip_next-- and next
!ll
028
MC/DC0%0/2
$skip_next > 0 && ($skip_next-- && (next))
$skip_next > 0 $skip_next--
Truth table33%1/3
A && B
A= $skip_next > 0B= $skip_next--
ABresult
0X0
100
111
650 150 ▶ unless ( ref $entry ) {
Branch: 1 branch
BranchTrueFalseTotal
unless (ref $entry) 64 86 150
651 64 $ea = lc $entry;
652 $skip_next++ if
653 ( $res && $ea eq $self->{'operators'}[1])
654 64 ▶ || (!$res && $ea eq $self->{'operators'}[0]);
Branch: 1 branch
BranchTrueFalseTotal
if $res and $ea eq $self->{"operators"}[1] or not $res and $ea eq $self->{"operators"}[0] 28 36 64
Condition100%9/9
$res and $ea eq $self->{"operators"}[1] or not $res and $ea eq $self->{"operators"}[0]
l!l&&r!l&&!r
141436
$res and $ea eq $self->{"operators"}[1]
!ll&&!rl&&r
321814
not $res and $ea eq $self->{"operators"}[0]
!ll&&!rl&&r
181814
MC/DC75%3/4
$res and $ea eq $self->{"operators"}[1] or not $res and $ea eq $self->{"operators"}[0]
$res $ea eq $self->{"operators"}[1] not $res $ea eq $self->{"operators"}[0]
Truth table57%4/7
A and B or not(C) and D
A= $resB= $ea eq $self->{"operators"}[1]C= not $resD= $ea eq $self->{"operators"}[0]
ABCDresult
11XX1
0X111
10111
0X0X0
0X100
100X0
10100
655 64 next;
656 }
657  
658 86 my $cur;
659 86 ▶ if ( ref $entry eq 'ARRAY' ) {
Branch: 1 branch
BranchTrueFalseTotal
if (ref $entry eq 'ARRAY') { } 8 78 86
660 8 $cur = $self->solve( $entry, $cb, @rest );
661 } else {
662 78 $cur = $cb->( $entry, @rest );
663 }
664 86 ▶ if ( $ea eq $self->{'operators'}[1] ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($ea eq $self->{'operators'}[1]) { } 68 18 86
665 68 ▶ $res ||= $cur;
Condition66%2/3
$res ||= $cur
l!l&&r!l&&!r
03335
MC/DC50%1/2
$res ||= $cur
$res $cur
Truth table66%2/3
A ||= B
A= $resB= $cur
ABresult
1X1
011
000
666 } else {
667 18 ▶ $res &&= $cur;
Condition66%2/3
$res &&= $cur
!ll&&!rl&&r
0810
MC/DC50%1/2
$res &&= $cur
$res $cur
Truth table66%2/3
A &&= B
A= $resB= $cur
ABresult
0X0
100
111
668 }
669 }
670 50 return $res;
671 }
672  
673 =head3 fsolve $tree $callback @rest
674  
675 Does in filter+solve in one go. Callback can return undef to filter out an operand,
676 and a defined boolean value to be used in solve.
677  
678 Any additional arguments (@rest) are passed all the time into the callback.
679  
680 Returns boolean result of the equation or undef if all operands have been filtered.
681  
682 See also L<filter|/"filter $tree $callback @rest"> and L<solve|/"solve $tree $callback @rest">.
683  
684 =cut
685  
686 40 ▶sub fsolve {
Subroutine fsolve: called CC=16 SCAR=27.9
Pod documented
687 40 my ($self, $tree, $cb, @rest) = @_;
688  
689 40 my ($res, $ea, $skip_next) = (undef, $self->{'operators'}[1], 0);
690 40 foreach my $entry ( @$tree ) {
691 154 ▶ $skip_next-- and next if $skip_next > 0;
Branch: 1 branch
BranchTrueFalseTotal
if $skip_next > 0 30 124 154
Condition60%3/5
$skip_next > 0 && ($skip_next-- && (next))
!ll&&!rl&&r
124300
$skip_next-- and next
!ll
030
MC/DC0%0/2
$skip_next > 0 && ($skip_next-- && (next))
$skip_next > 0 $skip_next--
Truth table33%1/3
A && B
A= $skip_next > 0B= $skip_next--
ABresult
0X0
100
111
692 124 ▶ unless ( ref $entry ) {
Branch: 1 branch
BranchTrueFalseTotal
unless (ref $entry) 48 76 124
693 48 $ea = lc $entry;
694 $skip_next++ if
695 ( $res && $ea eq $self->{'operators'}[1])
696 48 ▶ || (!$res && $ea eq $self->{'operators'}[0]);
Branch: 1 branch
BranchTrueFalseTotal
if $res and $ea eq $self->{"operators"}[1] or not $res and $ea eq $self->{"operators"}[0] 21 27 48
Condition100%9/9
$res and $ea eq $self->{"operators"}[1] or not $res and $ea eq $self->{"operators"}[0]
l!l&&r!l&&!r
101127
$res and $ea eq $self->{"operators"}[1]
!ll&&!rl&&r
271110
not $res and $ea eq $self->{"operators"}[0]
!ll&&!rl&&r
111611
MC/DC75%3/4
$res and $ea eq $self->{"operators"}[1] or not $res and $ea eq $self->{"operators"}[0]
$res $ea eq $self->{"operators"}[1] not $res $ea eq $self->{"operators"}[0]
Truth table57%4/7
A and B or not(C) and D
A= $resB= $ea eq $self->{"operators"}[1]C= not $resD= $ea eq $self->{"operators"}[0]
ABCDresult
11XX1
0X111
10111
0X0X0
0X100
100X0
10100
697 48 next;
698 }
699  
700 76 my $cur;
701 76 ▶ if ( ref $entry eq 'ARRAY' ) {
Branch: 1 branch
BranchTrueFalseTotal
if (ref $entry eq 'ARRAY') { } 0 76 76
702 0 $cur = $self->fsolve( $entry, $cb, @rest );
703 } else {
704 76 $cur = $cb->( $entry, @rest );
705 }
706 76 ▶ if ( defined $cur ) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $cur) { } 58 18 76
707 58 ▶ $res ||= 0;
Condition100%2/2
$res ||= 0
l!l
850
MC/DC100%1/1
$res ||= 0
$res
Truth table100%2/2
A
A= $res
Aresult
11
00
708 58 ▶ if ( $ea eq $self->{'operators'}[1] ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($ea eq $self->{'operators'}[1]) { } 50 8 58
709 50 ▶ $res ||= $cur;
Condition66%2/3
$res ||= $cur
l!l&&r!l&&!r
02525
MC/DC50%1/2
$res ||= $cur
$res $cur
Truth table66%2/3
A ||= B
A= $resB= $cur
ABresult
1X1
011
000
710 } else {
711 8 ▶ $res &&= $cur;
Condition66%2/3
$res &&= $cur
!ll&&!rl&&r
044
MC/DC50%1/2
$res &&= $cur
$res $cur
Truth table66%2/3
A &&= B
A= $resB= $cur
ABresult
0X0
100
111
712 }
713 } else {
714 18 ▶ $skip_next++ unless defined $res;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $res 11 7 18
715 }
716 }
717 40 return $res;
718 }
719  
720 =head3 partial_solve $tree $callback @rest
721  
722 Partially solve a $tree. Callback can return undef or a new expression
723 and a defined boolean value to be used in solve.
724  
725 Returns either result or array reference with expression.
726  
727 Any additional arguments (@rest) are passed all the time into the callback.
728  
729 =cut
730  
731 19 ▶sub partial_solve {
Subroutine partial_solve: called CC=20 SCAR=30.7
Pod documented
732 19 my ($self, $tree, $cb, @rest) = @_;
733  
734 19 my @res;
735  
736 19 my ($last, $ea, $skip_next) = (0, $self->{'operators'}[1], 0);
737 19 foreach my $entry ( @$tree ) {
738 51 ▶ $skip_next-- and next if $skip_next > 0;
Branch: 1 branch
BranchTrueFalseTotal
if $skip_next > 0 4 47 51
Condition60%3/5
$skip_next > 0 && ($skip_next-- && (next))
!ll&&!rl&&r
4740
$skip_next-- and next
!ll
04
MC/DC0%0/2
$skip_next > 0 && ($skip_next-- && (next))
$skip_next > 0 $skip_next--
Truth table33%1/3
A && B
A= $skip_next > 0B= $skip_next--
ABresult
0X0
100
111
739 47 ▶ unless ( ref $entry ) {
Branch: 1 branch
BranchTrueFalseTotal
unless (ref $entry) 16 31 47
740 16 $ea = lc $entry;
741 16 ▶ unless ( ref $last ) {
Branch: 1 branch
BranchTrueFalseTotal
if (ref $last) { } 8 8 16
742 $skip_next++ if
743 ( $last && $ea eq $self->{'operators'}[1])
744 8 ▶ || (!$last && $ea eq $self->{'operators'}[0]);
Branch: 1 branch
BranchTrueFalseTotal
if $last and $ea eq $self->{"operators"}[1] or not $last and $ea eq $self->{"operators"}[0] 4 4 8
Condition100%9/9
$last and $ea eq $self->{"operators"}[1] or not $last and $ea eq $self->{"operators"}[0]
l!l&&r!l&&!r
224
$last and $ea eq $self->{"operators"}[1]
!ll&&!rl&&r
422
not $last and $ea eq $self->{"operators"}[0]
!ll&&!rl&&r
222
MC/DC75%3/4
$last and $ea eq $self->{"operators"}[1] or not $last and $ea eq $self->{"operators"}[0]
$last $ea eq $self->{"operators"}[1] not $last $ea eq $self->{"operators"}[0]
Truth table57%4/7
A and B or not(C) and D
A= $lastB= $ea eq $self->{"operators"}[1]C= not $lastD= $ea eq $self->{"operators"}[0]
ABCDresult
11XX1
0X111
10111
0X0X0
0X100
100X0
10100
745 } else {
746 8 push @res, $entry;
747 }
748 16 next;
749 }
750  
751 31 ▶ if ( ref $entry eq 'ARRAY' ) {
Branch: 1 branch
BranchTrueFalseTotal
if (ref $entry eq 'ARRAY') { } 0 31 31
752 0 $last = $self->solve( $entry, $cb, @rest );
753 # drop parens with one condition inside
754 0 ▶ $last = $last->[0] if ref $last && @$last == 1;
Branch: 1 branch
BranchTrueFalseTotal
if ref $last and @$last == 1 0 0 0
Condition0%0/3
ref $last and @$last == 1
!ll&&!rl&&r
000
MC/DC0%0/2
ref $last and @$last == 1
ref $last @$last == 1
Truth table0%0/3
A and B
A= ref $lastB= @$last == 1
ABresult
0X0
100
111
755 } else {
756 31 $last = $cb->( $entry, @rest );
757 31 ▶ $last = $entry unless defined $last;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $last 13 18 31
758 }
759 31 ▶ unless ( ref $last ) {
Branch: 1 branch
BranchTrueFalseTotal
if (ref $last) { } 13 18 31
760 18 ▶ if ( $ea eq $self->{'operators'}[0] ) {
Branch: 2 branches
BranchTrueFalseTotal
if ($ea eq $self->{'operators'}[0]) { } 4 14 18
elsif ($ea eq $self->{'operators'}[1]) { } 14 0 14
761 # (...) AND 0
762 4 ▶ unless ( $last ) { @res = () } else { pop @res };
Branch: 1 branch
BranchTrueFalseTotal
if ($last) { } 2 2 4
763 }
764 elsif ( $ea eq $self->{'operators'}[1] ) {
765 # (...) OR 1
766 14 ▶ if ( $last ) { @res = () } else { pop @res };
Branch: 1 branch
BranchTrueFalseTotal
if ($last) { } 7 7 14
767 }
768 } else {
769 13 push @res, $last;
770 }
771 }
772  
773 19 ▶ return $last unless @res; # solution
Branch: 1 branch
BranchTrueFalseTotal
unless @res 10 9 19
774 9 return \@res; # more than one condition
775 }
776  
777 10 1;
778  
779 =head1 ALTERNATIVES
780  
781 There are some alternative implementations available on the CPAN.
782  
783 =over 4
784  
785 =item L<Search::QueryParser> - similar purpose with several differences.
786  
787 =item Another?
788  
789 =back
790  
791 =head1 AUTHORS
792  
793 Ruslan Zakirov E<lt>ruz@cpan.orgE<gt>, Robert Spier E<lt>rspier@pobox.comE<gt>
794  
795 =head1 COPYRIGHT
796  
797 This program is free software; you can redistribute it and/or modify it under
798 the same terms as Perl itself.
799  
800 =cut
↑ Summary