ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/cvsroot/cf.schmorp.de/server/lib/cf/match.pm
Revision: 1.8
Committed: Sat Oct 10 19:11:50 2009 UTC (17 years, 1 month ago) by root
Branch: MAIN
Changes since 1.7: +5 -1 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     to find any (boolean context), or all (list context), matching objects.
9    
10     =head1 MATCH EXAMPLES
11    
12     Match the object if it has a slaying field of C<key1>:
13    
14     slaying = "key1"
15    
16     Match the object if it has an object with name C<force> and
17     slaying C<poison> in it's inventory:
18    
19     has (name = "force" and slaying = "poison")
20    
21 root 1.4 Find all inventory objects with value >= 10, which are not invisible:
22 root 1.1
23 root 1.4 value >= 10 and not invisible in inv
24 root 1.1
25     Find all potions with spell objects inside them in someones inventory:
26    
27     type=SPELL in type=POTION in inv
28    
29     Find all potions inside someones inventory, or inside applied containers:
30    
31 root 1.3 type=POTION also in type=CONTAINER and applied in inv
32 root 1.1
33     =head1 LANGUAGE
34    
35     # object selection
36    
37     select = set
38     | select also rep 'in' set
39     also = nothing | 'also'
40     rep = nothing | 'rep' | 'repeatedly'
41    
42     set = 'inv' | 'env' | 'map'
43    
44     empty =
45    
46     # object matching
47    
48     match = factor
49     | factor 'and'? match
50     | factor 'or' match
51    
52     factor = 'not' factor
53     | '(' match ')'
54     | expr
55     | expr operator constant
56    
57 root 1.4 operator = '=' | '==' | '!=' | '<' | '<=' | '>' | '>='
58 root 1.1
59     expr = flag
60     | sattr
61     | aattr '[' <constant> ']'
62     | special
63     | func '(' args ')'
64     | '{' perl code block '}'
65    
66     func = <any function name>
67     sattr = <any scalar object attribute>
68     aattr = <any array object attribute>
69     flag = <any object flag>
70     special = <any ()-less "function">
71    
72     constant = <number> | '"' <string> '"' | <uppercase cf::XXX name>
73     args = <depends on function>
74    
75 root 1.4 TODO: repeatedly, env, contains, possbly matches
76 root 1.1
77     =head2 STRUCTURE
78    
79     The two main structures are the C<select>, which selects objects matching
80     various criteria, and the C<match>, which determines if an object matches
81     some desired properties.
82    
83     A C<select> is passed a set of "context objects" that it is applied
84     to. This is initially just one object - for altars, it is the object
85     dropped on it, for pedestals, the object on top of it and so on.
86    
87     This set of context objects can be modified in various ways, for example
88     by replacing it with the inventories of all objects, or all objects on the
89     same mapspace, and so on, by using the C<in> operator.
90    
91 root 1.4 Once the set of context objects has been established, each object is
92 root 1.1 matched against the C<match> expression. Sometimes the server is only
93     interested in knowing whether I<anything> matches, and sometimes the
94     server is interested in I<all> objects that match.
95    
96     =head2 OPERATORS
97    
98     =over 4
99    
100     =item and, or, not, ()
101    
102     Match expressions can be combined with C<and> or C<or> to build larger
103     expressions. C<not> negates the expression, and parentheses can be used to
104     group match expressions.
105    
106     Example: match applied weapons.
107    
108     type=WEAPON and applied
109    
110     Example: match horns or rods.
111    
112     type=HORN or type=ROD
113    
114     =item in ...
115    
116 root 1.8 The in operator takes the context set and modifies it in various ways. As
117     a less technical description, think of the C<in> as being a I<look into>
118     or I<look at> operator - instead of looking at whatever was provided to
119     the match, the C<in> operator lets you look at other sets of objects, most
120     often the inventory.
121 root 1.1
122     =over 4
123    
124     =item in inv
125    
126     Replaces all objects by their inventory.
127    
128     Example: find all spell objects inside the object to be matched.
129    
130     type=SPELL in inv
131    
132     =item in env
133    
134     Replaces all objects by their containing object, if they have one.
135    
136     =item in map
137    
138     Replaces all objects by the objects that are on the same mapspace as them.
139    
140     =item in <match>
141    
142     Finds all context objects matching the match expression, and then puts
143     their inventories into the context set.
144    
145     Note that C<in inv> is simply a special case of an C<< in <match> >> that
146     matches any object.
147    
148     Example: find all spells inside potions inside the inventory of the context
149     object(s).
150    
151     type=SPELL in type=POTION in inv
152    
153     =item also in ...
154    
155     Instead of replacing the context set with something new, the new objects
156     are added to the existing set.
157    
158     Example: check if the context object I<is> a spell, or I<contains> a spell.
159    
160     type=SPELL also in inv
161    
162     =item repeatedly in ...
163    
164     Repeats the operation as many times as possible. This can be used to
165     recursively look into objects.
166    
167     =item also repeatedly in ...
168    
169     C<also> and C<repeatedly> can be combined.
170    
171     Example: check if there are any unpaid items in an inventory,
172     or in the inventories of the inventory objects, and so on.
173    
174     unpaid also repeatedly in inv
175    
176     Example: check if a object is inside a player.
177    
178     type=PLAYER also repeatedly in env
179    
180     =back
181    
182     =back
183    
184     =head2 EXPRESSIONS
185    
186     Match expressions usually consist of simple boolean checks (flag XYZ is
187     set) or simple comparisons.
188    
189     =over 4
190    
191 root 1.2 =item flags
192    
193     Flag names (without the leading C<FLAG_>) can be used as-is, in which case
194     their corresponding flag value is used.
195    
196     =item scalar object attributes
197    
198     Object attributes that consist of a single value (C<name>, C<title>,
199     C<value> and so on) can be specified by simply using their name, in which
200     acse their corresponding value is used.
201    
202     =item array objects attributes
203    
204     The C<resist> array can be accessed by specifying C<< resist [ ATNR_type ]
205     >>.
206    
207 root 1.4 Example: match an acid resistance higher than 30.
208 root 1.2
209     resist[ATNR_ACID] > 30
210    
211     =item functions
212    
213     Some additional functions with or without arguments in parentheses are
214     available.
215    
216     =item { BLOCK }
217    
218     You can specify perl code to execute by putting it inside curly
219     braces. The last expression evaluated inside will become the result.
220    
221     =item comparisons, <, <=, ==, =, !=, =>, >
222    
223     You can compare expressions against constants via any of these
224     operators. If the constant is a string, then a string compare will be
225     done, otherwise a numerical comparison is used.
226    
227 root 1.4 Example: match an object with name "schnops" that has a value >= 10.
228 root 1.2
229 root 1.4 name="schnops" and value >= 10
230 root 1.2
231     =item uppercase constant names
232    
233 root 1.4 Any uppercase word that exists as constant inside the C<cf::> namespace
234     (that is, any deliantra constant) can also be used as-is, but needs to be
235 root 1.2 specified in uppercase.
236    
237     Example: match a type of POTION (using C<cf::POTION>).
238    
239     type=POTION
240    
241 root 1.1 =back
242    
243     =head2 FUNCTIONS
244    
245     =over 4
246    
247 root 1.2 =item any
248    
249     This simply evaluates to true, and simply makes matching I<any> object a
250     bit easier to read.
251    
252 root 1.1 =item has(match)
253    
254     True iff the object has a matching inventory object.
255    
256     =item count(select)
257    
258 root 1.4 Number of matching objects - the context object for the C<select> are the
259     original context objects for the overall C<select>. # TODO bullshit
260 root 1.1
261     =back
262    
263     =cut
264    
265    
266     package cf::match;
267    
268     use common::sense;
269    
270     use List::Util ();
271    
272     # parser state
273     # $_ # string to be parsed
274     our $all; # find all, or just the first matching object
275    
276     {
277     package cf::match::exec;
278    
279     use List::Util qw(first);
280    
281     sub env_chain {
282     my @res;
283     push @res, $_
284     while $_ = $_->env;
285     @res
286     }
287    
288     package cf::match::parser;
289    
290     use common::sense;
291    
292     sub ws {
293     /\G\s+/gc;
294     }
295    
296     our %func = (
297     has => sub {
298     'first { ' . &match . ' } $_->inv'
299     },
300     count => sub {
301     local $all = 1;
302     '(scalar ' . &select . ')'
303     },
304     );
305    
306     our %special = (
307     any => sub {
308     1
309     },
310     );
311    
312     sub constant {
313     ws;
314    
315     return $1 if /\G([\-\+0-9\.]+)/gc;
316     return "cf::$1" if /\G([A-Z0-9_]+)/gc;
317    
318     #TODO better string parsing, also include ''
319     return $1 if /\G("[^"]+")/gc;
320    
321     die "number, string or uppercase constant name expected\n";
322     }
323    
324     our $flag = $cf::REFLECT{object}{flags};
325     our $sattr = $cf::REFLECT{object}{scalars};
326     our $aattr = $cf::REFLECT{object}{arrays};
327    
328     sub expr {
329     # ws done by factor
330     my $res;
331    
332     if (/\G ( \{ (?: (?> [^{}]+ ) | (?-1) )* \} ) /gcx) {
333     # perl
334    
335     my $expr = $1;
336    
337     $res .= $expr =~ /\{([^;]+)\}/ ? $1 : "do $expr";
338    
339     } elsif (/\G([A-Za-z0-9_]+)/gc) {
340    
341     if (my $func = $func{$1}) {
342     /\G\s*\(/gc
343     or die "'(' expected after function name\n";
344    
345     $res .= $func->();
346    
347     /\G\s*\)/gc
348     or die "')' expected after function arguments\n";
349    
350     } elsif (my $func = $special{$1}) {
351     $res .= $func->();
352    
353     } elsif (exists $flag->{lc $1}) {
354     $res .= "\$_->flag (cf::FLAG_\U$1)";
355    
356     } elsif (exists $sattr->{$1}) {
357     $res .= "\$_->$1";
358    
359     } elsif (exists $aattr->{$1}) {
360    
361     $res .= "\$_->$1";
362    
363     /\G\s*\[/gc
364     or die "'[' expected after array name\n";
365    
366     $res .= "(" . constant . ")";
367    
368     /\G\s*\]/gc
369     or die "']' expected after array index\n";
370    
371     } else {
372     $res .= constant;
373     }
374    
375     } else {
376     die "expr expected\n";
377     }
378    
379     $res
380     }
381    
382     our %stringop = (
383     "==" => "eq",
384     "!=" => "ne",
385     "<=" => "le",
386     ">=" => "ge",
387     "<" => "lt",
388     ">" => "gt",
389     );
390    
391     sub factor {
392     ws;
393    
394     my $res;
395    
396     if (/\Gnot\b\s*/gc) {
397     $res .= "!";
398     }
399    
400     if (/\G\(/gc) {
401     # ()
402     $res .= &match;
403     ws;
404     /\G\)/gc or die "')' expected\n";
405    
406     } else {
407     my $expr = expr;
408    
409     $res .= $expr;
410    
411     if (/\G\s*([=!<>]=?)/gc) {
412     my $op = $1;
413    
414     $op = "==" if $op eq "=";
415     my $const = constant;
416     $op = $stringop{$op} if $const =~ /^"/;
417    
418     $res .= " $op $const";
419     }
420     }
421    
422     "($res)"
423     }
424    
425     sub match {
426     my $res = factor;
427    
428     while () {
429     ws;
430     if (/\G(?=also\b|in\b|\)|$)/gc) {
431     # early stop => faster and requires no backtracking
432     last;
433     } elsif (/\Gor\b/gc) {
434     $res .= " || ";
435     } else {
436     /\Gand\b/gc;
437     $res .= " && ";
438     }
439     $res .= factor;
440     }
441    
442     $res
443     }
444    
445     sub select {
446     my $res;
447    
448     my $also; # undef means first iteration
449     while () {
450     if (/\G\s*(inv|env|map)\b/gc) {
451     if ($1 eq "inv") {
452     $res .= " map+(${also}\$_->inv),";
453     } elsif ($1 eq "env") {
454 root 1.4 $res .= " map+(${also}env_chain), "; # TODO
455 root 1.1 } elsif ($1 eq "map") {
456     $res .= " map+(${also}\$_->map->at (\$_->x, \$_->y)),";
457     }
458     last unless /\G\s*in\b/gc;
459     } else {
460     $res .= " map+($also\$_->inv)," if defined $also;
461     $res .= $all ? " grep { " : " first {";
462     $res .= match;
463     $res .= "}";
464    
465     $also = /\G\s*also\b/gc ? '$_, ' : '';
466     last unless /\G\s*in\b/gc;
467     }
468     }
469    
470     "$res \@ctx"
471     }
472    
473     }
474    
475     sub parse($;$) {
476     local $_ = shift;
477     local $all = shift;
478    
479 root 1.7 my $res = cf::match::parser::select;
480 root 1.1
481     if ($@) {
482     my $ctx = 20;
483     my $str = substr $_, (List::Util::max 0, (pos) - $ctx), $ctx * 2;
484     substr $str, (List::Util::min $ctx, pos), 0, "<-- HERE -->";
485    
486     chomp $@;
487     die "$@ ($str)\n";
488     }
489    
490     $res
491     }
492    
493 root 1.6 if (0) {
494 root 1.5 my $perl = parse '{ {1}}', 0;
495 root 1.1
496 root 1.2 warn $perl, "\n";#d#
497 root 1.7 $perl = eval "package cf::match::exec; no warnings; no feature; our \@ctx; sub { $perl }"; die if $@;
498 root 1.2 use B::Deparse;
499     warn B::Deparse->new->coderef2text ($perl);
500     exit 0;
501     }
502 root 1.1
503     1;
504