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

Comparing deliantra/server/lib/cf/match.pm (file contents):
Revision 1.6 by root, Sat Oct 10 05:33:08 2009 UTC vs.
Revision 1.15 by root, Mon Oct 12 17:37:43 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
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
…		…
127		110
128	=item in env	111	=item in env
129		112
130	Replaces all objects by their containing object, if they have one.	113	Replaces all objects by their containing object, if they have one.
131		114
		115	=item in arch
		116
		117	Replaces all objects by their archetypes.
		118
132	=item in map	119	=item in map
133		120
134	Replaces all objects by the objects that are on the same mapspace as them.	121	Replaces all objects by the objects that are on the same mapspace as them.
135		122
136	=item in <match>	123	=item in <condition>
137		124
138	Finds all context objects matching the match expression, and then puts	125	Finds all context objects matching the condition, and then puts their
139	their inventories into the context set.	126	inventories into the context set.
140		127
141	Note that C<in inv> is simply a special case of an C<< in <match> >> that	128	Note that C<in inv> is simply a special case of an C<< in <condition> >> that
142	matches any object.	129	matches any object.
143		130
144	Example: find all spells inside potions inside the inventory of the context	131	Example: find all spells inside potions inside the inventory of the context
145	object(s).	132	object(s).
146		133
…		…
153		140
154	Example: check if the context object I<is> a spell, or I<contains> a spell.	141	Example: check if the context object I<is> a spell, or I<contains> a spell.
155		142
156	type=SPELL also in inv	143	type=SPELL also in inv
157		144
158	=item repeatedly in ...	145	=item deep in ...
159		146
160	Repeats the operation as many times as possible. This can be used to	147	Repeats the operation as many times as possible. This can be used to
161	recursively look into objects.	148	recursively look into objects.
162		149
163	=item also repeatedly in ...	150	=item also deep in ...
164		151
165	C<also> and C<repeatedly> can be combined.	152	C<also> and C<deep> can be combined.
166		153
167	Example: check if there are any unpaid items in an inventory,	154	Example: check if there are any unpaid items in an inventory,
168	or in the inventories of the inventory objects, and so on.	155	or in the inventories of the inventory objects, and so on.
169		156
170	unpaid also repeatedly in inv	157	unpaid also deep in inv
171		158
172	Example: check if a object is inside a player.	159	Example: check if a object is inside a player.
173		160
174	type=PLAYER also repeatedly in env	161	type=PLAYER also deep in env
175		162
176	=back	163	=back
177		164
		165	=item of ...
		166
		167	By default, all matches are applied to the "obviously appropriate" object,
		168	such as the item dropped on a button or moving over a detector. This can
		169	be changed to a number of other objects - not all of them are available
		170	for each match (when not available, the match will simply fail).
		171
		172	An C<of> term ends a match, nothing is allowed to follow.
		173
		174	=over 4
		175
		176	=item of object
		177
		178	Starts with the default object - this is the object passed to the match to
		179	match against by default. Matches have an explicit C<of object> appended,
		180	but submatches start at the current object, and in this case C<of object>
		181	can be used to start at the original object once more.
		182
		183	=item of source
		184
		185	Starts with the I<source> object - this object is sometimes passed to
		186	matches and represents the object that is the source of the action, such
		187	as a rod or a potion when it is applied. Often, the I<source> is the same
		188	as the I<originator>.
		189
		190	=item of originator
		191
		192	Starts with the I<originator> - one step farther removed than the
		193	I<source>, the I<originator> is sometimes passed to matches and represents
		194	the original initiator of an action, most commonly a player or monster.
		195
		196	This object is often identical to the I<source> (e.g. when a player casts
		197	a spell, the player is both source and originator).
		198
		199	=item of self
		200
		201	Starts with the object initiating/asking for the match - this is basically
		202	always the object that the match expression is attached to.
		203
178	=back	204	=back
179		205
180	=head2 EXPRESSIONS	206	=head2 EXPRESSIONS
181		207
182	Match expressions usually consist of simple boolean checks (flag XYZ is	208	Expressions used in conditions usually consist of simple boolean checks
183	set) or simple comparisons.	209	(flag XYZ is set) or simple comparisons.
184		210
185	=over 4	211	=over 4
186		212
187	=item flags	213	=item flags
188		214
…		…
212	=item { BLOCK }	238	=item { BLOCK }
213		239
214	You can specify perl code to execute by putting it inside curly	240	You can specify perl code to execute by putting it inside curly
215	braces. The last expression evaluated inside will become the result.	241	braces. The last expression evaluated inside will become the result.
216		242
		243	The perlcode can access C<$_>, which rferes to the object currently being
		244	matches, and the C<$object>, C<$self>, C<$source> and C<$originator>.
		245
		246	Example: check whether the slaying field consists of digits only.
		247
		248	{ $_->slaying =~ /^\d+$/ }
		249
