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

Comparing deliantra/server/lib/cf/match.pm (file contents):
Revision 1.8 by root, Sat Oct 10 19:11:50 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
…		…
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 and applied 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, contains, possbly matches
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 object 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
…		…
135		114
136	=item in map	115	=item in map
137		116
138	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.
139		118
140	=item in <match>	119	=item in <cond>
141		120
142	Finds all context objects matching the match expression, and then puts	121	Finds all context objects matching the condition, and then puts their
143	their inventories into the context set.	122	inventories into the context set.
144		123
145	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
146	matches any object.	125	matches any object.
147		126
148	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
149	object(s).	128	object(s).
150		129
…		…
157		136
158	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.
159		138
160	type=SPELL also in inv	139	type=SPELL also in inv
161		140
162	=item repeatedly in ...	141	=item deep in ...
163		142
164	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
165	recursively look into objects.	144	recursively look into objects.
166		145
167	=item also repeatedly in ...	146	=item also deep in ...
168		147
169	C<also> and C<repeatedly> can be combined.	148	C<also> and C<deep> can be combined.
170		149
171	Example: check if there are any unpaid items in an inventory,	150	Example: check if there are any unpaid items in an inventory,
172	or in the inventories of the inventory objects, and so on.	151	or in the inventories of the inventory objects, and so on.
173		152
174	unpaid also repeatedly in inv	153	unpaid also deep in inv
175		154
176	Example: check if a object is inside a player.	155	Example: check if a object is inside a player.
177		156
178	type=PLAYER also repeatedly in env	157	type=PLAYER also deep in env
179		158
180	=back	159	=back
181		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
182	=back	200	=back
183		201
184	=head2 EXPRESSIONS	202	=head2 EXPRESSIONS
185		203
186	Match expressions usually consist of simple boolean checks (flag XYZ is	204	Expressions used in conditions usually consist of simple boolean checks
187	set) or simple comparisons.	205	(flag XYZ is set) or simple comparisons.
188		206
189	=over 4	207	=over 4
190		208
191	=item flags	209	=item flags
192		210
…		…
216	=item { BLOCK }	234	=item { BLOCK }
217		235
218	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
219	braces. The last expression evaluated inside will become the result.	237	braces. The last expression evaluated inside will become the result.
220		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+$/ }
		245
221	=item comparisons, <, <=, ==, =, !=, =>, >	246	=item comparisons, <, <=, ==, =, !=, =>, >
222		247
223	You can compare expressions against constants via any of these	248	You can compare expressions against constants via any of these
224	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
225	done, otherwise a numerical comparison is used.	250	done, otherwise a numerical comparison is used.
…		…
247	=item any	272	=item any
248		273
249	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
250	bit easier to read.	275	bit easier to read.
251		276
252	=item has(match)	277	=item has(condition)
253		278
254	True iff the object has a matching inventory object.	279	True iff the object has a matching inventory object.
255		280
256	=item count(select)	281	=item count(match)
257		282
258	Number of matching objects - the context object for the C<select> are the	283	Number of matching objects - the context object for the C<match> is the
259	original context objects for the overall C<select>. # TODO bullshit	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
260		300
261	=back	301	=back
262		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
263	=cut	353	=cut
264		354
		355	=head2 PERL FUNCTIONS
		356
		357	=over 4
		358
		359	=cut
