New package dependency field format

[Adam Heath <doogie@brainfood.com>]

As many of you might know, I've been working on a dpkg rewrite.  So far, I've
been able to limit myself to low-level helper functions.  However, last week,
I started working on the mid-level support routines.  This included the
dependency parser.

The interface to the parser will be a starting pointer, with a length.  The
output will be an rpn stack, which will be simple to evaluate at runtime.

The following is a simplie grammer for the dependency field:

==
/* Whitespace is insignificate between tokens */

<expression>:
	'(' <expression> ')' |
	'!' <expression> |
	<predicate> (<operator> <predicate>)*;
<operator>:
	',' | '|';
<predicate>:
	<arch> |
	<feature> |
	<package>;
<arch>:
	'[' '!'? <arch-name> (',' <arch-name>)* ']';
<feature>:
	'{' <arch-feature> (';' <arch-feature>)* '};
<arch-feature>:
	<arch-name> ':' '!'? <feature-name> (',' '!'? <feature-name>)*;
<package>:
	<package-name> <version>? <arch>? <feature>?
<version>:
	'(' <verop> <version-string> (',' <verop> <version-string>)* ')';

<verop>:
	"<<" | "<=" | '<' |	// < is promoted to <<
	">>" | ">=" | '>' |	// > is promoted to >>
	"!=" | '=';

<package-name>:
	[a-zA-Z_.+-]+;
<arch-name>:
	[a-zA-Z_.+-]+;
<feature-name>:
	[a-zA-Z_.+-]+;
/* The list of disallowed chars should probably be expanded */
<version-string>:
	[^][[:space:]()*]+;
==

Changes from the old format:

	* Addition of != operator.
	* Full nestable parenthetical expression support.
	* arch and feature predicates and package restrictions.
	* Multiple version restrictions on a single package.
	* Inversion support(not operator)

Explanations of new features:

Addition of != operator:

	I hope this one is self explanatory.

Full nestable parenthetical expression support:

	This support is implemented by converting the incoming expression into
	an internal rpn stack.  This allows the dependency checker(not yet
	written) to be simple.

arch and feature predicates and package restrictions:

	The syntax of the arch predicate is the same as it currently is for
	build-depends.  Feature predicates are a combination of an arch name,
	and a list of required or conflicting features.  Each feature name is
	specific to that particular arch.

	dpkg itself will not maintain a list of allowed feature names.
	Instead, the checking of a feature will be delegated to an external
	program.

	An astute observer will note that, strictly speaking, arch predicates
	are superflous.  One could just generate a unique dependency line for
	the target arch when the deb is generated.

Multiple version restrictions on a single package:

	This feature allows for better range support.  Consider the
	following standard line:

	Conflicts: foo (<= 1.2.3), foo (>= 1.2.0)

	This line means that foo 1.2.5 will conflict with the current package,
	even tho the 2 listed predicates might infer otherwise.  However,
	listing it as:

	Conflicts: foo (<= 1.2.3, >= 1.2.0)

	means that the predicate is only true if all the version predicates
	are also true.  This allows for correct range support.

Inversion support(not operator):

	Any predicate or expression can have the sense of it's test inverted,
	by using a preceeding '!'.  In some scenarios, this could be used to
	replace the separate need for Conflicts.