217	=item comparisons, <, <=, ==, =, !=, =>, >	250	=item comparisons, <, <=, ==, =, !=, =>, >
218		251
219	You can compare expressions against constants via any of these	252	You can compare expressions against constants via any of these
220	operators. If the constant is a string, then a string compare will be	253	operators. If the constant is a string, then a string compare will be
221	done, otherwise a numerical comparison is used.	254	done, otherwise a numerical comparison is used.
…		…
243	=item any	276	=item any
244		277
245	This simply evaluates to true, and simply makes matching I<any> object a	278	This simply evaluates to true, and simply makes matching I<any> object a
246	bit easier to read.	279	bit easier to read.
247		280
248	=item has(match)	281	=item has(condition)
249		282
250	True iff the object has a matching inventory object.	283	True iff the object has a matching inventory object.
251		284
252	=item count(select)	285	=item count(match)
253		286
254	Number of matching objects - the context object for the C<select> are the	287	Number of matching objects - the context object for the C<match> is the
255	original context objects for the overall C<select>. # TODO bullshit	288	currently tested object - you can override this with an C<in object> for
		289	example.
		290
		291	=item match(match)
		292
		293	An independent match - semantics like C<count>, except it only matters
		294	whether the match finds any object (which is faster).
		295
		296	=item dump()
		297
		298	Dumps the object to the server log when executed, and evaluates to true.
		299
		300	Note that logical operations are short-circuiting, so this only dumps
		301	potions:
		302
		303	type=POTION and dump()
256		304
257	=back	305	=back
258		306
		307	=head2 GRAMMAR
		308
		309	This is the grammar that was used to implement the matching language
		310	module. It is meant to be easily readable by humans, not to implement it
		311	exactly as-is.
		312
		313	# object matching and selecting
		314
		315	match = chain
		316	\| chain 'of' root
		317	root = 'object' \| 'self' \| 'source' \| 'originator'
		318	chain = condition
		319	\| chain also deep 'in' set
		320	also = nothing \| 'also'
		321	deep = nothing \| 'deep'
		322	set = 'inv' \| 'env' \| 'arch' \| 'map'
		323
		324	empty =
		325
		326	# boolean matching condition
		327
		328	condition = factor
		329	\| factor 'and'? condition
		330	\| factor 'or' condition
		331
		332	factor = 'not' factor
		333	\| '(' condition ')'
		334	\| expr
		335	\| expr operator constant
		336
		337	operator = '=' \| '==' \| '!=' \| '<' \| '<=' \| '>' \| '>='
		338
		339	expr = flag
		340	\| sattr
		341	\| aattr '[' <constant> ']'
		342	\| special
		343	\| func '(' args ')'
		344	\| '{' perl code block '}'
		345
		346	func = <any function name>
		347	sattr = <any scalar object attribute>
		348	aattr = <any array object attribute>
		349	flag = <any object flag>
		350	special = <any ()-less "function">
		351
		352	constant = <number> \| '"' <string> '"' \| <uppercase cf::XXX name>
		353	args = <depends on function>
		354
		355	TODO: contains, matches, query_name, selling_price, buying_price?
		356
259	=cut	357	=cut
260		358
		359	=head2 PERL FUNCTIONS
		360
		361	=over 4
		362
		363	=cut
