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.6 by root, Sat Oct 10 05:33:08 2009 UTC vs.
Revision 1.13 by root, Sun Oct 11 23:51:47 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. 71Sometimes the server is only interested in knowing whether I<anything>
72matches, and sometimes the server is interested in I<all> objects that
73match.
95 74
96=head2 OPERATORS 75=head2 OPERATORS
97 76
98=over 4 77=over 4
99 78
100=item and, or, not, () 79=item and, or, not, ()
101 80
102Match expressions can be combined with C<and> or C<or> to build larger 81Conditions can be combined with C<and> or C<or> to build larger
103expressions. C<not> negates the expression, and parentheses can be used to 82expressions. C<not> negates the expression, and parentheses can be used to
104group match expressions. 83group conditions.
105 84
106Example: match applied weapons. 85Example: match applied weapons.
107 86
108 type=WEAPON and applied 87 applied type=WEAPON
109 88
110Example: match horns or rods. 89Example: match horns or rods.
111 90
112 type=HORN or type=ROD 91 type=HORN or type=ROD
113 92
114=item in ... 93=item in ...
115 94
116The in operator takes the context set and modifies it in various ways. 95The in operator takes the context set and modifies it in various ways. As
96a less technical description, think of the C<in> as being a I<look into>
97or I<look at> operator - instead of looking at whatever was provided to
98the match, the C<in> operator lets you look at other sets of objects, most
99often the inventory.
117 100
118=over 4 101=over 4
119 102
120=item in inv 103=item in inv
121 104
131 114
132=item in map 115=item in map
133 116
134Replaces all objects by the objects that are on the same mapspace as them. 117Replaces all objects by the objects that are on the same mapspace as them.
135 118
136=item in <match> 119=item in <cond>
137 120
138Finds all context objects matching the match expression, and then puts 121Finds all context objects matching the condition, and then puts their
139their inventories into the context set. 122inventories into the context set.
140 123
141Note that C<in inv> is simply a special case of an C<< in <match> >> that 124Note that C<in inv> is simply a special case of an C<< in <cond> >> that
142matches any object. 125matches any object.
143 126
144Example: find all spells inside potions inside the inventory of the context 127Example: find all spells inside potions inside the inventory of the context
145object(s). 128object(s).
146 129
153 136
154Example: check if the context object I<is> a spell, or I<contains> a spell. 137Example: check if the context object I<is> a spell, or I<contains> a spell.
155 138
156 type=SPELL also in inv 139 type=SPELL also in inv
157 140
158=item repeatedly in ... 141=item deep in ...
159 142
160Repeats the operation as many times as possible. This can be used to 143Repeats the operation as many times as possible. This can be used to
161recursively look into objects. 144recursively look into objects.
162 145
163=item also repeatedly in ... 146=item also deep in ...
164 147
165C<also> and C<repeatedly> can be combined. 148C<also> and C<deep> can be combined.
166 149
167Example: check if there are any unpaid items in an inventory, 150Example: check if there are any unpaid items in an inventory,
168or in the inventories of the inventory objects, and so on. 151or in the inventories of the inventory objects, and so on.
169 152
170 unpaid also repeatedly in inv 153 unpaid also deep in inv
171 154
172Example: check if a object is inside a player. 155Example: check if a object is inside a player.
173 156
174 type=PLAYER also repeatedly in env 157 type=PLAYER also deep in env
175 158
176=back 159=back
177 160
161=item of ...
162
163By default, all matches are applied to the "obviously appropriate" object,
164such as the item dropped on a button or moving over a detector. This can
165be changed to a number of other objects - not all of them are available
166for each match (when not available, the match will simply fail).
167
168An C<of> term ends a match, nothing is allowed to follow.
169
170=over 4
171
172=item of object
173
174Starts with the default object - this is the object passed to the match to
175match against by default. Matches have an explicit C<of object> appended,
176but submatches start at the current object, and in this case C<of object>
177can be used to start at the original object once more.
178
179=item of source
180
181Starts with the I<source> object - this object is sometimes passed to
182matches and represents the object that is the source of the action, such
183as a rod or a potion when it is applied. Often, the I<source> is the same
184as the I<originator>.
185
186=item of originator
187
188Starts with the I<originator> - one step farther removed than the
189I<source>, the I<originator> is sometimes passed to matches and represents
190the original initiator of an action, most commonly a player or monster.
191
192This object is often identical to the I<source> (e.g. when a player casts
193a spell, the player is both source and originator).
194
195=item of self
196
197Starts with the object initiating/asking for the match - this is basically
198always the object that the match expression is attached to.
199
178=back 200=back
179 201
180=head2 EXPRESSIONS 202=head2 EXPRESSIONS
181 203
182Match expressions usually consist of simple boolean checks (flag XYZ is 204Expressions used in conditions usually consist of simple boolean checks
183set) or simple comparisons. 205(flag XYZ is set) or simple comparisons.
184 206
185=over 4 207=over 4
186 208
187=item flags 209=item flags
188 210
212=item { BLOCK } 234=item { BLOCK }
213 235
214You can specify perl code to execute by putting it inside curly 236You can specify perl code to execute by putting it inside curly
215braces. The last expression evaluated inside will become the result. 237braces. The last expression evaluated inside will become the result.
216 238
239The perlcode can access C<$_>, which rferes to the object currently being
240matches, and the C<$object>, C<$self>, C<$source> and C<$originator>.
241
242Example: check whether the slaying field consists of digits only.
243
244 { $_->slaying =~ /^\d+$/ }
245
217=item comparisons, <, <=, ==, =, !=, =>, > 246=item comparisons, <, <=, ==, =, !=, =>, >
218 247
219You can compare expressions against constants via any of these 248You can compare expressions against constants via any of these
220operators. If the constant is a string, then a string compare will be 249operators. If the constant is a string, then a string compare will be
221done, otherwise a numerical comparison is used. 250done, otherwise a numerical comparison is used.
243=item any 272=item any
244 273
245This simply evaluates to true, and simply makes matching I<any> object a 274This simply evaluates to true, and simply makes matching I<any> object a
246bit easier to read. 275bit easier to read.
247 276
248=item has(match) 277=item has(condition)
249 278
250True iff the object has a matching inventory object. 279True iff the object has a matching inventory object.
251 280
252=item count(select) 281=item count(match)
253 282
254Number of matching objects - the context object for the C<select> are the 283Number of matching objects - the context object for the C<match> is the
255original context objects for the overall C<select>. # TODO bullshit 284currently tested object - you can override this with an C<in object> for
285example.
286
287=item match(match)
288
289An independent match - semantics like C<count>, except it only matters
290whether the match finds any object (which is faster).
291
292=item dump
293
294Dumps the object to the server log when executed, and evaluates to true.
295
296Note that logical operations are short-circuiting, so this only dumps
297potions:
298
299 type=POTION and dump
256 300
257=back 301=back
258 302
303=head2 GRAMMAR
304
305This is the grammar that was used to implement the matching language
306module. It is meant to be easily readable by humans, not to implement it
307exactly as-is.
308
309 # object matching and selecting
310
311 match = chain
312 | chain 'of' root
313 root = 'object' | 'self' | 'source' | 'originator'
314 chain = condition
315 | chain also deep 'in' set
316 also = nothing | 'also'
317 deep = nothing | 'deep'
318 set = 'inv' | 'env' | 'map'
319
320 empty =
321
322 # boolean matching condition
323
324 condition = factor
325 | factor 'and'? cond
326 | factor 'or' cond
327
328 factor = 'not' factor
329 | '(' cond ')'
330 | expr
331 | expr operator constant
332
333 operator = '=' | '==' | '!=' | '<' | '<=' | '>' | '>='
334
335 expr = flag
336 | sattr
337 | aattr '[' <constant> ']'
338 | special
339 | func '(' args ')'
340 | '{' perl code block '}'
341
342 func = <any function name>
343 sattr = <any scalar object attribute>
344 aattr = <any array object attribute>
345 flag = <any object flag>
346 special = <any ()-less "function">
347
348 constant = <number> | '"' <string> '"' | <uppercase cf::XXX name>
349 args = <depends on function>
350
351 TODO: contains, matches, query_name, selling_price, buying_price?
352
259=cut 353=cut
260 354
355=head2 PERL FUNCTIONS
356
357=over 4
358
359=cut
261 360
262package cf::match; 361package cf::match;
263 362
264use common::sense; 363use common::sense;
265 364
270our $all; # find all, or just the first matching object 369our $all; # find all, or just the first matching object
271 370
272{ 371{
273 package cf::match::exec; 372 package cf::match::exec;
274 373
275 our @ctx; # root object(s)
276
277 use List::Util qw(first); 374 use List::Util qw(first);
278
279 sub env_chain {
280 my @res;
281 push @res, $_
282 while $_ = $_->env;
283 @res
284 }
285 375
286 package cf::match::parser; 376 package cf::match::parser;
287 377
288 use common::sense; 378 use common::sense;
289 379
291 /\G\s+/gc; 381 /\G\s+/gc;
292 } 382 }
293 383
294 our %func = ( 384 our %func = (
295 has => sub { 385 has => sub {
296 'first { ' . &match . ' } $_->inv' 386 'first { ' . &condition . ' } $_->inv'
297 }, 387 },
298 count => sub { 388 count => sub {
299 local $all = 1; 389 local $all = 1;
300 '(scalar ' . &select . ')' 390 '(scalar ' . &match ('$_') . ')'
391 },
392 match => sub {
393 local $all = 0;
394 '(scalar ' . &match ('$_') . ')'
301 }, 395 },
302 ); 396 );
303 397
304 our %special = ( 398 our %special = (
305 any => sub { 399 any => sub {
306 1 400 1
401 },
402 dump => sub {
403 'do {
404 warn "cf::match::match dump:\n"
405 . "self: " . eval { $self->name } . "\n"
406 . $_->as_string;
407 1
408 }';
307 }, 409 },
308 ); 410 );
309 411
310 sub constant { 412 sub constant {
311 ws; 413 ws;
395 $res .= "!"; 497 $res .= "!";
396 } 498 }
397 499
398 if (/\G\(/gc) { 500 if (/\G\(/gc) {
399 # () 501 # ()
400 $res .= &match; 502 $res .= &condition;
401 ws; 503 ws;
402 /\G\)/gc or die "')' expected\n"; 504 /\G\)/gc or die "')' expected\n";
403 505
404 } else { 506 } else {
405 my $expr = expr; 507 my $expr = expr;
418 } 520 }
419 521
420 "($res)" 522 "($res)"
421 } 523 }
422 524
423 sub match { 525 sub condition {
424 my $res = factor; 526 my $res = factor;
425 527
426 while () { 528 while () {
427 ws; 529 ws;
530
531 # first check some stop-symbols, so we don't have to backtrack
428 if (/\G(?=also\b|in\b|\)|$)/gc) { 532 if (/\G(?=also\b|deep\b|in\b|of\b\)|$)/gc) {
429 # early stop => faster and requires no backtracking
430 last; 533 last;
534
431 } elsif (/\Gor\b/gc) { 535 } elsif (/\Gor\b/gc) {
432 $res .= " || "; 536 $res .= " || ";
537
433 } else { 538 } else {
434 /\Gand\b/gc; 539 /\Gand\b/gc;
435 $res .= " && "; 540 $res .= " && ";
436 } 541 }
437 $res .= factor; 542 $res .= factor;
438 } 543 }
439 544
440 $res 545 $res
441 } 546 }
442 547
443 sub select { 548 sub match {
444 my $res; 549 my $default = shift;
445 550
446 my $also; # undef means first iteration 551 my $res = ($all ? " grep { " : " first {") . condition . " }";
552
447 while () { 553 while () {
554 ws;
555
556 my $also = /\Galso\s+/gc + 0;
557 my $deep = /\Gdeep\s+/gc + 0;
558
559 if (/\Gin\s+/gc) {
560 my $expand;
561
448 if (/\G\s*(inv|env|map)\b/gc) { 562 if (/\G(inv|env|map)\b/gc) {
449 if ($1 eq "inv") { 563 if ($1 eq "inv") {
450 $res .= " map+(${also}\$_->inv),"; 564 $expand = "map \$_->inv,";
451 } elsif ($1 eq "env") { 565 } elsif ($1 eq "env") {
452 $res .= " map+(${also}env_chain), "; # TODO 566 $expand = "map \$_->env // (),";
453 } elsif ($1 eq "map") { 567 } elsif ($1 eq "map") {
454 $res .= " map+(${also}\$_->map->at (\$_->x, \$_->y)),"; 568 $expand = "map \$_->map->at (\$_->x, \$_->y),";
569 }
570 } else {
571 $expand = "map \$_->inv, grep { " . condition . " }";
455 } 572 }
456 last unless /\G\s*in\b/gc; 573
574 if ($also || $deep) {
575 $res .= " do {\n"
576 . " my \@res;\n";
577 $res .= " while (\@_) {\n" if $deep;
578 $res .= " push \@res, \@_;\n" if $also;
579 $res .= " \@_ = $expand \@_;\n";
580 $res .= " }\n" if $deep;
581 $res .= " (\@res, \@_)\n"
582 . "}";
583 } else {
584 $res .= " $expand";
585 }
586 } elsif (/\Gof\s+(self|object|source|originator)\b/gc) {
587 $also || $deep
588 and die "neither 'also' nor 'deep' can be used with 'of'\n";
589
590 if ($1 eq "self") {
591 return "$res \$self // ()";
592 } elsif ($1 eq "object") {
593 return "$res \$object";
594 } elsif ($1 eq "source") {
595 return "$res \$source // ()";
596 } elsif ($1 eq "originator") {
597 return "$res \$originator // \$source // ()";
598 }
457 } else { 599 } else {
458 $res .= " map+($also\$_->inv)," if defined $also; 600 return "$res $default";
459 $res .= $all ? " grep { " : " first {";
460 $res .= match;
461 $res .= "}";
462
463 $also = /\G\s*also\b/gc ? '$_, ' : '';
464 last unless /\G\s*in\b/gc;
465 } 601 }
466 } 602 }
467
468 "$res \@ctx"
469 } 603 }
470
471} 604}
472 605
473sub parse($;$) { 606sub parse($;$) {
474 local $_ = shift; 607 local $_ = shift;
475 local $all = shift; 608 local $all = shift;
476 609
477 my $res = "package cf::match::exec;\n" 610 my $res;
478 . eval { cf::match::parser::select }; 611
612 eval {
613 $res = cf::match::parser::match "\$object";
614
615 /\G\s*$/gc
616 or die "unexpected trailing characters after match\n";
617 };
479 618
480 if ($@) { 619 if ($@) {
481 my $ctx = 20; 620 my $ctx = 20;
482 my $str = substr $_, (List::Util::max 0, (pos) - $ctx), $ctx * 2; 621 my $str = substr $_, (List::Util::max 0, (pos) - $ctx), $ctx * 2;
483 substr $str, (List::Util::min $ctx, pos), 0, "<-- HERE -->"; 622 substr $str, (List::Util::min $ctx, pos), 0, "<-- HERE -->";
487 } 626 }
488 627
489 $res 628 $res
490} 629}
491 630
492if (0) { 631if (0) {#d#
493 my $perl = parse '{ {1}}', 0; 632 die parse 'applied', 1;
494
495 warn $perl, "\n";#d#
496 $perl = eval "no warnings; no feature; sub { $perl }"; die if $@;
497 use B::Deparse;
498 warn B::Deparse->new->coderef2text ($perl);
499 exit 0; 633 exit 0;
500} 634}
501 635
636=item cf::match::match $match, $object[, $self[, $source[, $originator]]]
637
638Compiles (and caches) the C<$match> expression and matches it against
639the C<$object>. C<$self> should be the object initiating the match (or
640C<undef>), C<$source> should be the actor/source and C<$originator> the
641object that initiated the action (such as the player). C<$originator>
642defaults to C<$source> when not given.
643
644In list context it finds and returns all matching objects, in scalar
645context only a true or false value.
646
647=cut
648
649our %CACHE;
650
651sub compile($$) {
652 my ($match, $all) = @_;
653 my $expr = parse $match, $all;
654 warn "MATCH DEBUG $match,$all => $expr\n";#d#
655 $expr = eval "
656 package cf::match::exec;
657 sub {
658 my (\$object, \$self, \$source, \$originator) = \@_;
659 $expr
660 }
661 ";
662 die if $@;
663
664 $expr
665}
666
667sub match($$;$$$) {
668 my $match = shift;
669 my $all = wantarray+0;
670
671 &{
672 $CACHE{"$all$match"} ||= compile $match, $all
673 }
674}
675
676#d# $::schmorp=cf::player::find "schmorp"&
677#d# cf::match::match '', $::schmorp->ob
678
679
680=back
681
682=head1 AUTHOR
683
684 Marc Lehmann <schmorp@schmorp.de>
685 http://home.schmorp.de/
686
687=cut
688
5021; 6891;
503 690

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines