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