ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/cvsroot/cf.schmorp.de/server/lib/cf/match.pm
Revision: 1.19
Committed: Tue Oct 13 15:58:19 2009 UTC (17 years, 1 month ago) by root
Branch: MAIN
Changes since 1.18: +7 -0 lines
Log Message:
*** empty log message ***

File Contents

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