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