ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/cvsroot/cf.schmorp.de/server/lib/cf/match.pm
Revision: 1.9
Committed: Sun Oct 11 00:24:35 2009 UTC (17 years, 1 month ago) by root
Branch: MAIN
Changes since 1.8: +155 -81 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     =item comparisons, <, <=, ==, =, !=, =>, >
218    
219     You can compare expressions against constants via any of these
220     operators. If the constant is a string, then a string compare will be
221     done, otherwise a numerical comparison is used.
222    
223 root 1.4 Example: match an object with name "schnops" that has a value >= 10.
224 root 1.2
225 root 1.4 name="schnops" and value >= 10
226 root 1.2
227     =item uppercase constant names
228    
229 root 1.4 Any uppercase word that exists as constant inside the C<cf::> namespace
230     (that is, any deliantra constant) can also be used as-is, but needs to be
231 root 1.2 specified in uppercase.
232    
233     Example: match a type of POTION (using C<cf::POTION>).
234    
235     type=POTION
236    
237 root 1.1 =back
238    
239     =head2 FUNCTIONS
240    
241     =over 4
242    
243 root 1.2 =item any
244    
245     This simply evaluates to true, and simply makes matching I<any> object a
246     bit easier to read.
247    
248 root 1.9 =item has(cond)
249 root 1.1
250     True iff the object has a matching inventory object.
251    
252 root 1.9 =item count(match)
253    
254     Number of matching objects - the context object for the C<match> are the
255     original context objects for the overall C<match>. # TODO bullshit
256    
257     =item match(match)
258 root 1.1
259 root 1.9 An independent match - unlike C<count>, it only matters whether the match
260     finds any object (which is faster).
261 root 1.1
262     =back
263    
264 root 1.9 =head2 GRAMMAR
265    
266     This is the grammar that was used to implement the matching language
267     module. It is meant to be easily readable by humans, not to implement it
268     exactly as-is.
269    
270     # object matching and selecting
271    
272     match = set
273     | match also rep 'in' set
274     also = nothing | 'also'
275     rep = nothing | 'rep' | 'repeatedly'
276    
277     set = 'inv' | 'env' | 'map'
278     | 'object' | 'source' | 'originator' | 'self'
279    
280     empty =
281    
282     # boolean matching condition
283    
284     condition = factor
285     | factor 'and'? cond
286     | factor 'or' cond
287    
288     factor = 'not' factor
289     | '(' cond ')'
290     | expr
291     | expr operator constant
292    
293     operator = '=' | '==' | '!=' | '<' | '<=' | '>' | '>='
294    
295     expr = flag
296     | sattr
297     | aattr '[' <constant> ']'
298     | special
299     | func '(' args ')'
300     | '{' perl code block '}'
301    
302     func = <any function name>
303     sattr = <any scalar object attribute>
304     aattr = <any array object attribute>
305     flag = <any object flag>
306     special = <any ()-less "function">
307    
308     constant = <number> | '"' <string> '"' | <uppercase cf::XXX name>
309     args = <depends on function>
310    
311     TODO: repeatedly, env, contains, possbly matches
312    
313 root 1.1 =cut
314    
315    
316     package cf::match;
317    
318     use common::sense;
319    
320     use List::Util ();
321    
322     # parser state
323     # $_ # string to be parsed
324     our $all; # find all, or just the first matching object
325    
326     {
327     package cf::match::exec;
328    
329     use List::Util qw(first);
330    
331     sub env_chain {
332     my @res;
333     push @res, $_
334     while $_ = $_->env;
335     @res
336     }
337    
338     package cf::match::parser;
339    
340     use common::sense;
341    
342     sub ws {
343     /\G\s+/gc;
344     }
345    
346     our %func = (
347     has => sub {
348 root 1.9 'first { ' . &condition . ' } $_->inv'
349 root 1.1 },
350     count => sub {
351     local $all = 1;
352 root 1.9 '(scalar ' . &match . ')'
353     },
354     match => sub {
355     local $all = 0;
356     '(scalar ' . &match . ')'
357 root 1.1 },
358     );
359    
360     our %special = (
361     any => sub {
362     1
363     },
364     );
365    
366     sub constant {
367     ws;
368    
369     return $1 if /\G([\-\+0-9\.]+)/gc;
370     return "cf::$1" if /\G([A-Z0-9_]+)/gc;
371    
372     #TODO better string parsing, also include ''
373     return $1 if /\G("[^"]+")/gc;
374    
375     die "number, string or uppercase constant name expected\n";
376     }
377    
378     our $flag = $cf::REFLECT{object}{flags};
379     our $sattr = $cf::REFLECT{object}{scalars};
380     our $aattr = $cf::REFLECT{object}{arrays};
381    
382     sub expr {
383     # ws done by factor
384     my $res;
385    
386     if (/\G ( \{ (?: (?> [^{}]+ ) | (?-1) )* \} ) /gcx) {
387     # perl
388    
389     my $expr = $1;
390    
391     $res .= $expr =~ /\{([^;]+)\}/ ? $1 : "do $expr";
392    
393     } elsif (/\G([A-Za-z0-9_]+)/gc) {
394    
395     if (my $func = $func{$1}) {
396     /\G\s*\(/gc
397     or die "'(' expected after function name\n";
398    
399     $res .= $func->();
400    
401     /\G\s*\)/gc
402     or die "')' expected after function arguments\n";
403    
404     } elsif (my $func = $special{$1}) {
405     $res .= $func->();
406    
407     } elsif (exists $flag->{lc $1}) {
408     $res .= "\$_->flag (cf::FLAG_\U$1)";
409    
410     } elsif (exists $sattr->{$1}) {
411     $res .= "\$_->$1";
412    
413     } elsif (exists $aattr->{$1}) {
414    
415     $res .= "\$_->$1";
416    
417     /\G\s*\[/gc
418     or die "'[' expected after array name\n";
419    
420     $res .= "(" . constant . ")";
421    
422     /\G\s*\]/gc
423     or die "']' expected after array index\n";
424    
425     } else {
426     $res .= constant;
427     }
428    
429     } else {
430     die "expr expected\n";
431     }
432    
433     $res
434     }
435    
436     our %stringop = (
437     "==" => "eq",
438     "!=" => "ne",
439     "<=" => "le",
440     ">=" => "ge",
441     "<" => "lt",
442     ">" => "gt",
443     );
444    
445     sub factor {
446     ws;
447    
448     my $res;
449    
450     if (/\Gnot\b\s*/gc) {
451     $res .= "!";
452     }
453    
454     if (/\G\(/gc) {
455     # ()
456 root 1.9 $res .= &condition;
457 root 1.1 ws;
458     /\G\)/gc or die "')' expected\n";
459    
460     } else {
461     my $expr = expr;
462    
463     $res .= $expr;
464    
465     if (/\G\s*([=!<>]=?)/gc) {
466     my $op = $1;
467    
468     $op = "==" if $op eq "=";
469     my $const = constant;
470     $op = $stringop{$op} if $const =~ /^"/;
471    
472     $res .= " $op $const";
473     }
474     }
475    
476     "($res)"
477     }
478    
479 root 1.9 sub condition {
480 root 1.1 my $res = factor;
481    
482     while () {
483     ws;
484     if (/\G(?=also\b|in\b|\)|$)/gc) {
485     # early stop => faster and requires no backtracking
486     last;
487     } elsif (/\Gor\b/gc) {
488     $res .= " || ";
489     } else {
490     /\Gand\b/gc;
491     $res .= " && ";
492     }
493     $res .= factor;
494     }
495    
496     $res
497     }
498    
499 root 1.9 sub match {
500 root 1.1 my $res;
501    
502     my $also; # undef means first iteration
503     while () {
504 root 1.9 if (/\G\s*(inv|env|map|object|subject|originator)\b/gc) {
505 root 1.1 if ($1 eq "inv") {
506     $res .= " map+(${also}\$_->inv),";
507     } elsif ($1 eq "env") {
508 root 1.4 $res .= " map+(${also}env_chain), "; # TODO
509 root 1.1 } elsif ($1 eq "map") {
510     $res .= " map+(${also}\$_->map->at (\$_->x, \$_->y)),";
511 root 1.9 } elsif ($1 eq "self") {
512     return "$res \$self";
513     } elsif ($1 eq "object") {
514     last; # default
515     } elsif ($1 eq "source") {
516     return "$res \$source";
517     } elsif ($1 eq "originator") {
518     return "$res \$originator";
519 root 1.1 }
520     last unless /\G\s*in\b/gc;
521     } else {
522     $res .= " map+($also\$_->inv)," if defined $also;
523     $res .= $all ? " grep { " : " first {";
524 root 1.9 $res .= condition;
525 root 1.1 $res .= "}";
526    
527     $also = /\G\s*also\b/gc ? '$_, ' : '';
528     last unless /\G\s*in\b/gc;
529     }
530     }
531    
532 root 1.9 "$res \$object"
533 root 1.1 }
534    
535     }
536    
537     sub parse($;$) {
538     local $_ = shift;
539     local $all = shift;
540    
541 root 1.9 my $res = cf::match::parser::match;
542 root 1.1
543     if ($@) {
544     my $ctx = 20;
545     my $str = substr $_, (List::Util::max 0, (pos) - $ctx), $ctx * 2;
546     substr $str, (List::Util::min $ctx, pos), 0, "<-- HERE -->";
547    
548     chomp $@;
549     die "$@ ($str)\n";
550     }
551    
552     $res
553     }
554    
555 root 1.9 our %CACHE;
556 root 1.1
557 root 1.9 sub match($$$;$$) {
558     my ($self, $match, $object, $source, $originator) = @_;
559     my $all = wantarray+0;
560    
561     $originator ||= $source;
562    
563     &{
564     $CACHE{"$all$match"} ||= do {
565     my $expr = parse $match, $all;
566     warn "$match,$all => $expr\n";#d#
567     $expr = eval "package cf::match::exec; sub { $expr }";
568     die if $@;
569     $expr
570     }
571     }
572 root 1.2 }
573 root 1.1
574 root 1.9 #match undef, "any", undef;
575     #exit 0;
576    
577 root 1.1 1;
578