[ViewVC] Diff of: cvs/deliantra/server/lib/cf/match.pm

Comparing deliantra/server/lib/cf/match.pm (file contents):
Revision 1.2 by root, Sat Oct 10 05:17:46 2009 UTC vs.
Revision 1.13 by root, Sun Oct 11 23:51:47 2009 UTC

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

Diff Legend

-–
+Removed lines
-+
+Added lines
-<
+Changed lines
->
+Changed lines

Comparing deliantra/server/lib/cf/match.pm (file contents): Revision 1.2 by root, Sat Oct 10 05:17:46 2009 UTC vs. Revision 1.13 by root, Sun Oct 11 23:51:47 2009 UTC

Diff Legend

Comparing deliantra/server/lib/cf/match.pm (file contents):
Revision 1.2 by root, Sat Oct 10 05:17:46 2009 UTC vs.
Revision 1.13 by root, Sun Oct 11 23:51:47 2009 UTC