265		360
266	package cf::match;	361	package cf::match;
267		362
268	use common::sense;	363	use common::sense;
269		364
…		…
276	{	371	{
277	package cf::match::exec;	372	package cf::match::exec;
278		373
279	use List::Util qw(first);	374	use List::Util qw(first);
280		375
281	sub env_chain {
282	my @res;
283	push @res, $_
284	while $_ = $_->env;
285	@res
286	}
287
288	package cf::match::parser;	376	package cf::match::parser;
289		377
290	use common::sense;	378	use common::sense;
291		379
292	sub ws {	380	sub ws {
293	/\G\s+/gc;	381	/\G\s+/gc;
294	}	382	}
295		383
296	our %func = (	384	our %func = (
297	has => sub {	385	has => sub {
298	'first { ' . &match . ' } $_->inv'	386	'first { ' . &condition . ' } $_->inv'
299	},	387	},
300	count => sub {	388	count => sub {
301	local $all = 1;	389	local $all = 1;
302	'(scalar ' . &select . ')'	390	'(scalar ' . &match ('$_') . ')'
		391	},
		392	match => sub {
		393	local $all = 0;
		394	'(scalar ' . &match ('$_') . ')'
303	},	395	},
304	);	396	);
305		397
306	our %special = (	398	our %special = (
307	any => sub {	399	any => sub {
308	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	}';
309	},	409	},
310	);	410	);
311		411
312	sub constant {	412	sub constant {
313	ws;	413	ws;
…		…
397	$res .= "!";	497	$res .= "!";
398	}	498	}
399		499
400	if (/\G\(/gc) {	500	if (/\G\(/gc) {
401	# ()	501	# ()
402	$res .= &match;	502	$res .= &condition;
403	ws;	503	ws;
404	/\G\)/gc or die "')' expected\n";	504	/\G\)/gc or die "')' expected\n";
405		505
406	} else {	506	} else {
407	my $expr = expr;	507	my $expr = expr;
…		…
420	}	520	}
421		521
422	"($res)"	522	"($res)"
423	}	523	}
424		524
425	sub match {	525	sub condition {
426	my $res = factor;	526	my $res = factor;
427		527
428	while () {	528	while () {
429	ws;	529	ws;
		530
		531	# first check some stop-symbols, so we don't have to backtrack
430	if (/\G(?=also\b\|in\b\|\)\|$)/gc) {	532	if (/\G(?=also\b\|deep\b\|in\b\|of\b\)\|$)/gc) {
431	# early stop => faster and requires no backtracking
432	last;	533	last;
		534
433	} elsif (/\Gor\b/gc) {	535	} elsif (/\Gor\b/gc) {
434	$res .= " \|\| ";	536	$res .= " \|\| ";
		537
435	} else {	538	} else {
436	/\Gand\b/gc;	539	/\Gand\b/gc;
437	$res .= " && ";	540	$res .= " && ";
438	}	541	}
439	$res .= factor;	542	$res .= factor;
440	}	543	}
441		544
442	$res	545	$res
443	}	546	}
444		547
445	sub select {	548	sub match {
446	my $res;	549	my $default = shift;
447		550
448	my $also; # undef means first iteration	551	my $res = ($all ? " grep { " : " first {") . condition . " }";
		552
449	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
450	if (/\G\s*(inv\|env\|map)\b/gc) {	562	if (/\G(inv\|env\|map)\b/gc) {
451	if ($1 eq "inv") {	563	if ($1 eq "inv") {
452	$res .= " map+(${also}\$_->inv),";	564	$expand = "map \$_->inv,";
453	} elsif ($1 eq "env") {	565	} elsif ($1 eq "env") {
454	$res .= " map+(${also}env_chain), "; # TODO	566	$expand = "map \$_->env // (),";
455	} elsif ($1 eq "map") {	567	} elsif ($1 eq "map") {
456	$res .= " map+(${also}\$_->map->at (\$_->x, \$_->y)),";	568	$expand = "map \$_->map->at (\$_->x, \$_->y),";
		569	}
		570	} else {
		571	$expand = "map \$_->inv, grep { " . condition . " }";
457	}	572	}
458	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	}
459	} else {	599	} else {
460	$res .= " map+($also\$_->inv)," if defined $also;	600	return "$res $default";
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	}	601	}
468	}	602	}
469
470	"$res \@ctx"
471	}	603	}
472
473	}	604	}
474		605
475	sub parse($;$) {	606	sub parse($;$) {
476	local $_ = shift;	607	local $_ = shift;
477	local $all = shift;	608	local $all = shift;
478		609
		610	my $res;
		611
		612	eval {
479	my $res = cf::match::parser::select;	613	$res = cf::match::parser::match "\$object";
		614
		615	/\G\s*$/gc
		616	or die "unexpected trailing characters after match\n";
		617	};
480		618
481	if ($@) {	619	if ($@) {
482	my $ctx = 20;	620	my $ctx = 20;
483	my $str = substr $_, (List::Util::max 0, (pos) - $ctx), $ctx * 2;	621	my $str = substr $_, (List::Util::max 0, (pos) - $ctx), $ctx * 2;
484	substr $str, (List::Util::min $ctx, pos), 0, "<-- HERE -->";	622	substr $str, (List::Util::min $ctx, pos), 0, "<-- HERE -->";
…		…
488	}	626	}
489		627
490	$res	628	$res
491	}	629	}
492		630
493	if (0) {	631	if (0) {#d#
494	my $perl = parse '{ {1}}', 0;	632	die parse 'applied', 1;
495
496	warn $perl, "\n";#d#
497	$perl = eval "package cf::match::exec; no warnings; no feature; our \@ctx; sub { $perl }"; die if $@;
498	use B::Deparse;
499	warn B::Deparse->new->coderef2text ($perl);
500	exit 0;	633	exit 0;
501	}	634	}
502		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
503	1;	689	1;
504		690

Diff Legend

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

Comparing deliantra/server/lib/cf/match.pm (file contents): Revision 1.8 by root, Sat Oct 10 19:11:50 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.8 by root, Sat Oct 10 19:11:50 2009 UTC vs.
Revision 1.13 by root, Sun Oct 11 23:51:47 2009 UTC