ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/cvsroot/cf.schmorp.de/server/lib/cf/match.pm
Revision: 1.29
Committed: Sat Aug 28 00:30:29 2010 UTC (16 years, 2 months ago) by root
Branch: MAIN
Changes since 1.28: +9 -3 lines
Log Message:
*** empty log message ***

File Contents

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