261		364
262	package cf::match;	365	package cf::match;
263		366
264	use common::sense;	367	use common::sense;
265		368
…		…
270	our $all; # find all, or just the first matching object	373	our $all; # find all, or just the first matching object
271		374
272	{	375	{
273	package cf::match::exec;	376	package cf::match::exec;
274		377
275	our @ctx; # root object(s)
276
277	use List::Util qw(first);	378	use List::Util qw(first);
278
279	sub env_chain {
280	my @res;
281	push @res, $_
282	while $_ = $_->env;
283	@res
284	}
285		379
286	package cf::match::parser;	380	package cf::match::parser;
287		381
288	use common::sense;	382	use common::sense;
289		383
…		…
291	/\G\s+/gc;	385	/\G\s+/gc;
292	}	386	}
293		387
294	our %func = (	388	our %func = (
295	has => sub {	389	has => sub {
296	'first { ' . &match . ' } $_->inv'	390	'first { ' . &condition . ' } $_->inv'
297	},	391	},
298	count => sub {	392	count => sub {
299	local $all = 1;	393	local $all = 1;
300	'(scalar ' . &select . ')'	394	'(scalar ' . &match ('$_') . ')'
		395	},
		396	match => sub {
		397	local $all = 0;
		398	'(scalar ' . &match ('$_') . ')'
		399	},
		400	dump => sub {
		401	'do {
		402	warn "cf::match::match dump:\n"
		403	. "self: " . eval { $self->name } . "\n"
		404	. $_->as_string;
		405	1
		406	}';
301	},	407	},
302	);	408	);
303		409
304	our %special = (	410	our %special = (
305	any => sub {	411	any => sub {
…		…
395	$res .= "!";	501	$res .= "!";
396	}	502	}
397		503
398	if (/\G\(/gc) {	504	if (/\G\(/gc) {
399	# ()	505	# ()
400	$res .= &match;	506	$res .= &condition;
401	ws;	507	ws;
402	/\G\)/gc or die "')' expected\n";	508	/\G\)/gc or die "')' expected\n";
403		509
404	} else {	510	} else {
405	my $expr = expr;	511	my $expr = expr;
…		…
418	}	524	}
419		525
420	"($res)"	526	"($res)"
421	}	527	}
422		528
423	sub match {	529	sub condition {
424	my $res = factor;	530	my $res = factor;
425		531
426	while () {	532	while () {
427	ws;	533	ws;
		534
		535	# first check some stop-symbols, so we don't have to backtrack
428	if (/\G(?=also\b\|in\b\|\)\|$)/gc) {	536	if (/\G(?=also\b\|deep\b\|in\b\|of\b\)\|\z)/gc) {
429	# early stop => faster and requires no backtracking	537	pos = pos; # argh. the misop hits again. again. again. again. you die.
430	last;	538	last;
		539
431	} elsif (/\Gor\b/gc) {	540	} elsif (/\Gor\b/gc) {
432	$res .= " \|\| ";	541	$res .= " \|\| ";
		542
433	} else {	543	} else {
434	/\Gand\b/gc;	544	/\Gand\b/gc;
435	$res .= " && ";	545	$res .= " && ";
436	}	546	}
437	$res .= factor;	547	$res .= factor;
438	}	548	}
439		549
440	$res	550	$res
441	}	551	}
442		552
443	sub select {	553	sub match {
444	my $res;	554	my $default = shift;
445		555
446	my $also; # undef means first iteration	556	my $res = ($all ? " grep { " : " first {") . condition . " }";
		557
447	while () {	558	while () {
		559	ws;
		560
		561	my $also = /\Galso\s+/gc + 0;
		562	my $deep = /\Gdeep\s+/gc + 0;
		563
		564	if (/\Gin\s+/gc) {
		565	my $expand;
		566
448	if (/\G\s*(inv\|env\|map)\b/gc) {	567	if (/\G(inv\|env\|map\|arch)\b/gc) {
449	if ($1 eq "inv") {	568	if ($1 eq "inv") {
450	$res .= " map+(${also}\$_->inv),";	569	$expand = "map \$_->inv,";
451	} elsif ($1 eq "env") {	570	} elsif ($1 eq "env") {
452	$res .= " map+(${also}env_chain), "; # TODO	571	$expand = "map \$_->env // (),";
		572	} elsif ($1 eq "arch") {
		573	$expand = "map \$_->arch,";
453	} elsif ($1 eq "map") {	574	} elsif ($1 eq "map") {
454	$res .= " map+(${also}\$_->map->at (\$_->x, \$_->y)),";	575	$expand = "map \$_->map->at (\$_->x, \$_->y),";
		576	}
		577	} else {
		578	$expand = "map \$_->inv, grep { " . condition . " }";
455	}	579	}
456	last unless /\G\s*in\b/gc;	580
		581	if ($also \|\| $deep) {
		582	$res .= " do {\n"
		583	. " my \@res;\n";
		584	$res .= " while (\@_) {\n" if $deep;
		585	$res .= " push \@res, \@_;\n" if $also;
		586	$res .= " \@_ = $expand \@_;\n";
		587	$res .= " }\n" if $deep;
		588	$res .= " (\@res, \@_)\n"
		589	. "}";
		590	} else {
		591	$res .= " $expand";
		592	}
		593	} elsif (/\Gof\s+(self\|object\|source\|originator)\b/gc) {
		594	$also \|\| $deep
		595	and die "neither 'also' nor 'deep' can be used with 'of'\n";
		596
		597	if ($1 eq "self") {
		598	return "$res \$self // ()";
		599	} elsif ($1 eq "object") {
		600	return "$res \$object";
		601	} elsif ($1 eq "source") {
		602	return "$res \$source // ()";
		603	} elsif ($1 eq "originator") {
		604	return "$res \$originator // \$source // ()";
		605	}
457	} else {	606	} else {
458	$res .= " map+($also\$_->inv)," if defined $also;	607	return "$res $default";
459	$res .= $all ? " grep { " : " first {";
460	$res .= match;
461	$res .= "}";
462
463	$also = /\G\s*also\b/gc ? '$_, ' : '';
464	last unless /\G\s*in\b/gc;
465	}	608	}
466	}	609	}
467
468	"$res \@ctx"
469	}	610	}
470
471	}	611	}
472		612
473	sub parse($;$) {	613	sub parse($;$) {
474	local $_ = shift;	614	local $_ = shift;
475	local $all = shift;	615	local $all = shift;
476		616
477	my $res = "package cf::match::exec;\n"	617	my $res;
478	. eval { cf::match::parser::select };	618
		619	eval {
		620	$res = cf::match::parser::match "\$object";
		621
		622	/\G$/gc
		623	or die "unexpected trailing characters after match\n";
		624	};
479		625
480	if ($@) {	626	if ($@) {
481	my $ctx = 20;	627	my $ctx = 20;
482	my $str = substr $_, (List::Util::max 0, (pos) - $ctx), $ctx * 2;	628	my $str = substr $_, (List::Util::max 0, (pos) - $ctx), $ctx * 2;
483	substr $str, (List::Util::min $ctx, pos), 0, "<-- HERE -->";	629	substr $str, (List::Util::min $ctx, pos), 0, "<-- HERE -->";
…		…
487	}	633	}
488		634
489	$res	635	$res
490	}	636	}
491		637
492	if (0) {	638	if (0) {#d#
493	my $perl = parse '{ {1}}', 0;	639	die parse 'type=SPELL_EFFECT and match(name="bullet" in arch)', 1;
494
495	warn $perl, "\n";#d#
496	$perl = eval "no warnings; no feature; sub { $perl }"; die if $@;
497	use B::Deparse;
498	warn B::Deparse->new->coderef2text ($perl);
499	exit 0;	640	exit 0;
500	}	641	}
501		642
		643	=item cf::match::match $match, $object[, $self[, $source[, $originator]]]
		644
		645	Compiles (and caches) the C<$match> expression and matches it against
		646	the C<$object>. C<$self> should be the object initiating the match (or
		647	C<undef>), C<$source> should be the actor/source and C<$originator> the
		648	object that initiated the action (such as the player). C<$originator>
		649	defaults to C<$source> when not given.
		650
		651	In list context it finds and returns all matching objects, in scalar
		652	context only a true or false value.
		653
		654	=cut
		655
		656	our %CACHE;
		657
		658	sub compile($$) {
		659	my ($match, $all) = @_;
		660	my $expr = parse $match, $all;
		661	warn "MATCH DEBUG $match,$all => $expr\n";#d#
		662	$expr = eval "
		663	package cf::match::exec;
		664	sub {
		665	my (\$object, \$self, \$source, \$originator) = \@_;
		666	$expr
		667	}
		668	";
		669	die if $@;
		670
		671	$expr
		672	}
		673
		674	sub match($$;$$$) {
		675	my $match = shift;
		676	my $all = wantarray+0;
		677
		678	&{
		679	$CACHE{"$all$match"} \|\|= compile $match, $all
		680	}
		681	}
		682
		683	#d# $::schmorp=cf::player::find "schmorp"&
		684	#d# cf::match::match '', $::schmorp->ob
		685
		686
		687	=back
		688
		689	=head1 AUTHOR
		690
		691	Marc Lehmann <schmorp@schmorp.de>
		692	http://home.schmorp.de/
		693
		694	=cut
		695
502	1;	696	1;
503		697

Diff Legend

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

Comparing deliantra/server/lib/cf/match.pm (file contents): Revision 1.6 by root, Sat Oct 10 05:33:08 2009 UTC vs. Revision 1.15 by root, Mon Oct 12 17:37:43 2009 UTC

Diff Legend

Comparing deliantra/server/lib/cf/match.pm (file contents):
Revision 1.6 by root, Sat Oct 10 05:33:08 2009 UTC vs.
Revision 1.15 by root, Mon Oct 12 17:37:43 2009 UTC