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