ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/deliantra/server/lib/cf/match.pm
(Generate patch)

Comparing deliantra/server/lib/cf/match.pm (file contents):
Revision 1.8 by root, Sat Oct 10 19:11:50 2009 UTC vs.
Revision 1.22 by root, Sat Oct 24 11:45:40 2009 UTC

3cf::match - object matching language 3cf::match - object matching language
4 4
5=head1 DESCRIPTION 5=head1 DESCRIPTION
6 6
7This module implements a simple object matching language. It can be asked 7This module implements a simple object matching language. It can be asked
8to find any (boolean context), or all (list context), matching objects. 8to find any ("check for a match"), or all ("find all objects") matching
9objects.
9 10
10=head1 MATCH EXAMPLES 11=head1 MATCH EXAMPLES
11 12
12Match the object if it has a slaying field of C<key1>: 13Match the object if it has a slaying field of C<key1>:
13 14
24 25
25Find all potions with spell objects inside them in someones inventory: 26Find all potions with spell objects inside them in someones inventory:
26 27
27 type=SPELL in type=POTION in inv 28 type=SPELL in type=POTION in inv
28 29
29Find all potions inside someones inventory, or inside applied containers: 30Find all scrolls inside someones inventory, or inside applied scroll
31containers:
30 32
31 type=POTION also in type=CONTAINER and applied in inv 33 type=SCROLL also in applied type=CONTAINER race="scroll" in inv
32 34
33=head1 LANGUAGE 35Find all unpaid items, anywhere, even deeply nested inside other items, in
36the originator:
34 37
35 # object selection 38 unpaid also deep in inv of originator
36 39
37 select = set 40=head1 MATCH EXPRESSIONS
38 | select also rep 'in' set
39 also = nothing | 'also'
40 rep = nothing | 'rep' | 'repeatedly'
41
42 set = 'inv' | 'env' | 'map'
43
44 empty =
45
46 # object matching
47
48 match = factor
49 | factor 'and'? match
50 | factor 'or' match
51
52 factor = 'not' factor
53 | '(' match ')'
54 | expr
55 | expr operator constant
56
57 operator = '=' | '==' | '!=' | '<' | '<=' | '>' | '>='
58
59 expr = flag
60 | sattr
61 | aattr '[' <constant> ']'
62 | special
63 | func '(' args ')'
64 | '{' perl code block '}'
65
66 func = <any function name>
67 sattr = <any scalar object attribute>
68 aattr = <any array object attribute>
69 flag = <any object flag>
70 special = <any ()-less "function">
71
72 constant = <number> | '"' <string> '"' | <uppercase cf::XXX name>
73 args = <depends on function>
74
75 TODO: repeatedly, env, contains, possbly matches
76 41
77=head2 STRUCTURE 42=head2 STRUCTURE
78 43
79The two main structures are the C<select>, which selects objects matching 44The two main structures are the C<match>, which selects objects matching
80various criteria, and the C<match>, which determines if an object matches 45various criteria, and the C<condition, which determines if an object
81some desired properties. 46matches some desired properties:
82 47
48 condition
49 condition in set-modifier
50 condition of root-object
51
83A C<select> is passed a set of "context objects" that it is applied 52A C<condition> receives a set of "context objects" that it is applied
84to. This is initially just one object - for altars, it is the object 53to. This is initially just one object - by default, for altars, it is the
85dropped on it, for pedestals, the object on top of it and so on. 54object dropped on it, for pedestals, the object on top of it and so on.
86 55
87This set of context objects can be modified in various ways, for example 56This set of context objects can be modified in various ways, for example
88by replacing it with the inventories of all objects, or all objects on the 57by replacing it with the inventories of all objects, or all items on the
89same mapspace, and so on, by using the C<in> operator. 58same mapspace, and so on, by using the C<in> operator:
90 59
60 condition in inv
61 condition in map
62
63Also, besides the default root object where all this begins, you can start
64elsewhere, for example in the I<originator> (usually the player):
65
66 condition in inv of originator
67
91Once the set of context objects has been established, each object is 68Once the final set of context objects has been established, each object
92matched against the C<match> expression. Sometimes the server is only 69is matched against the C<condition>.
93interested in knowing whether I<anything> matches, and sometimes the 70
94server is interested in I<all> objects that match. 71It is possible to chain modifiers from right-to-left, so this example
72would start with the originator, take it's inventory, find all inventory
73items which are potions, looks into their inventory, and then finds all
74spells.
75
76 type=SPELL in type=POTION in inv of originator
77
78Sometimes the server is only interested in knowing whether I<anything>
79matches, and sometimes the server is interested in I<all> objects that
80match.
95 81
96=head2 OPERATORS 82=head2 OPERATORS
97 83
98=over 4 84=over 4
99 85
100=item and, or, not, () 86=item and, or, not, ()
101 87
102Match expressions can be combined with C<and> or C<or> to build larger 88Conditions can be combined with C<and> or C<or> to build larger
103expressions. C<not> negates the expression, and parentheses can be used to 89expressions. C<not> negates the condition, and parentheses can be used to
104group match expressions. 90override operator precedence and execute submatches.
91
92Not that C<not> only negates a condition and not the whole match
93expressions, thus
94
95 not applied in inv
96
97is true if there is I<any> non-object in the inventory. To negate a whole
98match, you have to use a sub-match. To check whether there is I<no>
99applied object in someones inventory, write this:
100
101 not (applied in inv)
105 102
106Example: match applied weapons. 103Example: match applied weapons.
107 104
108 type=WEAPON and applied 105 applied type=WEAPON
109 106
110Example: match horns or rods. 107Example: match horns or rods.
111 108
112 type=HORN or type=ROD 109 type=HORN or type=ROD
113 110
131 128
132=item in env 129=item in env
133 130
134Replaces all objects by their containing object, if they have one. 131Replaces all objects by their containing object, if they have one.
135 132
133=item in arch
134
135Replaces all objects by their archetypes.
136
136=item in map 137=item in map
137 138
138Replaces all objects by the objects that are on the same mapspace as them. 139Replaces all objects by the objects that are on the same mapspace as them.
139 140
140=item in <match> 141=item in head
141 142
143Replaces all objects by their head objects.
144
145=item in <condition>
146
142Finds all context objects matching the match expression, and then puts 147Finds all context objects matching the condition, and then puts their
143their inventories into the context set. 148inventories into the context set.
144 149
145Note that C<in inv> is simply a special case of an C<< in <match> >> that 150Note that C<in inv> is simply a special case of an C<< in <condition> >> that
146matches any object. 151matches any object.
147 152
148Example: find all spells inside potions inside the inventory of the context 153Example: find all spells inside potions inside the inventory of the context
149object(s). 154object(s).
150 155
157 162
158Example: check if the context object I<is> a spell, or I<contains> a spell. 163Example: check if the context object I<is> a spell, or I<contains> a spell.
159 164
160 type=SPELL also in inv 165 type=SPELL also in inv
161 166
162=item repeatedly in ... 167=item also deep in ...
163 168
164Repeats the operation as many times as possible. This can be used to 169Repeats the operation as many times as possible. This can be used to
165recursively look into objects. 170recursively look into objects.
166 171
167=item also repeatedly in ... 172So for example, C<also deep in inv> means to take the inventory of all
173objects, taking their inventories, and so on, and adding all these objects
174to the context set.
168 175
169C<also> and C<repeatedly> can be combined. 176Similarly, C<also deep in env> means to take the environment object, their
177environemnt object and so on.
170 178
171Example: check if there are any unpaid items in an inventory, 179Example: check if there are any unpaid items in an inventory,
172or in the inventories of the inventory objects, and so on. 180or in the inventories of the inventory objects, and so on.
173 181
174 unpaid also repeatedly in inv 182 unpaid also deep in inv
175 183
176Example: check if a object is inside a player. 184Example: check if a object is inside a player.
177 185
178 type=PLAYER also repeatedly in env 186 type=PLAYER also deep in env
179 187
180=back 188=back
181 189
190=item of ...
191
192By default, all matches are applied to the "obviously appropriate" object,
193such as the item dropped on a button or moving over a detector. This can
194be changed to a number of other objects - not all of them are available
195for each match (when not available, the match will simply fail).
196
197An C<of> term ends a match, nothing is allowed to follow.
198
199=over 4
200
201=item of object
202
203Starts with the default object - this is the object passed to the match to
204match against by default. Matches have an explicit C<of object> appended,
205but submatches start at the current object, and in this case C<of object>
206can be used to start at the original object once more.
207
208=item of source
209
210Starts with the I<source> object - this object is sometimes passed to
211matches and represents the object that is the source of the action, such
212as a rod or a potion when it is applied. Often, the I<source> is the same
213as the I<originator>.
214
215=item of originator
216
217Starts with the I<originator> - one step farther removed than the
218I<source>, the I<originator> is sometimes passed to matches and represents
219the original initiator of an action, most commonly a player or monster.
220
221This object is often identical to the I<source> (e.g. when a player casts
222a spell, the player is both source and originator).
223
224=item of self
225
226Starts with the object initiating/asking for the match - this is basically
227always the object that the match expression is attached to.
228
182=back 229=back
183 230
184=head2 EXPRESSIONS 231=head2 EXPRESSIONS
185 232
186Match expressions usually consist of simple boolean checks (flag XYZ is 233Expressions used in conditions usually consist of simple boolean checks
187set) or simple comparisons. 234(flag XYZ is set) or simple comparisons.
188 235
189=over 4 236=over 4
190 237
191=item flags 238=item flags
192 239
216=item { BLOCK } 263=item { BLOCK }
217 264
218You can specify perl code to execute by putting it inside curly 265You can specify perl code to execute by putting it inside curly
219braces. The last expression evaluated inside will become the result. 266braces. The last expression evaluated inside will become the result.
220 267
268The perlcode can access C<$_>, which rferes to the object currently being
269matches, and the C<$object>, C<$self>, C<$source> and C<$originator>.
270
271Example: check whether the slaying field consists of digits only.
272
273 { $_->slaying =~ /^\d+$/ }
274
221=item comparisons, <, <=, ==, =, !=, =>, > 275=item comparisons, <, <=, ==, =, !=, =>, >
222 276
223You can compare expressions against constants via any of these 277You can compare expressions against constants via any of these
224operators. If the constant is a string, then a string compare will be 278operators. If the constant is a string, then a string compare will be
225done, otherwise a numerical comparison is used. 279done, otherwise a numerical comparison is used.
247=item any 301=item any
248 302
249This simply evaluates to true, and simply makes matching I<any> object a 303This simply evaluates to true, and simply makes matching I<any> object a
250bit easier to read. 304bit easier to read.
251 305
252=item has(match) 306=item none
307
308This simply evaluates to false, and simply makes matching I<never> a bit
309easier to read.
310
311=item has(condition)
253 312
254True iff the object has a matching inventory object. 313True iff the object has a matching inventory object.
255 314
256=item count(select) 315=item count(match)
257 316
258Number of matching objects - the context object for the C<select> are the 317Number of matching objects - the context object for the C<match> is the
259original context objects for the overall C<select>. # TODO bullshit 318currently tested object - you can override this with an C<in object> for
319example.
320
321=item dump()
322
323Dumps the object to the server log when executed, and evaluates to true.
324
325Note that logical operations are short-circuiting, so this only dumps
326potions:
327
328 type=POTION and dump()
260 329
261=back 330=back
262 331
332=head2 GRAMMAR
333
334This is the grammar that was used to implement the matching language
335module. It is meant to be easily readable by humans, not to implement it
336exactly as-is.
337
338 # object matching and selecting
339
340 match = chain
341 | chain 'of' root
342 root = 'object' | 'self' | 'source' | 'originator'
343 chain = condition
344 | chain also deep 'in' modifier
345 also = nothing | 'also'
346 deep = nothing | 'deep'
347 modifier ='inv' | 'env' | 'arch' | 'map' | 'head'
348
349 nothing =
350
351 # boolean matching condition
352
353 condition = factor
354 | factor 'and'? condition
355 | factor 'or' condition
356
357 factor = 'not' factor
358 | '(' match ')'
359 | expr
360 | expr operator constant
361
362 operator = '=' | '==' | '!=' | '<' | '<=' | '>' | '>='
363
364 expr = flag
365 | sattr
366 | aattr '[' <constant> ']'
367 | 'stat.' statattr
368 | special
369 | func '(' args ')'
370 | '{' perl code block '}'
371
372 func = <any function name>
373 sattr = <any scalar object attribute>
374 aattr = <any array object attribute>
375 flag = <any object flag>
376 statattr = <any stat attribute: exp, food, str, dex, hp, maxhp...>
377 special = <any ()-less "function">
378
379 constant = <number> | '"' <string> '"' | <uppercase cf::XXX name>
380 args = <depends on function>
381
382 TODO: contains, matches, query_name, selling_price, buying_price?
383
263=cut 384=cut
264 385
386=head2 PERL FUNCTIONS
387
388=over 4
389
390=cut
265 391
266package cf::match; 392package cf::match;
267 393
268use common::sense; 394use common::sense;
269 395
270use List::Util (); 396use List::Util ();
271
272# parser state
273# $_ # string to be parsed
274our $all; # find all, or just the first matching object
275 397
276{ 398{
277 package cf::match::exec; 399 package cf::match::exec;
278 400
279 use List::Util qw(first); 401 use List::Util qw(first);
280
281 sub env_chain {
282 my @res;
283 push @res, $_
284 while $_ = $_->env;
285 @res
286 }
287 402
288 package cf::match::parser; 403 package cf::match::parser;
289 404
290 use common::sense; 405 use common::sense;
291 406
292 sub ws { 407 sub ws {
293 /\G\s+/gc; 408 /\G\s+/gc;
294 } 409 }
295 410
411 sub condition ();
412 sub match ($$);
413
296 our %func = ( 414 our %func = (
297 has => sub { 415 has => sub {
298 'first { ' . &match . ' } $_->inv' 416 'first { ' . condition . ' } $_->inv'
299 }, 417 },
300 count => sub { 418 count => sub {
301 local $all = 1; 419 '(scalar ' . (match 1, '$_') . ')'
302 '(scalar ' . &select . ')' 420 },
421 dump => sub {
422 'do {
423 warn "cf::match::match dump:\n"
424 . "self: " . eval { $self->name } . "\n"
425 . $_->as_string;
426 1
427 }';
303 }, 428 },
304 ); 429 );
305 430
306 our %special = ( 431 our %special = (
307 any => sub { 432 any => sub {
308 1 433 1
309 }, 434 },
435 none => sub {
436 0
437 },
310 ); 438 );
311 439
312 sub constant { 440 sub constant {
313 ws; 441 ws;
314 442
322 } 450 }
323 451
324 our $flag = $cf::REFLECT{object}{flags}; 452 our $flag = $cf::REFLECT{object}{flags};
325 our $sattr = $cf::REFLECT{object}{scalars}; 453 our $sattr = $cf::REFLECT{object}{scalars};
326 our $aattr = $cf::REFLECT{object}{arrays}; 454 our $aattr = $cf::REFLECT{object}{arrays};
455 our $lattr = $cf::REFLECT{living}{scalars};
327 456
328 sub expr { 457 sub expr {
329 # ws done by factor 458 # ws done by factor
330 my $res; 459 my $res;
331 460
334 463
335 my $expr = $1; 464 my $expr = $1;
336 465
337 $res .= $expr =~ /\{([^;]+)\}/ ? $1 : "do $expr"; 466 $res .= $expr =~ /\{([^;]+)\}/ ? $1 : "do $expr";
338 467
468 } elsif (/\Gstats\.([A-Za-z0-9_]+)/gc) {
469
470 if (exists $lattr->{$1}) {
471 $res .= "\$_->stats->$1";
472 } elsif (exists $lattr->{"\u$1"}) {
473 $res .= "\$_->stats->\u$1";
474 } else {
475 die "living statistic name expected (str, pow, hp, sp...)\n";
476 }
477
339 } elsif (/\G([A-Za-z0-9_]+)/gc) { 478 } elsif (/\G([A-Za-z0-9_]+)/gc) {
340 479
341 if (my $func = $func{$1}) { 480 if (my $func = $func{$1}) {
342 /\G\s*\(/gc 481 /\G\s*\(/gc
343 or die "'(' expected after function name\n"; 482 or die "'(' expected after function name\n";
371 } else { 510 } else {
372 $res .= constant; 511 $res .= constant;
373 } 512 }
374 513
375 } else { 514 } else {
515 Carp::cluck;#d#
376 die "expr expected\n"; 516 die "expr expected\n";
377 } 517 }
378 518
379 $res 519 $res
380 } 520 }
397 $res .= "!"; 537 $res .= "!";
398 } 538 }
399 539
400 if (/\G\(/gc) { 540 if (/\G\(/gc) {
401 # () 541 # ()
402 $res .= &match; 542
403 ws; 543 $res .= '(' . (match 0, '$_') . ')';
544
404 /\G\)/gc or die "')' expected\n"; 545 /\G\s*\)/gc or die "closing ')' expected\n";
405 546
406 } else { 547 } else {
407 my $expr = expr; 548 my $expr = expr;
408 549
409 $res .= $expr; 550 $res .= $expr;
420 } 561 }
421 562
422 "($res)" 563 "($res)"
423 } 564 }
424 565
425 sub match { 566 sub condition () {
426 my $res = factor; 567 my $res = factor;
427 568
428 while () { 569 while () {
429 ws; 570 ws;
571
572 # first check some stop-symbols, so we don't have to backtrack
430 if (/\G(?=also\b|in\b|\)|$)/gc) { 573 if (/\G(?=also\b|deep\b|in\b|of\b|\)|\z)/gc) {
431 # early stop => faster and requires no backtracking 574 pos = pos; # argh. the misop hits again. again. again. again. you die.
432 last; 575 last;
576
433 } elsif (/\Gor\b/gc) { 577 } elsif (/\Gor\b/gc) {
434 $res .= " || "; 578 $res .= " || ";
579
435 } else { 580 } else {
436 /\Gand\b/gc; 581 /\Gand\b/gc;
437 $res .= " && "; 582 $res .= " && ";
438 } 583 }
439 $res .= factor; 584 $res .= factor;
440 } 585 }
441 586
442 $res 587 $res
443 } 588 }
444 589
445 sub select { 590 sub match ($$) {
446 my $res; 591 my ($wantarray, $defctx) = @_;
447 592
448 my $also; # undef means first iteration 593 my $res = condition;
594
595 # if nothing follows, we have a simple condition, so
596 # optimise a comon case.
597 if ($defctx eq '$_' and /\G\s*(?=\)|$)/gc) {
598 return $wantarray
599 ? "$res ? \$_ : ()"
600 : $res;
601 }
602
603 $res = ($wantarray ? " grep { " : " first { ") . $res . "}";
604
449 while () { 605 while () {
606 ws;
607
608 my $also = /\Galso\s+/gc + 0;
609 my $deep = /\Gdeep\s+/gc + 0;
610
611 if (/\Gin\s+/gc) {
612 my $expand;
613
450 if (/\G\s*(inv|env|map)\b/gc) { 614 if (/\G(inv|env|map|arch|head)\b/gc) {
451 if ($1 eq "inv") { 615 if ($1 eq "inv") {
452 $res .= " map+(${also}\$_->inv),"; 616 $expand = "map \$_->inv,";
453 } elsif ($1 eq "env") { 617 } elsif ($1 eq "env") {
454 $res .= " map+(${also}env_chain), "; # TODO 618 $expand = "map \$_->env // (),";
619 } elsif ($1 eq "head") {
620 $expand = "map \$_->head,";
621 $deep = 0; # infinite loop otherwise
622 } elsif ($1 eq "arch") {
623 $expand = "map \$_->arch,";
624 $deep = 0; # infinite loop otherwise
455 } elsif ($1 eq "map") { 625 } elsif ($1 eq "map") {
456 $res .= " map+(${also}\$_->map->at (\$_->x, \$_->y)),"; 626 $expand = "map \$_->map->at (\$_->x, \$_->y),";
627 $deep = 0; # infinite loop otherwise
628 }
629 } else {
630 $expand = "map \$_->inv, grep { " . condition . " }";
457 } 631 }
458 last unless /\G\s*in\b/gc; 632
633 if ($also || $deep) {
634 $res .= " do {\n"
635 . " my \@res;\n";
636 $res .= " while (\@_) {\n" if $deep;
637 $res .= " push \@res, \@_;\n" if $also;
638 $res .= " \@_ = $expand \@_;\n";
639 $res .= " }\n" if $deep;
640 $res .= " (\@res, \@_)\n"
641 . "}";
642 } else {
643 $res .= " $expand";
644 }
459 } else { 645 } else {
460 $res .= " map+($also\$_->inv)," if defined $also;
461 $res .= $all ? " grep { " : " first {";
462 $res .= match;
463 $res .= "}";
464 646
465 $also = /\G\s*also\b/gc ? '$_, ' : ''; 647 if (/\Gof\s+(self|object|source|originator)\b/gc) {
466 last unless /\G\s*in\b/gc; 648 $also || $deep
649 and die "neither 'also' nor 'deep' can be used with 'of'\n";
650
651 if ($1 eq "self") {
652 return "$res \$self // ()";
653 } elsif ($1 eq "object") {
654 return "$res \$object";
655 } elsif ($1 eq "source") {
656 return "$res \$source // ()";
657 } elsif ($1 eq "originator") {
658 return "$res \$originator // \$source // ()";
659 }
660 } else {
661 return "$res $defctx";
662 }
467 } 663 }
468 } 664 }
469
470 "$res \@ctx"
471 } 665 }
472
473} 666}
474 667
475sub parse($;$) { 668sub parse($$) { # wantarray, matchexpr
476 local $_ = shift; 669 my $res;
477 local $all = shift;
478 670
479 my $res = cf::match::parser::select; 671 local $_ = $_[1];
672
673 eval {
674 $res = cf::match::parser::match $_[0], "\$object";
675
676 /\G$/gc
677 or die "unexpected trailing characters after match\n";
678 };
480 679
481 if ($@) { 680 if ($@) {
482 my $ctx = 20; 681 my $ctx = 20;
483 my $str = substr $_, (List::Util::max 0, (pos) - $ctx), $ctx * 2; 682 my $str = substr $_, (List::Util::max 0, (pos) - $ctx), $ctx * 2;
484 substr $str, (List::Util::min $ctx, pos), 0, "<-- HERE -->"; 683 substr $str, (List::Util::min $ctx, pos), 0, "<-- HERE -->";
488 } 687 }
489 688
490 $res 689 $res
491} 690}
492 691
493if (0) { 692if (0) {#d#
494 my $perl = parse '{ {1}}', 0; 693 die parse 1, 'stats.pow';
495
496 warn $perl, "\n";#d#
497 $perl = eval "package cf::match::exec; no warnings; no feature; our \@ctx; sub { $perl }"; die if $@;
498 use B::Deparse;
499 warn B::Deparse->new->coderef2text ($perl);
500 exit 0; 694 exit 0;
501} 695}
502 696
697our %CACHE;
698
699sub compile($$) {
700 my ($wantarray, $match) = @_;
701 my $expr = parse $wantarray, $match;
702 warn "MATCH DEBUG $match,$wantarray => $expr\n";#d#
703 $expr = eval "
704 package cf::match::exec;
705 sub {
706 my (\$object, \$self, \$source, \$originator) = \@_;
707 $expr
708 }
709 ";
710 die if $@;
711
712 $expr
713}
714
715=item cf::match::match $match, $object[, $self[, $source[, $originator]]]
716
717Compiles (and caches) the C<$match> expression and matches it against
718the C<$object>. C<$self> should be the object initiating the match (or
719C<undef>), C<$source> should be the actor/source and C<$originator> the
720object that initiated the action (such as the player). C<$originator>
721defaults to C<$source> when not given.
722
723In list context it finds and returns all matching objects, in scalar
724context only a true or false value.
725
726=cut
727
728sub match($$;$$$) {
729 my $match = shift;
730 my $wantarray = wantarray+0;
731
732 &{
733 $CACHE{"$wantarray$match"} ||= compile $wantarray, $match
734 }
735}
736
737our $CACHE_CLEARER = AE::timer 3600, 3600, sub {
738 %CACHE = ();
739};
740
741#d# $::schmorp=cf::player::find "schmorp"&
742#d# cf::match::match '', $::schmorp->ob
743
744
745=back
746
747=head1 AUTHOR
748
749 Marc Lehmann <schmorp@schmorp.de>
750 http://home.schmorp.de/
751
752=cut
753
5031; 7541;
504 755

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines