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