302201 : Unify the two query approaches used in p2

40 files changed, 1349 insertions, 207 deletions

diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/ArtifactKey.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/ArtifactKey.java
index 709fa2b1c..bdd70f866 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/ArtifactKey.java
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/ArtifactKey.java
@@ -10,21 +10,25 @@
  *******************************************************************************/
 package org.eclipse.equinox.internal.p2.metadata;
 
-import org.eclipse.equinox.p2.metadata.Version;
-
 import java.util.ArrayList;
 import java.util.StringTokenizer;
 import org.eclipse.core.runtime.Assert;
 import org.eclipse.equinox.p2.metadata.IArtifactKey;
+import org.eclipse.equinox.p2.metadata.Version;
+import org.eclipse.equinox.p2.metadata.expression.IMemberProvider;
 
 /** 
  * The concrete type for representing IArtifactKey's.
  * <p>
  * See {link IArtifact for a description of the lifecycle of artifact keys) 
  */
-public class ArtifactKey implements IArtifactKey {
+public class ArtifactKey implements IArtifactKey, IMemberProvider {
 	private static final String SEPARATOR = ","; //$NON-NLS-1$
 
+	public static final String MEMBER_ID = "id"; //$NON-NLS-1$
+	public static final String MEMBER_CLASSIFIER = "classifier"; //$NON-NLS-1$
+	public static final String MEMBER_VERSION = "version"; //$NON-NLS-1$
+
 	private final String id;
 	private final String classifier;
 	private final Version version;
@@ -123,4 +127,17 @@ public class ArtifactKey implements IArtifactKey {
 		return data.toString();
 	}
 
+	public Object getMember(String memberName) {
+		// It is OK to use identity comparisons here since
+		// a) All constant valued strings are always interned
+		// b) The Member constructor always interns the name
+		//
+		if (MEMBER_ID == memberName)
+			return id;
+		if (MEMBER_VERSION == memberName)
+			return version;
+		if (MEMBER_CLASSIFIER == memberName)
+			return classifier;
+		throw new IllegalArgumentException();
+	}
 }
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/IUMap.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/IUMap.java
index 3ce2054da..32715828f 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/IUMap.java
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/IUMap.java
@@ -16,7 +16,6 @@ import org.eclipse.equinox.internal.p2.core.helpers.CollectionUtils;
 import org.eclipse.equinox.p2.metadata.IInstallableUnit;
 import org.eclipse.equinox.p2.metadata.Version;
 import org.eclipse.equinox.p2.metadata.query.InstallableUnitQuery;
-import org.eclipse.equinox.p2.query.Collector;
 import org.eclipse.equinox.p2.query.IQueryResult;
 
 /**
@@ -142,16 +141,8 @@ public class IUMap {
 		Iterator<IInstallableUnit> candidates;
 		if (query.getId() == null)
 			candidates = iterator();
-		else {
-			Object bucket = units.get(query.getId());
-			if (bucket == null)
-				return Collector.emptyCollector();
-
-			if (bucket.getClass().isArray())
-				candidates = CollectionUtils.unmodifiableList((IInstallableUnit[]) bucket).iterator();
-			else
-				candidates = Collections.<IInstallableUnit> singletonList((IInstallableUnit) bucket).iterator();
-		}
+		else
+			candidates = getUnits(query.getId()).iterator();
 		return query.perform(candidates);
 
 	}
@@ -160,6 +151,18 @@ public class IUMap {
 		return get(unit.getId(), unit.getVersion()) != null;
 	}
 
+	/**
+	 * Returns a collection of units that has the given <code>id</code>.
+	 * @param id The id of the desired units. Must not be <code>null</code>.
+	 * @return The units corresponding to the given <code>id</code>.
+	 */
+	public Collection<IInstallableUnit> getUnits(String id) {
+		Object bucket = units.get(id);
+		if (bucket == null)
+			return CollectionUtils.emptyList();
+		return bucket.getClass().isArray() ? CollectionUtils.unmodifiableList((IInstallableUnit[]) bucket) : Collections.<IInstallableUnit> singletonList((IInstallableUnit) bucket);
+	}
+
 	public IQueryResult<IInstallableUnit> get(String id) {
 		return internalGet(id, null);
 	}
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/Messages.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/Messages.java
index 0466d2676..654d4c0aa 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/Messages.java
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/Messages.java
@@ -131,6 +131,10 @@ public class Messages extends NLS {
 
 	public static String unbalanced_format_parenthesis;
 
+	public static String no_expression_factory;
+
+	public static String no_expression_parser;
+
 	private static final String BUNDLE_NAME = "org.eclipse.equinox.internal.p2.metadata.messages"; //$NON-NLS-1$
 
 	static {
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/MetadataActivator.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/MetadataActivator.java
index 40881fcc0..686d11de8 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/MetadataActivator.java
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/MetadataActivator.java
@@ -10,23 +10,109 @@
  *******************************************************************************/
 package org.eclipse.equinox.internal.p2.metadata;
 
-import org.osgi.framework.BundleActivator;
-import org.osgi.framework.BundleContext;
+import org.eclipse.core.runtime.IStatus;
+import org.eclipse.core.runtime.Status;
+import org.eclipse.equinox.internal.p2.core.helpers.LogHelper;
+import org.eclipse.equinox.p2.metadata.expression.IExpressionFactory;
+import org.eclipse.equinox.p2.metadata.expression.IExpressionParser;
+import org.osgi.framework.*;
 
 public class MetadataActivator implements BundleActivator {
 	public static final String PI_METADATA = "org.eclipse.equinox.p2.metadata"; //$NON-NLS-1$
-	public static BundleContext context;
+
+	public static final String SERVICE_PRIORITY = "service.priority"; //$NON-NLS-1$
+
+	public static MetadataActivator instance;
+
+	private BundleContext context;
+	private IExpressionFactory expressionFactory;
+	private ServiceReference expressionFactoryReference;
+	private IExpressionParser expressionParser;
+	private ServiceReference expressionParserReference;
 
 	public static BundleContext getContext() {
-		return context;
+		MetadataActivator activator = instance;
+		return activator == null ? null : activator.context;
+	}
+
+	public static IExpressionFactory getExpressionFactory() {
+		MetadataActivator activator = instance;
+		return activator == null ? null : activator._getExpressionFactory();
+	}
+
+	public static IExpressionParser getExpressionParser() {
+		MetadataActivator activator = instance;
+		return activator == null ? null : activator._getExpressionParser();
 	}
 
 	public void start(BundleContext aContext) throws Exception {
-		MetadataActivator.context = aContext;
+		context = aContext;
+		instance = this;
 	}
 
 	public void stop(BundleContext aContext) throws Exception {
-		MetadataActivator.context = null;
+		instance = null;
+
+		if (expressionFactoryReference != null) {
+			aContext.ungetService(expressionFactoryReference);
+			expressionFactoryReference = null;
+			expressionFactory = null;
+		}
+		if (expressionParserReference != null) {
+			aContext.ungetService(expressionParserReference);
+			expressionParserReference = null;
+			expressionParser = null;
+		}
 	}
 
+	private ServiceReference getBestReference(Class<?> serviceInterface) {
+		ServiceReference[] refs;
+		String serviceName = serviceInterface.getName();
+		try {
+			refs = context.getAllServiceReferences(serviceName, null);
+		} catch (InvalidSyntaxException e) {
+			LogHelper.log(new Status(IStatus.ERROR, context.getBundle().getSymbolicName(), "Unable to obtain service references for service " + serviceName, e)); //$NON-NLS-1$
+			return null;
+		}
+
+		if (refs == null)
+			return null;
+
+		ServiceReference best = null;
+		int idx = refs.length;
+		while (--idx >= 0) {
+			ServiceReference ref = refs[idx];
+			if (best == null) {
+				best = ref;
+				continue;
+			}
+			Integer refPrio = (Integer) ref.getProperty(SERVICE_PRIORITY);
+			Integer bestPrio = (Integer) best.getProperty(SERVICE_PRIORITY);
+			if (refPrio == null)
+				continue;
+			if (bestPrio == null || bestPrio.intValue() < refPrio.intValue())
+				best = ref;
+		}
+		return best;
+	}
+
+	private synchronized IExpressionFactory _getExpressionFactory() {
+		if (expressionFactory == null) {
+			expressionFactoryReference = getBestReference(IExpressionFactory.class);
+			if (expressionFactoryReference == null)
+				throw new IllegalStateException(Messages.no_expression_factory);
+			expressionFactory = (IExpressionFactory) context.getService(expressionFactoryReference);
+		}
+		return expressionFactory;
+	}
+
+	private synchronized IExpressionParser _getExpressionParser() {
+		if (expressionParser == null) {
+			expressionParserReference = getBestReference(IExpressionParser.class);
+			if (expressionParserReference == null)
+				throw new IllegalStateException(Messages.no_expression_parser);
+			expressionParser = (IExpressionParser) context.getService(expressionParserReference);
+		}
+		return expressionParser;
+	}
 }
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/RequiredCapability.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/RequiredCapability.java
index 4fcb387fc..7a43439c8 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/RequiredCapability.java
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/RequiredCapability.java
@@ -256,13 +256,21 @@ public class RequiredCapability implements IRequiredCapability, IMemberProvider
 		return new VersionRange(v, expr == range_II_Expression || expr == range_IN_Expression, h, expr == range_II_Expression || expr == range_NI_Expression);
 	}
 
+	public static boolean isSimpleRequirement(IMatchExpression<IInstallableUnit> matchExpression) {
+		return isPredefined(ExpressionUtil.getOperand(matchExpression));
+	}
+
 	private static IExpression assertValid(IMatchExpression<IInstallableUnit> matchExpression) {
 		IExpression expr = ExpressionUtil.getOperand(matchExpression);
-		if (!(expr == allVersionsExpression || expr == range_II_Expression || expr == range_IN_Expression || expr == range_NI_Expression || expr == range_NN_Expression || expr == strictVersionExpression || expr == openEndedExpression || expr == openEndedNonInclusiveExpression))
+		if (!isPredefined(expr))
 			throw new IllegalArgumentException();
 		return expr;
 	}
 
+	private static boolean isPredefined(IExpression expr) {
+		return expr == allVersionsExpression || expr == range_II_Expression || expr == range_IN_Expression || expr == range_NI_Expression || expr == range_NN_Expression || expr == strictVersionExpression || expr == openEndedExpression || expr == openEndedNonInclusiveExpression;
+	}
+
 	public Object getMember(String memberName) {
 		// It is OK to use identity comparisons here since
 		// a) All constant valued strings are always interned
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/TranslationSupport.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/TranslationSupport.java
index e42289040..9f11ef4e3 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/TranslationSupport.java
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/TranslationSupport.java
@@ -193,7 +193,7 @@ public class TranslationSupport {
 
 		SoftReference<IQueryResult<IInstallableUnit>> queryResultReference = localeCollectorCache.get(locale);
 		if (queryResultReference != null) {
-			Collector<IInstallableUnit> cached = (Collector<IInstallableUnit>) queryResultReference.get();
+			IQueryResult<IInstallableUnit> cached = queryResultReference.get();
 			if (cached != null)
 				return cached;
 		}
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/CoercingComparator.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/CoercingComparator.java
index c69e75e32..6a017aea3 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/CoercingComparator.java
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/CoercingComparator.java
@@ -64,7 +64,7 @@ public abstract class CoercingComparator<T> {
 				return (Class<?>) v;
 			if (v instanceof String) {
 				try {
-					return MetadataActivator.context.getBundle().loadClass(((String) v).trim());
+					return MetadataActivator.getContext().getBundle().loadClass(((String) v).trim());
 				} catch (Exception e) {
 					//
 				}
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/CollectionFilter.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/CollectionFilter.java
index bb845d373..f4d320149 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/CollectionFilter.java
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/CollectionFilter.java
@@ -13,6 +13,8 @@ package org.eclipse.equinox.internal.p2.metadata.expression;
 import java.util.Iterator;
 import org.eclipse.equinox.p2.metadata.expression.IEvaluationContext;
 import org.eclipse.equinox.p2.metadata.expression.IExpressionVisitor;
+import org.eclipse.equinox.p2.metadata.index.IIndex;
+import org.eclipse.equinox.p2.metadata.index.IIndexProvider;
 
 /**
  * Some kind of operation that is performed for each element of a collection. I.e.
@@ -51,13 +53,13 @@ public abstract class CollectionFilter extends Unary {
 	}
 
 	public final Object evaluate(IEvaluationContext context) {
-		Iterator<?> lval = operand.evaluateAsIterator(context);
+		Iterator<?> lval = getInnerIterator(context);
 		context = lambda.prolog(context);
 		return evaluate(context, lval);
 	}
 
 	public final Iterator<?> evaluateAsIterator(IEvaluationContext context) {
-		Iterator<?> lval = operand.evaluateAsIterator(context);
+		Iterator<?> lval = getInnerIterator(context);
 		context = lambda.prolog(context);
 		return evaluateAsIterator(context, lval);
 	}
@@ -82,4 +84,47 @@ public abstract class CollectionFilter extends Unary {
 	protected Iterator<?> evaluateAsIterator(IEvaluationContext context, Iterator<?> iterator) {
 		throw new UnsupportedOperationException();
 	}
+
+	private transient IIndexProvider<?> lastIndexProvider;
+	private transient IIndex<?> lastIndex;
+
+	private IIndex<?> getIndex(Class<?> elementClass, IIndexProvider<?> indexProvider) {
+		if (lastIndexProvider == indexProvider)
+			return lastIndex;
+
+		for (String member : getIndexCandidateMembers(elementClass, lambda.getItemVariable(), lambda.getOperand())) {
+			IIndex<?> index = indexProvider.getIndex(member);
+			if (index != null)
+				lastIndex = index;
+		}
+		lastIndexProvider = indexProvider;
+		return lastIndex;
+	}
+
+	protected Iterator<?> getInnerIterator(IEvaluationContext context) {
+		Object collection = operand.evaluate(context);
+		if (collection instanceof Everything<?>) {
+			// Try to find an index
+			//
+			IIndexProvider<?> indexProvider = context.getIndexProvider();
+			if (indexProvider != null) {
+				Class<?> elementClass = ((Everything<?>) collection).getElementClass();
+				IIndex<?> index = getIndex(elementClass, indexProvider);
+				if (index != null) {
+					Iterator<?> indexed = index.getCandidates(context, lambda.getItemVariable(), lambda.getOperand());
+					if (indexed != null)
+						return indexed;
+				}
+			}
+		}
+
+		// No index. We need every element
+		if (collection instanceof IRepeatableIterator<?>)
+			return ((IRepeatableIterator<?>) collection).getCopy();
+
+		Iterator<?> itor = RepeatableIterator.create(collection);
+		if (operand instanceof Variable)
+			((Variable) operand).setValue(context, itor);
+		return itor;
+	}
 }
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/CompoundIterator.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/CompoundIterator.java
new file mode 100644
index 000000000..4aaf2a417
--- /dev/null
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/CompoundIterator.java
@@ -0,0 +1,84 @@
+/*******************************************************************************
+ * Copyright (c) 2009 - 2010 Cloudsmith Inc. and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *     Cloudsmith Inc. - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.equinox.internal.p2.metadata.expression;
+
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+/**
+ * A CompoundIterator will assume that its contained iterator that will produce
+ * elements that in turn can be represented as iterators. The elements of those
+ * iterators will be returned in sequence, thus removing one iterator dimension.
+ * Elements of the contained iterator that are not iterators will be coerced
+ * into iterators using {@link RepeatableIterator#create(Object)}.
+ */
+public class CompoundIterator<T> implements Iterator<T> {
+	private static final Object NO_ELEMENT = new Object();
+	private final Iterator<? extends Object> iteratorIterator;
+	private Iterator<T> currentIterator;
+
+	private T nextObject = noElement();
+
+	/**
+	 * Creates a compound iterator that will iterated over the elements
+	 * of the provided <code>iterator</code>. Each element will be coerced
+	 * into an iterator and its elements in turn are returned
+	 * in succession by the compound iterator.
+	 *
+	 * @param iterator
+	 */
+	public CompoundIterator(Iterator<? extends Object> iterator) {
+		this.iteratorIterator = iterator;
+	}
+
+	public boolean hasNext() {
+		return positionNext();
+	}
+
+	public T next() {
+		if (!positionNext())
+			throw new NoSuchElementException();
+
+		T nxt = nextObject;
+		nextObject = noElement();
+		return nxt;
+	}
+
+	/**
+	 * Remove is not supported by this iterator so calling this method
+	 * will always yield an exception.
+	 * @throws UnsupportedOperationException
+	 */
+	public void remove() {
+		throw new UnsupportedOperationException();
+	}
+
+	@SuppressWarnings("unchecked")
+	private boolean positionNext() {
+		if (nextObject != NO_ELEMENT)
+			return true;
+
+		while (currentIterator == null || !currentIterator.hasNext()) {
+			if (!iteratorIterator.hasNext())
+				return false;
+
+			Object nextItor = iteratorIterator.next();
+			currentIterator = (nextItor instanceof Iterator<?>) ? (Iterator<T>) nextItor : RepeatableIterator.<T> create(nextItor);
+		}
+		nextObject = currentIterator.next();
+		return true;
+	}
+
+	@SuppressWarnings("unchecked")
+	private static <T> T noElement() {
+		return (T) NO_ELEMENT;
+	}
+}
\ No newline at end of file
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/ContextExpression.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/ContextExpression.java
new file mode 100644
index 000000000..ec2394f50
--- /dev/null
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/ContextExpression.java
@@ -0,0 +1,73 @@
+/*******************************************************************************
+ * Copyright (c) 2009 Cloudsmith Inc. and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *     Cloudsmith Inc. - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.equinox.internal.p2.metadata.expression;
+
+import java.util.Iterator;
+import org.eclipse.equinox.p2.metadata.expression.*;
+
+/**
+ * The context expression is the top expression in context queries. It introduces the
+ * variable 'everything' and initialized it with the iterator that represents all
+ * available items.
+ */
+public class ContextExpression<T> extends Unary implements IContextExpression<T> {
+	private static final Object[] noParams = new Object[0];
+	protected final Object[] parameters;
+
+	public ContextExpression(Expression expression, Object[] parameters) {
+		super(expression);
+		this.parameters = parameters == null ? noParams : parameters;
+	}
+
+	public boolean accept(IExpressionVisitor visitor) {
+		return visitor.visit(operand);
+	}
+
+	public void toString(StringBuffer bld, Variable rootVariable) {
+		operand.toString(bld, rootVariable);
+	}
+
+	public IEvaluationContext createContext(Class<T> elementClass, Iterator<T> iterator) {
+		Variable everything = ExpressionFactory.EVERYTHING;
+		IEvaluationContext context = EvaluationContext.create(parameters, everything);
+		context.setValue(everything, new Everything<T>(elementClass, iterator, operand));
+		return context;
+	}
+
+	public int getExpressionType() {
+		return 0;
+	}
+
+	public String getOperator() {
+		throw new UnsupportedOperationException();
+	}
+
+	public int getPriority() {
+		return operand.getPriority();
+	}
+
+	public Object[] getParameters() {
+		return parameters;
+	}
+
+	public int hashCode() {
+		return operand.hashCode();
+	}
+
+	@SuppressWarnings("unchecked")
+	public Iterator<T> iterator(IEvaluationContext context) {
+		return (Iterator<T>) evaluateAsIterator(context);
+	}
+
+	public void toString(StringBuffer bld) {
+		toString(bld, ExpressionFactory.EVERYTHING);
+	}
+}
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/EvaluationContext.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/EvaluationContext.java
index 6048a008a..49e9bbcac 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/EvaluationContext.java
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/EvaluationContext.java
@@ -12,17 +12,18 @@ package org.eclipse.equinox.internal.p2.metadata.expression;
 
 import org.eclipse.equinox.p2.metadata.expression.IEvaluationContext;
 import org.eclipse.equinox.p2.metadata.expression.IExpression;
+import org.eclipse.equinox.p2.metadata.index.IIndexProvider;
 
 /**
  * Highly specialized evaluation contexts optimized for misc purposes
  */
 public class EvaluationContext implements IEvaluationContext {
-	static class SingleVariableContext extends EvaluationContext {
+	public static class SingleVariableContext extends EvaluationContext {
 		private Object value;
 
 		private final IExpression variable;
 
-		public SingleVariableContext(IEvaluationContext parentContext, IExpression variable, Object[] parameters) {
+		public SingleVariableContext(EvaluationContext parentContext, IExpression variable, Object[] parameters) {
 			super(parentContext, parameters);
 			this.variable = variable;
 		}
@@ -39,10 +40,10 @@ public class EvaluationContext implements IEvaluationContext {
 		}
 	}
 
-	static class MultiVariableContext extends EvaluationContext {
+	public static class MultiVariableContext extends EvaluationContext {
 		private final Object[] values;
 
-		public MultiVariableContext(IEvaluationContext parentContext, IExpression[] variables, Object[] parameters) {
+		public MultiVariableContext(EvaluationContext parentContext, IExpression[] variables, Object[] parameters) {
 			super(parentContext, parameters);
 			values = new Object[variables.length * 2];
 			for (int idx = 0, ndx = 0; ndx < variables.length; ++ndx, idx += 2)
@@ -75,7 +76,7 @@ public class EvaluationContext implements IEvaluationContext {
 	}
 
 	public static IEvaluationContext create(IEvaluationContext parent, IExpression variable) {
-		return new SingleVariableContext(parent, variable, ((EvaluationContext) parent).parameters);
+		return new SingleVariableContext((EvaluationContext) parent, variable, ((EvaluationContext) parent).parameters);
 	}
 
 	public static IEvaluationContext create(IEvaluationContext parent, IExpression[] variables) {
@@ -87,13 +88,13 @@ public class EvaluationContext implements IEvaluationContext {
 			return create(parent, parameters);
 		if (parameters == null)
 			parameters = noParameters;
-		return variables.length == 1 ? new SingleVariableContext(parent, variables[0], parameters) : new MultiVariableContext(parent, variables, parameters);
+		return variables.length == 1 ? new SingleVariableContext((EvaluationContext) parent, variables[0], parameters) : new MultiVariableContext((EvaluationContext) parent, variables, parameters);
 	}
 
 	public static IEvaluationContext create(IEvaluationContext parent, Object[] parameters) {
 		if (parameters == null)
 			parameters = noParameters;
-		return new EvaluationContext(parent, parameters);
+		return new EvaluationContext((EvaluationContext) parent, parameters);
 	}
 
 	public static IEvaluationContext create(IExpression variable) {
@@ -114,11 +115,13 @@ public class EvaluationContext implements IEvaluationContext {
 		return create(INSTANCE, parameters, variables);
 	}
 
-	final IEvaluationContext parentContext;
+	final EvaluationContext parentContext;
 
 	private final Object[] parameters;
 
-	EvaluationContext(IEvaluationContext parentContext, Object[] parameters) {
+	private IIndexProvider<?> indexProvider;
+
+	EvaluationContext(EvaluationContext parentContext, Object[] parameters) {
 		this.parentContext = parentContext;
 		this.parameters = parameters;
 	}
@@ -138,4 +141,17 @@ public class EvaluationContext implements IEvaluationContext {
 			throw new IllegalArgumentException("No such variable: " + variable); //$NON-NLS-1$
 		parentContext.setValue(variable, value);
 	}
+
+	public IIndexProvider<?> getIndexProvider() {
+		if (indexProvider == null) {
+			if (parentContext == null)
+				return null;
+			return parentContext.getIndexProvider();
+		}
+		return indexProvider;
+	}
+
+	public void setIndexProvider(IIndexProvider<?> indexProvider) {
+		this.indexProvider = indexProvider;
+	}
 }
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/Everything.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/Everything.java
new file mode 100644
index 000000000..ebdb720b8
--- /dev/null
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/Everything.java
@@ -0,0 +1,95 @@
+/*******************************************************************************
+ * Copyright (c) 2009 Cloudsmith Inc. and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *     Cloudsmith Inc. - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.equinox.internal.p2.metadata.expression;
+
+import java.util.Collection;
+import java.util.Iterator;
+import org.eclipse.equinox.internal.p2.core.helpers.CollectionUtils;
+import org.eclipse.equinox.p2.metadata.expression.IExpression;
+import org.eclipse.equinox.p2.metadata.expression.IExpressionVisitor;
+import org.eclipse.equinox.p2.metadata.index.IIndexProvider;
+
+/**
+ * The immutable context used when evaluating an expression.
+ */
+public final class Everything<T> extends MatchIteratorFilter<T> implements IRepeatableIterator<T> {
+	private boolean atStart = true;
+
+	private final Class<T> elementClass;
+
+	public Everything(Class<T> elementClass, Collection<T> collection) {
+		super(RepeatableIterator.<T> create(collection == null ? CollectionUtils.<T> emptyList() : collection));
+		this.elementClass = elementClass;
+	}
+
+	public Everything(Class<T> elementClass, Iterator<? extends T> iterator, Expression expression) {
+		this(elementClass, iterator, needsRepeadedAccessToEverything(expression));
+	}
+
+	public Everything(Class<T> elementClass, IIndexProvider<? extends T> indexProvider) {
+		super(RepeatableIterator.<T> create(indexProvider));
+		this.elementClass = elementClass;
+	}
+
+	Everything(Class<T> elementClass, Iterator<? extends T> iterator, boolean needsRepeat) {
+		super(needsRepeat ? RepeatableIterator.create(iterator) : iterator);
+		this.elementClass = elementClass;
+	}
+
+	public IRepeatableIterator<T> getCopy() {
+		Iterator<? extends T> iterator = getInnerIterator();
+		if (iterator instanceof IRepeatableIterator<?>)
+			return new Everything<T>(elementClass, ((IRepeatableIterator<? extends T>) iterator).getCopy(), false);
+		if (atStart)
+			return this;
+		throw new UnsupportedOperationException();
+	}
+
+	public T next() {
+		atStart = false;
+		return super.next();
+	}
+
+	public Class<T> getElementClass() {
+		return elementClass;
+	}
+
+	public Object getIteratorProvider() {
+		Iterator<? extends T> iterator = getInnerIterator();
+		if (iterator instanceof IRepeatableIterator<?>)
+			return ((IRepeatableIterator<?>) iterator).getIteratorProvider();
+		return this;
+	}
+
+	protected boolean isMatch(T val) {
+		return elementClass.isInstance(val);
+	}
+
+	/**
+	 * Checks if the expression will make repeated requests for the 'everything' iterator.
+	 * @return <code>true</code> if repeated requests will be made, <code>false</code> if not.
+	 */
+	private static boolean needsRepeadedAccessToEverything(Expression expression) {
+		final boolean[] repeatedAccessNeeded = new boolean[] {false};
+		expression.accept(new IExpressionVisitor() {
+			public boolean visit(IExpression expr) {
+				// FIXME Needs proper counting
+				if (expr == ExpressionFactory.EVERYTHING) {
+					repeatedAccessNeeded[0] = true;
+					return false;
+				}
+				return true;
+			}
+		});
+		// return repeatedAccessNeeded[0];
+		return true;
+	}
+}
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/Expression.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/Expression.java
index 75f47dd94..767f7c1e7 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/Expression.java
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/Expression.java
@@ -11,6 +11,8 @@
 package org.eclipse.equinox.internal.p2.metadata.expression;
 
 import java.util.*;
+import org.eclipse.equinox.internal.p2.metadata.InstallableUnit;
+import org.eclipse.equinox.p2.metadata.IInstallableUnit;
 import org.eclipse.equinox.p2.metadata.expression.*;
 
 /**
@@ -93,6 +95,12 @@ public abstract class Expression implements IExpression, Comparable<Expression>,
 		}
 	}
 
+	public static Collection<String> getIndexCandidateMembers(Class<?> elementClass, Variable itemVariable, Expression operand) {
+		MembersFinder finder = new MembersFinder(elementClass, itemVariable);
+		operand.accept(finder);
+		return finder.getMembers();
+	}
+
 	/**
 	 * Let the visitor visit this instance and all expressions that this
 	 * instance contains.
@@ -264,6 +272,45 @@ public abstract class Expression implements IExpression, Comparable<Expression>,
 		}
 	}
 
+	private static class MembersFinder implements IExpressionVisitor {
+		private final ArrayList<String> members = new ArrayList<String>();
+		private final Class<?> elementClass;
+		private final IExpression operand;
+
+		MembersFinder(Class<?> elementClass, IExpression operand) {
+			this.elementClass = elementClass;
+			this.operand = operand;
+		}
+
+		public boolean visit(IExpression expression) {
+			if (expression instanceof Member) {
+				Member member = (Member) expression;
+				if (member.getOperand() == operand) {
+					String name = member.getName();
+					if (!members.contains(name))
+						members.add(member.getName());
+					return false;
+				}
+			} else if (expression instanceof Matches && IInstallableUnit.class.isAssignableFrom(elementClass)) {
+				// This one is a bit special since an
+				// IInstallableUnit ~= IRequirement often
+				// means that we can reuse the requirement
+				// expression.
+				Matches matches = (Matches) expression;
+				if (matches.lhs == operand) {
+					if (!members.contains(InstallableUnit.MEMBER_PROVIDED_CAPABILITIES))
+						members.add(InstallableUnit.MEMBER_PROVIDED_CAPABILITIES);
+					return false;
+				}
+			}
+			return true;
+		}
+
+		Collection<String> getMembers() {
+			return members;
+		}
+	}
+
 	static Expression addFilter(Expression base, Expression subFilter, int expressionType) {
 		if (base.equals(subFilter))
 			return base;
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/ExpressionFactory.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/ExpressionFactory.java
index f87c1c129..fc0ab18d5 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/ExpressionFactory.java
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/ExpressionFactory.java
@@ -6,6 +6,7 @@ import org.eclipse.equinox.p2.metadata.expression.*;
 public class ExpressionFactory implements IExpressionFactory, IExpressionConstants {
 	public static final IExpressionFactory INSTANCE = new ExpressionFactory();
 	public static final Variable THIS = new Variable(VARIABLE_THIS);
+	public static final Variable EVERYTHING = new Variable(VARIABLE_EVERYTHING);
 
 	protected static Expression[] convertArray(IExpression[] operands) {
 		Expression[] ops = new Expression[operands.length];
@@ -13,10 +14,6 @@ public class ExpressionFactory implements IExpressionFactory, IExpressionConstan
 		return ops;
 	}
 
-	protected ExpressionFactory() {
-		// Maintain singleton
-	}
-
 	public IExpression all(IExpression collection, IExpression lambda) {
 		return new All((Expression) collection, (LambdaExpression) lambda);
 	}
@@ -50,6 +47,10 @@ public class ExpressionFactory implements IExpressionFactory, IExpressionConstan
 		return EvaluationContext.create(parameters, variables);
 	}
 
+	public <T> IContextExpression<T> contextExpression(IExpression expr, Object... parameters) {
+		return new ContextExpression<T>((Expression) expr, parameters);
+	}
+
 	public IFilterExpression filterExpression(IExpression expression) {
 		return new LDAPFilter((Expression) expression);
 	}
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/MatchIteratorFilter.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/MatchIteratorFilter.java
new file mode 100644
index 000000000..8d21ed8f7
--- /dev/null
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/MatchIteratorFilter.java
@@ -0,0 +1,71 @@
+/*******************************************************************************
+ * Copyright (c) 2009 - 2010 Cloudsmith Inc. and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *     Cloudsmith Inc. - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.equinox.internal.p2.metadata.expression;
+
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+/**
+ * An iterator filter using a boolean {@link #isMatch(Object)} method.
+ */
+public abstract class MatchIteratorFilter<T> implements Iterator<T> {
+	private static final Object NO_ELEMENT = new Object();
+
+	private final Iterator<? extends T> innerIterator;
+
+	private T nextObject = noElement();
+
+	public MatchIteratorFilter(Iterator<? extends T> iterator) {
+		this.innerIterator = iterator;
+	}
+
+	public boolean hasNext() {
+		return positionNext();
+	}
+
+	public T next() {
+		if (!positionNext())
+			throw new NoSuchElementException();
+
+		T nxt = nextObject;
+		nextObject = noElement();
+		return nxt;
+	}
+
+	public void remove() {
+		throw new UnsupportedOperationException();
+	}
+
+	protected Iterator<? extends T> getInnerIterator() {
+		return innerIterator;
+	}
+
+	protected abstract boolean isMatch(T val);
+
+	private boolean positionNext() {
+		if (nextObject != NO_ELEMENT)
+			return true;
+
+		while (innerIterator.hasNext()) {
+			T nxt = innerIterator.next();
+			if (isMatch(nxt)) {
+				nextObject = nxt;
+				return true;
+			}
+		}
+		return false;
+	}
+
+	@SuppressWarnings("unchecked")
+	private static <T> T noElement() {
+		return (T) NO_ELEMENT;
+	}
+}
\ No newline at end of file
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/RepeatableIterator.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/RepeatableIterator.java
index e44a4e507..b7325286c 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/RepeatableIterator.java
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/RepeatableIterator.java
@@ -11,6 +11,7 @@
 package org.eclipse.equinox.internal.p2.metadata.expression;
 
 import java.util.*;
+import org.eclipse.equinox.p2.metadata.index.IIndexProvider;
 import org.eclipse.equinox.p2.query.IQueryResult;
 
 public class RepeatableIterator<T> implements IRepeatableIterator<T> {
@@ -121,14 +122,33 @@ public class RepeatableIterator<T> implements IRepeatableIterator<T> {
 		}
 	}
 
-	static class CollectionIterator<T> implements IRepeatableIterator<T> {
-		private final Collection<T> collection;
+	static abstract class DeferredIterator<T> implements IRepeatableIterator<T> {
+		private Iterator<T> iterator;
 
-		private final Iterator<T> iterator;
+		public boolean hasNext() {
+			if (iterator == null)
+				iterator = getIterator();
+			return iterator.hasNext();
+		}
+
+		public T next() {
+			if (iterator == null)
+				iterator = getIterator();
+			return iterator.next();
+		}
+
+		public void remove() {
+			throw new UnsupportedOperationException();
+		}
+
+		abstract Iterator<T> getIterator();
+	}
+
+	static class CollectionIterator<T> extends DeferredIterator<T> {
+		private final Collection<T> collection;
 
 		CollectionIterator(Collection<T> collection) {
 			this.collection = collection;
-			this.iterator = collection.iterator();
 		}
 
 		public IRepeatableIterator<T> getCopy() {
@@ -139,16 +159,28 @@ public class RepeatableIterator<T> implements IRepeatableIterator<T> {
 			return collection;
 		}
 
-		public boolean hasNext() {
-			return iterator.hasNext();
+		Iterator<T> getIterator() {
+			return collection.iterator();
 		}
+	}
 
-		public T next() {
-			return iterator.next();
+	static class IndexProviderIterator<T> extends DeferredIterator<T> {
+		private final IIndexProvider<T> indexProvider;
+
+		IndexProviderIterator(IIndexProvider<T> indexProvider) {
+			this.indexProvider = indexProvider;
 		}
 
-		public void remove() {
-			throw new UnsupportedOperationException();
+		public IRepeatableIterator<T> getCopy() {
+			return new IndexProviderIterator<T>(indexProvider);
+		}
+
+		public Object getIteratorProvider() {
+			return indexProvider;
+		}
+
+		Iterator<T> getIterator() {
+			return indexProvider.everything();
 		}
 	}
 
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/parser/ExpressionParser.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/parser/ExpressionParser.java
index 905d0927c..322299ffc 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/parser/ExpressionParser.java
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/parser/ExpressionParser.java
@@ -10,10 +10,10 @@
  *******************************************************************************/
 package org.eclipse.equinox.internal.p2.metadata.expression.parser;
 
-import org.eclipse.equinox.internal.p2.metadata.expression.LDAPApproximation;
-
 import java.util.*;
+import org.eclipse.equinox.internal.p2.metadata.MetadataActivator;
 import org.eclipse.equinox.internal.p2.metadata.expression.IExpressionConstants;
+import org.eclipse.equinox.internal.p2.metadata.expression.LDAPApproximation;
 import org.eclipse.equinox.p2.metadata.expression.*;
 
 public class ExpressionParser extends Stack<IExpression> implements IExpressionConstants, IExpressionParser {
@@ -77,8 +77,8 @@ public class ExpressionParser extends Stack<IExpression> implements IExpressionC
 	protected Object tokenValue;
 	protected String rootVariable;
 
-	public ExpressionParser(IExpressionFactory factory) {
-		this.factory = factory;
+	public ExpressionParser() {
+		factory = MetadataActivator.getExpressionFactory();
 	}
 
 	public synchronized IExpression parse(String exprString) {
@@ -100,6 +100,24 @@ public class ExpressionParser extends Stack<IExpression> implements IExpressionC
 		}
 	}
 
+	public synchronized IExpression parseQuery(String exprString) {
+		expression = exprString;
+		tokenPos = 0;
+		currentToken = 0;
+		tokenValue = null;
+		rootVariable = VARIABLE_EVERYTHING;
+		IExpression everythingVariable = factory.variable(VARIABLE_EVERYTHING);
+		push(everythingVariable);
+		try {
+			nextToken();
+			IExpression expr = parseCondition();
+			assertToken(TOKEN_END);
+			return expr;
+		} finally {
+			popVariable(); // pop context
+		}
+	}
+
 	protected Map<String, Integer> keywordToTokenMap() {
 		return keywords;
 	}
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/index/CapabilityIndex.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/index/CapabilityIndex.java
new file mode 100644
index 000000000..a26fd3034
--- /dev/null
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/index/CapabilityIndex.java
@@ -0,0 +1,204 @@
+/*******************************************************************************
+ * Copyright (c) 2010 Cloudsmith Inc. and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *     Cloudsmith Inc. - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.equinox.internal.p2.metadata.index;
+
+import java.util.*;
+import org.eclipse.equinox.internal.p2.core.helpers.CollectionUtils;
+import org.eclipse.equinox.internal.p2.metadata.*;
+import org.eclipse.equinox.internal.p2.metadata.expression.*;
+import org.eclipse.equinox.p2.metadata.*;
+import org.eclipse.equinox.p2.metadata.expression.*;
+
+/**
+ * An in-memory implementation of a CapabilityIndex based on a Map.
+ */
+@SuppressWarnings("unchecked")
+public class CapabilityIndex extends Index<IInstallableUnit> {
+
+	private final Map<String, Object> capabilityMap;
+
+	public CapabilityIndex(Iterator<IInstallableUnit> itor) {
+		HashMap<String, Object> index = new HashMap<String, Object>(300);
+		while (itor.hasNext()) {
+			IInstallableUnit iu = itor.next();
+			Collection<IProvidedCapability> pcs = iu.getProvidedCapabilities();
+			for (IProvidedCapability pc : pcs) {
+				String name = pc.getName();
+				Object prev = index.put(name, iu);
+				if (prev == null || prev == iu)
+					continue;
+
+				ArrayList<IInstallableUnit> list;
+				if (prev instanceof IInstallableUnit) {
+					list = new ArrayList<IInstallableUnit>();
+					list.add((IInstallableUnit) prev);
+				} else
+					list = (ArrayList<IInstallableUnit>) prev;
+				list.add(iu);
+				index.put(name, list);
+			}
+		}
+		this.capabilityMap = index;
+	}
+
+	private Object getRequirementIDs(IEvaluationContext ctx, IExpression requirement, Object queriedKeys) {
+		switch (requirement.getExpressionType()) {
+			case IExpression.TYPE_AND :
+				// AND is OK if at least one of the branches require the queried key
+				for (IExpression expr : ExpressionUtil.getOperands(requirement)) {
+					Object test = getRequirementIDs(ctx, expr, queriedKeys);
+					if (test != null) {
+						if (test == Boolean.FALSE)
+							// Failing exists so the AND will fail altogether
+							return test;
+
+						// It's safe to break here since an and'ing several queries
+						// for different keys and the same input will yield false anyway.
+						return test;
+					}
+				}
+				return null;
+
+			case IExpression.TYPE_OR :
+				// OR is OK if all the branches require the queried key
+				for (IExpression expr : ExpressionUtil.getOperands(requirement)) {
+					Object test = getRequirementIDs(ctx, expr, queriedKeys);
+					if (test == null)
+						// This branch did not require the key so index cannot be used
+						return null;
+
+					if (test == Boolean.FALSE)
+						// Branch will always fail regardless of input, so just ignore
+						continue;
+
+					queriedKeys = test;
+				}
+				return queriedKeys;
+
+			case IExpression.TYPE_ALL :
+			case IExpression.TYPE_EXISTS :
+				CollectionFilter cf = (CollectionFilter) requirement;
+				if (isIndexedMember(cf.getOperand(), ExpressionFactory.THIS, InstallableUnit.MEMBER_PROVIDED_CAPABILITIES)) {
+					LambdaExpression lambda = cf.lambda;
+					return getQueriedIDs(ctx, lambda.getItemVariable(), ProvidedCapability.MEMBER_NAME, lambda.getOperand(), queriedKeys);
+				}
+		}
+		return null;
+	}
+
+	@Override
+	protected Object getQueriedIDs(IEvaluationContext ctx, IExpression variable, String memberName, IExpression booleanExpr, Object queriedKeys) {
+		if (booleanExpr.getExpressionType() != IExpression.TYPE_MATCHES)
+			return super.getQueriedIDs(ctx, variable, memberName, booleanExpr, queriedKeys);
+
+		Matches matches = (Matches) booleanExpr;
+		if (matches.lhs != variable)
+			return null;
+
+		Object rhsObj = matches.rhs.evaluate(ctx);
+		if (!(rhsObj instanceof IRequirement))
+			return null;
+
+		// Let the requirement expression participate in the
+		// index usage query
+		//
+		IMatchExpression<IInstallableUnit> rm = ((IRequirement) rhsObj).getMatches();
+		return RequiredCapability.isSimpleRequirement(rm) ? concatenateUnique(queriedKeys, rm.getParameters()[0]) : getRequirementIDs(rm.createContext(), ((Unary) rm).operand, queriedKeys);
+	}
+
+	public Iterator<IInstallableUnit> getCandidates(IEvaluationContext ctx, IExpression variable, IExpression booleanExpr) {
+		Object queriedKeys = null;
+
+		// booleanExpression must be a collection filter on providedCapabilities
+		// or an IInstallableUnit used in a match expression.
+		//
+		IExpression expr = booleanExpr;
+		int type = booleanExpr.getExpressionType();
+		if (type == 0) {
+			// wrapper
+			expr = ((Unary) booleanExpr).operand;
+			type = expr.getExpressionType();
+		}
+
+		switch (type) {
+			case IExpression.TYPE_ALL :
+			case IExpression.TYPE_EXISTS :
+				CollectionFilter cf = (CollectionFilter) expr;
+				if (isIndexedMember(cf.getOperand(), variable, InstallableUnit.MEMBER_PROVIDED_CAPABILITIES)) {
+					// This is providedCapabilities.exists or providedCapabilites.all
+					//
+					LambdaExpression lambda = cf.lambda;
+					queriedKeys = getQueriedIDs(ctx, lambda.getItemVariable(), ProvidedCapability.MEMBER_NAME, lambda.getOperand(), queriedKeys);
+				} else {
+					// Might be the requiredCapabilities array.
+					//
+					Expression op = cf.getOperand();
+					if (op instanceof Member && InstallableUnit.MEMBER_REQUIRED_CAPABILITIES.equals(((Member) op).getName())) {
+						queriedKeys = getQueriedIDs(ctx, variable, ProvidedCapability.MEMBER_NAME, booleanExpr, queriedKeys);
+					}
+				}
+				break;
+
+			case IExpression.TYPE_MATCHES :
+				Matches matches = (Matches) expr;
+				if (matches.lhs != variable)
+					break;
+
+				Object rhsObj = matches.rhs.evaluate(ctx);
+				if (!(rhsObj instanceof IRequirement))
+					break;
+
+				// Let the requirement expression participate in the
+				// index usage query
+				//
+				IMatchExpression<IInstallableUnit> rm = ((IRequirement) rhsObj).getMatches();
+				queriedKeys = RequiredCapability.isSimpleRequirement(rm) ? concatenateUnique(queriedKeys, rm.getParameters()[0]) : getRequirementIDs(rm.createContext(), ((Unary) rm).operand, queriedKeys);
+				break;
+
+			default :
+				queriedKeys = null;
+		}
+
+		if (queriedKeys == null)
+			// Index cannot be used.
+			return null;
+
+		Collection<IInstallableUnit> matchingIUs;
+		if (queriedKeys == Boolean.FALSE) {
+			// It has been determined that the expression has no chance
+			// to succeed regardless of input
+			matchingIUs = CollectionUtils.<IInstallableUnit> emptySet();
+		} else if (queriedKeys instanceof Collection<?>) {
+			matchingIUs = new HashSet<IInstallableUnit>();
+			for (Object key : (Collection<Object>) queriedKeys)
+				collectMatchingIUs((String) key, matchingIUs);
+		} else {
+			Object v = capabilityMap.get(queriedKeys);
+			if (v == null)
+				matchingIUs = CollectionUtils.<IInstallableUnit> emptySet();
+			else if (v instanceof IInstallableUnit)
+				matchingIUs = Collections.singleton((IInstallableUnit) v);
+			else
+				matchingIUs = (Collection<IInstallableUnit>) v;
+		}
+		return matchingIUs.iterator();
+	}
+
+	private void collectMatchingIUs(String name, Collection<IInstallableUnit> collector) {
+		Object v = capabilityMap.get(name);
+		if (v == null)
+			return;
+		if (v instanceof IInstallableUnit)
+			collector.add((IInstallableUnit) v);
+		else
+			collector.addAll((Collection<IInstallableUnit>) v);
+	}
+}
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/index/IdIndex.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/index/IdIndex.java
new file mode 100644
index 000000000..a415e8ca4
--- /dev/null
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/index/IdIndex.java
@@ -0,0 +1,46 @@
+/*******************************************************************************
+ * Copyright (c) 2010 Cloudsmith Inc. and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *     Cloudsmith Inc. - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.equinox.internal.p2.metadata.index;
+
+import java.util.*;
+import org.eclipse.equinox.internal.p2.metadata.IUMap;
+import org.eclipse.equinox.internal.p2.metadata.InstallableUnit;
+import org.eclipse.equinox.p2.metadata.IInstallableUnit;
+import org.eclipse.equinox.p2.metadata.expression.IEvaluationContext;
+import org.eclipse.equinox.p2.metadata.expression.IExpression;
+
+public class IdIndex extends Index<IInstallableUnit> {
+	private final IUMap iuMap;
+
+	public IdIndex(IUMap iuMap) {
+		this.iuMap = iuMap;
+	}
+
+	public IdIndex(Iterator<IInstallableUnit> ius) {
+		iuMap = new IUMap();
+		while (ius.hasNext())
+			iuMap.add(ius.next());
+	}
+
+	public Iterator<IInstallableUnit> getCandidates(IEvaluationContext ctx, IExpression variable, IExpression booleanExpr) {
+		Object queriedKeys = getQueriedIDs(ctx, variable, InstallableUnit.MEMBER_ID, booleanExpr, null);
+		if (queriedKeys == null)
+			return null;
+
+		if (queriedKeys instanceof Collection<?>) {
+			HashSet<IInstallableUnit> collector = new HashSet<IInstallableUnit>();
+			for (Object key : (Collection<?>) queriedKeys)
+				collector.addAll(iuMap.getUnits((String) key));
+			return collector.iterator();
+		}
+		return iuMap.getUnits((String) queriedKeys).iterator();
+	}
+}
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/index/Index.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/index/Index.java
new file mode 100644
index 000000000..3c509bff2
--- /dev/null
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/index/Index.java
@@ -0,0 +1,123 @@
+/*******************************************************************************
+ * Copyright (c) 2010 Cloudsmith Inc. and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *     Cloudsmith Inc. - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.equinox.internal.p2.metadata.index;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import org.eclipse.equinox.internal.p2.metadata.expression.*;
+import org.eclipse.equinox.p2.metadata.expression.*;
+import org.eclipse.equinox.p2.metadata.index.IIndex;
+
+public abstract class Index<T> implements IIndex<T> {
+
+	protected static boolean isIndexedMember(IExpression expr, IExpression variable, String memberName) {
+		if (expr instanceof Member) {
+			Member member = (Member) expr;
+			return member.getOperand() == variable && member.getName().equals(memberName);
+		}
+		return false;
+	}
+
+	protected static Object concatenateUnique(Object previous, Object toAdd) {
+		if (previous == null || toAdd == null || toAdd == Boolean.FALSE)
+			return toAdd;
+
+		if (previous instanceof ArrayList<?>) {
+			@SuppressWarnings("unchecked")
+			ArrayList<Object> prevArr = (ArrayList<Object>) previous;
+			if (!prevArr.contains(toAdd))
+				prevArr.add(toAdd);
+			return previous;
+		}
+		if (previous.equals(toAdd))
+			return previous;
+
+		ArrayList<Object> arr = new ArrayList<Object>();
+		arr.add(previous);
+		arr.add(toAdd);
+		return arr;
+	}
+
+	protected Object getQueriedIDs(IEvaluationContext ctx, IExpression variable, String memberName, IExpression booleanExpr, Object queriedKeys) {
+		int type = booleanExpr.getExpressionType();
+		switch (type) {
+			case IExpression.TYPE_EQUALS :
+				Binary eqExpr = (Binary) booleanExpr;
+				IExpression lhs = eqExpr.lhs;
+				IExpression rhs = eqExpr.rhs;
+				if (isIndexedMember(lhs, variable, memberName))
+					return concatenateUnique(queriedKeys, rhs.evaluate(ctx));
+				if (isIndexedMember(rhs, variable, memberName))
+					return concatenateUnique(queriedKeys, lhs.evaluate(ctx));
+
+				// Not applicable for indexing
+				return null;
+
+			case IExpression.TYPE_AND :
+				// AND is OK if at least one of the branches require the queried key
+				for (IExpression expr : ExpressionUtil.getOperands(booleanExpr)) {
+					Object test = getQueriedIDs(ctx, variable, memberName, expr, queriedKeys);
+					if (test != null) {
+						if (test == Boolean.FALSE)
+							// Failing exists so the AND will fail altogether
+							return test;
+
+						// It's safe to break here since an and'ing several queries
+						// for different keys and the same input will yield false anyway.
+						return test;
+					}
+				}
+				return null;
+
+			case IExpression.TYPE_OR :
+				// OR is OK if all the branches require the queried key
+				for (IExpression expr : ExpressionUtil.getOperands(booleanExpr)) {
+					Object test = getQueriedIDs(ctx, variable, memberName, expr, queriedKeys);
+					if (test == null)
+						// This branch did not require the key so index cannot be used
+						return null;
+
+					if (test == Boolean.FALSE)
+						// Branch will always fail regardless of input, so just ignore
+						continue;
+
+					queriedKeys = test;
+				}
+				return queriedKeys;
+
+			case IExpression.TYPE_EXISTS :
+			case IExpression.TYPE_ALL :
+				// We must evaluate the lhs to find the referenced keys
+				//
+				CollectionFilter cf = (CollectionFilter) booleanExpr;
+				Iterator<?> values = cf.getOperand().evaluateAsIterator(ctx);
+				if (!values.hasNext())
+					// No keys are requested but we know that an exists must
+					// fail at this point. An all will however succeed regardless
+					// of what is used as input.
+					return type == IExpression.TYPE_ALL ? null : Boolean.FALSE;
+
+				LambdaExpression lambda = cf.lambda;
+				IEvaluationContext lambdaCtx = lambda.prolog(ctx);
+				Variable lambdaVar = lambda.getItemVariable();
+				IExpression filterExpr = lambda.getOperand();
+				do {
+					lambdaVar.setValue(lambdaCtx, values.next());
+					queriedKeys = getQueriedIDs(lambdaCtx, variable, memberName, filterExpr, queriedKeys);
+					if (queriedKeys == null)
+						// No use continuing. The expression does not require the key
+						return null;
+				} while (values.hasNext());
+				return queriedKeys;
+		}
+		return null;
+	}
+}
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/messages.properties b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/messages.properties
index a70676f45..540b61526 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/messages.properties
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/messages.properties
@@ -48,6 +48,8 @@ only_format_specified_0=Only a format was specified: {0}
 only_max_and_empty_string_defaults_can_have_translations=Only max string and empty string defaults can have translations
 original_must_start_with_colon_0=Original version must start with colon: {0}
 original_stated_but_missing_0=Expected original version after colon: {0}
+no_expression_factory=No Expression Factory service has been registered
+no_expression_parser=No Expression Parser service has been registered
 pad_defined_more_then_once=Pad was defined more then once
 performing_subquery=Performing subquery
 premature_end_of_format=Premature end of format
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/query/IUPropertyQuery.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/query/IUPropertyQuery.java
index 95f3f3375..1013e91aa 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/query/IUPropertyQuery.java
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/query/IUPropertyQuery.java
@@ -11,38 +11,39 @@
 package org.eclipse.equinox.internal.p2.metadata.query;
 
 import org.eclipse.equinox.p2.metadata.IInstallableUnit;
-import org.eclipse.equinox.p2.query.MatchQuery;
+import org.eclipse.equinox.p2.metadata.expression.*;
+import org.eclipse.equinox.p2.metadata.query.ExpressionQuery;
 
 /**
  * A query that searches for {@link IInstallableUnit} instances that have
  * a property whose value matches the provided value.  If no property name is 
  * specified, then all {@link IInstallableUnit} instances are accepted.
  */
-public class IUPropertyQuery extends MatchQuery<IInstallableUnit> {
-	private String propertyName;
-	private String propertyValue;
+public final class IUPropertyQuery extends ExpressionQuery<IInstallableUnit> {
+	public static final String ANY = "*"; //$NON-NLS-1$
 
-	/**
-	 * Creates a new query on the given property name and value.
-	 */
-	public IUPropertyQuery(String propertyName, String propertyValue) {
-		this.propertyName = propertyName;
-		this.propertyValue = propertyValue;
-	}
+	private static final IExpression matchTrueExpression = ExpressionUtil.parse("properties[$0] == true"); //$NON-NLS-1$
+	private static final IExpression matchNullExpression = ExpressionUtil.parse("properties[$0] == null"); //$NON-NLS-1$
+	private static final IExpression matchAnyExpression = ExpressionUtil.parse("properties[$0] != null"); //$NON-NLS-1$
+	private static final IExpression matchValueExpression = ExpressionUtil.parse("properties[$0] == $1"); //$NON-NLS-1$
 
-	/* (non-Javadoc)
-	 * @see org.eclipse.equinox.p2.query2.Query#isMatch(java.lang.Object)
-	 */
-	public boolean isMatch(IInstallableUnit candidate) {
+	public static IMatchExpression<IInstallableUnit> createMatchExpression(String propertyName, String propertyValue) {
+		IExpressionFactory factory = ExpressionUtil.getFactory();
 		if (propertyName == null)
-			return true;
-		String value = getProperty(candidate, propertyName);
-		if (value != null && (value.equals(propertyValue) || propertyValue == null))
-			return true;
-		return false;
+			return MATCH_ALL_UNITS;
+		if (propertyValue == null)
+			return factory.<IInstallableUnit> matchExpression(matchNullExpression, propertyName);
+		if (ANY.equals(propertyValue))
+			return factory.<IInstallableUnit> matchExpression(matchAnyExpression, propertyName);
+		if (Boolean.valueOf(propertyValue).booleanValue())
+			return factory.<IInstallableUnit> matchExpression(matchTrueExpression, propertyName);
+		return factory.<IInstallableUnit> matchExpression(matchValueExpression, propertyName, propertyValue);
 	}
 
-	protected String getProperty(IInstallableUnit iu, String name) {
-		return iu.getProperty(name);
+	/**
+	 * Creates a new query on the given property name and value.
+	 */
+	public IUPropertyQuery(String propertyName, String propertyValue) {
+		super(IInstallableUnit.class, createMatchExpression(propertyName, propertyValue));
 	}
 }
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/query/LatestIUVersionQuery.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/query/LatestIUVersionQuery.java
index fe79d9404..1115e2e03 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/query/LatestIUVersionQuery.java
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/query/LatestIUVersionQuery.java
@@ -19,10 +19,23 @@ import org.eclipse.equinox.p2.query.*;
  */
 public class LatestIUVersionQuery<T extends IVersionedId> extends ContextQuery<T> {
 
+	private final IQuery<T> query;
+
+	public LatestIUVersionQuery() {
+		this.query = null;
+	}
+
+	public LatestIUVersionQuery(IQuery<T> query) {
+		this.query = query;
+	}
+
 	/**
 	 * Performs the LatestIUVersionQuery
 	 */
 	public IQueryResult<T> perform(Iterator<T> iterator) {
+		if (query != null)
+			iterator = query.perform(iterator).iterator();
+
 		HashMap<String, T> greatestIUVersion = new HashMap<String, T>();
 		while (iterator.hasNext()) {
 			T versionedID = iterator.next();
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/query/UpdateQuery.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/query/UpdateQuery.java
index 3ca68f9a0..61f97c47f 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/query/UpdateQuery.java
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/query/UpdateQuery.java
@@ -10,19 +10,14 @@
  *******************************************************************************/
 package org.eclipse.equinox.internal.p2.metadata.query;
 
-import org.eclipse.equinox.p2.metadata.IUpdateDescriptor;
-
-import org.eclipse.equinox.p2.metadata.IInstallableUnitPatch;
-
-import org.eclipse.equinox.p2.metadata.IInstallableUnit;
-import org.eclipse.equinox.p2.metadata.IRequirement;
+import org.eclipse.equinox.p2.metadata.*;
 import org.eclipse.equinox.p2.query.MatchQuery;
 
 /**
  * A query that finds all IUs that are considered an "Update" of the 
  * specified IU.  
  */
-public class UpdateQuery extends MatchQuery<IInstallableUnit> {
+public final class UpdateQuery extends MatchQuery<IInstallableUnit> {
 	private IInstallableUnit updateFrom;
 
 	public UpdateQuery(IInstallableUnit updateFrom) {
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/expression/ExpressionUtil.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/expression/ExpressionUtil.java
index 84d48eb3e..eb1adc5af 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/expression/ExpressionUtil.java
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/expression/ExpressionUtil.java
@@ -10,8 +10,8 @@
  *******************************************************************************/
 package org.eclipse.equinox.p2.metadata.expression;
 
+import org.eclipse.equinox.internal.p2.metadata.MetadataActivator;
 import org.eclipse.equinox.internal.p2.metadata.expression.*;
-import org.eclipse.equinox.internal.p2.metadata.expression.parser.ExpressionParser;
 import org.eclipse.equinox.internal.p2.metadata.expression.parser.LDAPFilterParser;
 
 /**
@@ -20,22 +20,23 @@ import org.eclipse.equinox.internal.p2.metadata.expression.parser.LDAPFilterPars
  */
 public abstract class ExpressionUtil {
 	private static final LDAPFilterParser ldapFilterParser = new LDAPFilterParser(ExpressionFactory.INSTANCE);
-	private static final ExpressionParser expressionParser = new ExpressionParser(ExpressionFactory.INSTANCE);
+	public static final IExpression TRUE_EXPRESSION = getFactory().constant(Boolean.TRUE);
+	public static final IExpression FALSE_EXPRESSION = getFactory().constant(Boolean.FALSE);
 
 	/**
 	 * Returns the global expression factory
 	 * @return The global expression factory.
 	 */
 	public static IExpressionFactory getFactory() {
-		return ExpressionFactory.INSTANCE;
+		return MetadataActivator.getExpressionFactory();
 	}
 
 	/**
 	 * Creates and returns a new expression parser
 	 * @return The new parser
 	 */
-	public static IExpressionParser newParser() {
-		return new ExpressionParser(getFactory());
+	public static IExpressionParser getParser() {
+		return MetadataActivator.getExpressionParser();
 	}
 
 	/**
@@ -59,7 +60,7 @@ public abstract class ExpressionUtil {
 	 */
 	public static IExpression parse(String expression) {
 		expression = trimmedOrNull(expression);
-		return expression == null ? null : expressionParser.parse(expression);
+		return expression == null ? null : getParser().parse(expression);
 	}
 
 	/**
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/expression/IContextExpression.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/expression/IContextExpression.java
new file mode 100644
index 000000000..7dc24dd03
--- /dev/null
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/expression/IContextExpression.java
@@ -0,0 +1,44 @@
+/*******************************************************************************
+ * Copyright (c) 2009 Cloudsmith Inc. and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *     Cloudsmith Inc. - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.equinox.p2.metadata.expression;
+
+import java.util.Iterator;
+
+/**
+ * This is an expression that will need access to the global variable
+ * <code>everything</code>.
+ */
+public interface IContextExpression<T> extends IExpression {
+	/**
+	 * <p>Creates a new context to be passed to a subsequent evaluation. The context
+	 * will have the variable 'everything' set to an expression that represents
+	 * the <code>everything</code> iterator filtered for instances of <code>elementClass</code>.</p>
+	 * <p>The values of the iterator will be copied if necessary (when everything is referenced
+	 * more then once).</p>
+	 * @param elementClass the class of the iterator elements
+	 * @param everything The iterator that represents all queried material.
+	 * @return A new evaluation context.
+	 */
+	IEvaluationContext createContext(Class<T> elementClass, Iterator<T> everything);
+
+	/**
+	 * Returns the parameters that this context expression was created with.
+	 * @return An array of parameters, possibly empty but never <code>null</code>.
+	 */
+	Object[] getParameters();
+
+	/**
+	 * Evaluate the expression and return the expected collection result as an iterator
+	 * @param context The evaluation context
+	 * @return The result of the evaluation.
+	 */
+	Iterator<T> iterator(IEvaluationContext context);
+}
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/expression/IEvaluationContext.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/expression/IEvaluationContext.java
index 4b049c054..ee3021442 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/expression/IEvaluationContext.java
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/expression/IEvaluationContext.java
@@ -10,12 +10,18 @@
  *******************************************************************************/
 package org.eclipse.equinox.p2.metadata.expression;
 
+import org.eclipse.equinox.p2.metadata.index.IIndexProvider;
+
 /**
  * The evaluation context. Contexts can be nested and new contexts are pushed for each closure
  * during an evaluation of an expression.
  * @since 2.0
  */
 public interface IEvaluationContext {
+	IIndexProvider<?> getIndexProvider();
+
+	void setIndexProvider(IIndexProvider<?> indexProvider);
+
 	/**
 	 * Retrieve the value of the given <code>variable</code> from this context
 	 * @param variable The variable who's value should be retrieved
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/expression/IExpressionFactory.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/expression/IExpressionFactory.java
index 47d214619..f7e275df0 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/expression/IExpressionFactory.java
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/expression/IExpressionFactory.java
@@ -74,6 +74,14 @@ public interface IExpressionFactory {
 	IExpression constant(Object value);
 
 	/**
+	 * Creates a top level expression that represents a full query.
+	 * @param expr The query
+	 * @param parameters The parameters of the query
+	 * @return A top level query expression
+	 */
+	<T> IContextExpression<T> contextExpression(IExpression expr, Object... parameters);
+
+	/**
 	 * Create an expression that tests if <code>lhs</code> is equal to <code>rhs</code>.
 	 * @param lhs The left hand side value.
 	 * @param rhs The right hand side value.
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/expression/IExpressionParser.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/expression/IExpressionParser.java
index 6e716af06..c9f43b33c 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/expression/IExpressionParser.java
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/expression/IExpressionParser.java
@@ -10,6 +10,7 @@
  *******************************************************************************/
 package org.eclipse.equinox.p2.metadata.expression;
 
+
 /**
  * A parser that produces an expression tree based on a string representation. An
  * implementation will use the {@link IExpressionFactory} to create the actual expressions
@@ -18,9 +19,19 @@ package org.eclipse.equinox.p2.metadata.expression;
 public interface IExpressionParser {
 	/**
 	 * Create a new expression. The expression will have access to the global
-	 * variable and to the context parameters.
+	 * variable 'this' and to the context parameters.
 	 * @param exprString The string representing the boolean expression.
 	 * @return The resulting expression tree.
+	 * @throws ExpressionParseException
 	 */
 	IExpression parse(String exprString);
+
+	/**
+	 * Create an arbitrary expression. The expression will have access to the global
+	 * variable 'everything' and to the context parameters.
+	 * @param exprString The string representing the boolean expression.
+	 * @return The resulting expression tree.
+	 * @throws ExpressionParseException
+	 */
+	IExpression parseQuery(String exprString);
 }
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/index/IIndex.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/index/IIndex.java
new file mode 100644
index 000000000..b06ea05c0
--- /dev/null
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/index/IIndex.java
@@ -0,0 +1,35 @@
+/*******************************************************************************
+ * Copyright (c) 2010 Cloudsmith Inc. and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *     Cloudsmith Inc. - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.equinox.p2.metadata.index;
+
+import java.util.Iterator;
+import org.eclipse.equinox.p2.metadata.expression.IEvaluationContext;
+import org.eclipse.equinox.p2.metadata.expression.IExpression;
+
+/**
+ * Indexed access to the elements provided by an IQueryable
+ */
+public interface IIndex<T> {
+	/**
+	 * Obtains the elements that are candidates for the given <code>booleanExpr</code> when applied
+	 * using the given <code>variable</code> as <code>this</code>.
+	 * The returned set of elements are the elements that must be present in order for the expression
+	 * to evaluate to <code>true</code>. The set may contain false positives.
+	 * 
+	 * TODO: Write more about how the valid set of elements is determined.
+	 * 
+	 * @param ctx The evaluation context used when examining the <code>booleanExpr</code>.
+	 * @param variable The variable used as <code>this</code>.
+	 * @param booleanExpr The boolean expression.
+	 * @return The candidate elements or <code>null</code> if this index cannot be used.
+	 */
+	Iterator<T> getCandidates(IEvaluationContext ctx, IExpression variable, IExpression booleanExpr);
+}
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/query/ObjectMatchQuery.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/index/IIndexProvider.java
index f48e50aac..543acbdaf 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/query/ObjectMatchQuery.java
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/index/IIndexProvider.java
@@ -1,5 +1,5 @@
 /*******************************************************************************
- * Copyright (c) 2009 Cloudsmith Inc. and others.
+ * Copyright (c) 2010 Cloudsmith Inc. and others.
  * All rights reserved. This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License v1.0
  * which accompanies this distribution, and is available at
@@ -8,15 +8,12 @@
  * Contributors:
  *     Cloudsmith Inc. - initial API and implementation
  *******************************************************************************/
-package org.eclipse.equinox.internal.p2.metadata.query;
+package org.eclipse.equinox.p2.metadata.index;
 
-import org.eclipse.equinox.p2.query.MatchQuery;
+import java.util.Iterator;
 
-/**
- * Special implementation for use without generic support
- */
-public abstract class ObjectMatchQuery extends MatchQuery<Object> {
-	public boolean isMatch(Object candidate) {
-		return true;
-	}
+public interface IIndexProvider<T> {
+	IIndex<T> getIndex(String memberName);
+
+	Iterator<T> everything();
 }
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/index/IQueryWithIndex.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/index/IQueryWithIndex.java
new file mode 100644
index 000000000..672b5df89
--- /dev/null
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/index/IQueryWithIndex.java
@@ -0,0 +1,18 @@
+/*******************************************************************************
+ * Copyright (c) 2010 Cloudsmith Inc. and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *     Cloudsmith Inc. - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.equinox.p2.metadata.index;
+
+import org.eclipse.equinox.p2.query.IQuery;
+import org.eclipse.equinox.p2.query.IQueryResult;
+
+public interface IQueryWithIndex<T> extends IQuery<T> {
+	IQueryResult<T> perform(IIndexProvider<T> indexProvider);
+}
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/query/CategoryMemberQuery.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/query/CategoryMemberQuery.java
index dc59f605b..22bd85835 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/query/CategoryMemberQuery.java
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/query/CategoryMemberQuery.java
@@ -10,11 +10,8 @@
  *******************************************************************************/
 package org.eclipse.equinox.p2.metadata.query;
 
-import java.util.Collection;
-import org.eclipse.equinox.internal.p2.core.helpers.CollectionUtils;
 import org.eclipse.equinox.p2.metadata.IInstallableUnit;
-import org.eclipse.equinox.p2.metadata.IRequirement;
-import org.eclipse.equinox.p2.query.MatchQuery;
+import org.eclipse.equinox.p2.metadata.expression.*;
 
 /**
  * A query matching every {@link IInstallableUnit} that is a member
@@ -22,8 +19,13 @@ import org.eclipse.equinox.p2.query.MatchQuery;
  * 
  * @since 2.0 
  */
-public class CategoryMemberQuery extends MatchQuery<IInstallableUnit> {
-	private final Collection<IRequirement> required;
+public final class CategoryMemberQuery extends ExpressionQuery<IInstallableUnit> {
+	private static final IExpression expression = ExpressionUtil.parse("$0.exists(r | $0 ~= this"); //$NON-NLS-1$
+
+	private static IMatchExpression<IInstallableUnit> createExpression(IInstallableUnit category) {
+		IExpressionFactory factory = ExpressionUtil.getFactory();
+		return CategoryQuery.isCategory(category) ? factory.<IInstallableUnit> matchExpression(expression, category.getRequiredCapabilities()) : MATCH_NO_UNIT;
+	}
 
 	/**
 	 * Creates a new query that will return the members of the
@@ -33,23 +35,6 @@ public class CategoryMemberQuery extends MatchQuery<IInstallableUnit> {
 	 * @param category The category
 	 */
 	public CategoryMemberQuery(IInstallableUnit category) {
-		if (CategoryQuery.isCategory(category))
-			this.required = category.getRequiredCapabilities();
-		else
-			this.required = CollectionUtils.emptyList();
-	}
-
-	/*
-	 * (non-Javadoc)
-	 * @see org.eclipse.equinox.internal.provisional.p2.metadata.query.MatchQuery#isMatch(java.lang.Object)
-	 */
-	public boolean isMatch(IInstallableUnit candidate) {
-		// since a category lists its members as requirements, then meeting
-		// any requirement means the candidate is a member of the category.
-		for (IRequirement req : required) {
-			if (candidate.satisfies(req))
-				return true;
-		}
-		return false;
+		super(IInstallableUnit.class, createExpression(category));
 	}
 }
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/query/CategoryQuery.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/query/CategoryQuery.java
index d1d86f912..f93fbb4ab 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/query/CategoryQuery.java
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/query/CategoryQuery.java
@@ -12,22 +12,16 @@ package org.eclipse.equinox.p2.metadata.query;
 
 import org.eclipse.equinox.internal.p2.metadata.query.IUPropertyQuery;
 import org.eclipse.equinox.p2.metadata.IInstallableUnit;
-import org.eclipse.equinox.p2.query.MatchQuery;
 
 /**
  * A query matching every {@link IInstallableUnit} that is a category.
  * @since 2.0 
  */
-public final class CategoryQuery extends MatchQuery<IInstallableUnit> {
+public final class CategoryQuery extends ExpressionQuery<IInstallableUnit> {
 	private static final String PROP_TYPE_CATEGORY = "org.eclipse.equinox.p2.type.category"; //$NON-NLS-1$
-	private IUPropertyQuery query;
 
 	public CategoryQuery() {
-		query = new IUPropertyQuery(PROP_TYPE_CATEGORY, null);
-	}
-
-	public boolean isMatch(IInstallableUnit candidate) {
-		return query.isMatch(candidate);
+		super(IInstallableUnit.class, IUPropertyQuery.createMatchExpression(PROP_TYPE_CATEGORY, Boolean.TRUE.toString()));
 	}
 
 	/**
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/query/ExpressionQuery.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/query/ExpressionQuery.java
index 90624c637..345ed618b 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/query/ExpressionQuery.java
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/query/ExpressionQuery.java
@@ -10,30 +10,66 @@
  *******************************************************************************/
 package org.eclipse.equinox.p2.metadata.query;
 
+import java.util.HashSet;
+import java.util.Iterator;
+import org.eclipse.equinox.internal.p2.metadata.expression.Expression;
 import org.eclipse.equinox.internal.p2.metadata.expression.ExpressionFactory;
+import org.eclipse.equinox.p2.metadata.IArtifactKey;
+import org.eclipse.equinox.p2.metadata.IInstallableUnit;
 import org.eclipse.equinox.p2.metadata.expression.*;
-import org.eclipse.equinox.p2.query.MatchQuery;
+import org.eclipse.equinox.p2.metadata.index.*;
+import org.eclipse.equinox.p2.query.*;
 
 /**
  * A query that matches candidates against an expression.
  * @since 2.0
  */
-public class ExpressionQuery<T> extends MatchQuery<T> {
+public class ExpressionQuery<T> implements IQueryWithIndex<T> {
+	public static final IMatchExpression<IInstallableUnit> MATCH_ALL_UNITS = ExpressionUtil.getFactory().matchExpression(ExpressionUtil.TRUE_EXPRESSION);
+	public static final IMatchExpression<IInstallableUnit> MATCH_NO_UNIT = ExpressionUtil.getFactory().matchExpression(ExpressionUtil.FALSE_EXPRESSION);
+
 	private final IMatchExpression<T> expression;
-	private final IEvaluationContext context;
-	private final Class<T> matchingClass;
+	private final Class<? extends T> matchingClass;
+	private IEvaluationContext context;
 
-	public ExpressionQuery(Class<T> matchingClass, IExpression expression, Object... parameters) {
+	public ExpressionQuery(Class<? extends T> matchingClass, IExpression expression, Object... parameters) {
 		this(matchingClass, ExpressionUtil.getFactory().<T> matchExpression(expression, parameters));
 	}
 
-	public ExpressionQuery(Class<T> matchingClass, IMatchExpression<T> expression) {
+	public ExpressionQuery(Class<? extends T> matchingClass, IMatchExpression<T> expression) {
 		this.matchingClass = matchingClass;
 		this.expression = expression;
 		this.context = expression.createContext();
 	}
 
-	@Override
+	public IQueryResult<T> perform(IIndexProvider<T> indexProvider) {
+		Iterator<T> iterator = null;
+		for (String member : Expression.getIndexCandidateMembers(IArtifactKey.class, ExpressionFactory.THIS, (Expression) expression)) {
+			IIndex<T> index = indexProvider.getIndex(member);
+			if (index != null) {
+				iterator = index.getCandidates(context, ExpressionFactory.THIS, expression);
+				if (iterator != null)
+					break;
+			}
+		}
+		if (iterator == null)
+			iterator = indexProvider.everything();
+		return perform(iterator);
+	}
+
+	public IQueryResult<T> perform(Iterator<T> iterator) {
+		HashSet<T> result = null;
+		while (iterator.hasNext()) {
+			T value = iterator.next();
+			if (isMatch(value)) {
+				if (result == null)
+					result = new HashSet<T>();
+				result.add(value);
+			}
+		}
+		return result == null ? Collector.<T> emptyCollector() : new CollectionResult<T>(result);
+	}
+
 	public boolean isMatch(T candidate) {
 		if (!matchingClass.isInstance(candidate))
 			return false;
@@ -44,4 +80,8 @@ public class ExpressionQuery<T> extends MatchQuery<T> {
 	public IMatchExpression<T> getExpression() {
 		return expression;
 	}
+
+	public void setIndexProvider(IIndexProvider<T> indexProvider) {
+		context.setIndexProvider(indexProvider);
+	}
 }
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/query/FragmentQuery.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/query/FragmentQuery.java
index fc70dd9e9..de04066a3 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/query/FragmentQuery.java
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/query/FragmentQuery.java
@@ -10,26 +10,16 @@
  *******************************************************************************/
 package org.eclipse.equinox.p2.metadata.query;
 
-import org.eclipse.equinox.p2.metadata.IInstallableUnitFragment;
-
-import org.eclipse.equinox.internal.p2.metadata.query.IUPropertyQuery;
 import org.eclipse.equinox.p2.metadata.IInstallableUnit;
-import org.eclipse.equinox.p2.query.MatchQuery;
+import org.eclipse.equinox.p2.metadata.IInstallableUnitFragment;
 
 /**
  * A query matching every {@link IInstallableUnit} that is a category.
  * @since 2.0
  */
-public final class FragmentQuery extends MatchQuery<IInstallableUnit> {
-	private static final String PROP_TYPE_FRAGMENT = "org.eclipse.equinox.p2.type.fragment"; //$NON-NLS-1$
-	private IUPropertyQuery query;
-
+public final class FragmentQuery extends ExpressionQuery<IInstallableUnit> {
 	public FragmentQuery() {
-		query = new IUPropertyQuery(PROP_TYPE_FRAGMENT, null);
-	}
-
-	public boolean isMatch(IInstallableUnit candidate) {
-		return query.isMatch(candidate);
+		super(IInstallableUnitFragment.class, MATCH_ALL_UNITS);
 	}
 
 	/**
@@ -38,11 +28,8 @@ public final class FragmentQuery extends MatchQuery<IInstallableUnit> {
 	 * @return <tt>true</tt> if the parameter is a fragment.
 	 */
 	public static boolean isFragment(IInstallableUnit iu) {
-		if (iu instanceof IInstallableUnitFragment)
-			return true;
+		return iu instanceof IInstallableUnitFragment;
 		//		String value = iu.getProperty(PROP_TYPE_FRAGMENT);
-		//		if (value != null && (value.equals(Boolean.TRUE.toString())))
-		//			return true;
-		return false;
+		//		return value != null && (value.equals(Boolean.TRUE.toString()));
 	}
 }
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/query/GroupQuery.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/query/GroupQuery.java
index 298b04a2f..729920902 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/query/GroupQuery.java
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/query/GroupQuery.java
@@ -12,22 +12,16 @@ package org.eclipse.equinox.p2.metadata.query;
 
 import org.eclipse.equinox.internal.p2.metadata.query.IUPropertyQuery;
 import org.eclipse.equinox.p2.metadata.IInstallableUnit;
-import org.eclipse.equinox.p2.query.MatchQuery;
 
 /**
  * A query matching every {@link IInstallableUnit} that is a group. 
  * @since 2.0
  */
-public final class GroupQuery extends MatchQuery<IInstallableUnit> {
+public final class GroupQuery extends ExpressionQuery<IInstallableUnit> {
 	private static final String PROP_TYPE_GROUP = "org.eclipse.equinox.p2.type.group"; //$NON-NLS-1$
-	private IUPropertyQuery query;
 
 	public GroupQuery() {
-		query = new IUPropertyQuery(PROP_TYPE_GROUP, null);
-	}
-
-	public boolean isMatch(IInstallableUnit candidate) {
-		return query.isMatch(candidate);
+		super(IInstallableUnit.class, IUPropertyQuery.createMatchExpression(PROP_TYPE_GROUP, Boolean.TRUE.toString()));
 	}
 
 	/**
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/query/InstallableUnitQuery.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/query/InstallableUnitQuery.java
index ac2110b03..42f5c9915 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/query/InstallableUnitQuery.java
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/query/InstallableUnitQuery.java
@@ -10,26 +10,39 @@
  *******************************************************************************/
 package org.eclipse.equinox.p2.metadata.query;
 
-import org.eclipse.equinox.p2.metadata.Version;
-import org.eclipse.equinox.p2.metadata.VersionRange;
-
-import org.eclipse.equinox.p2.metadata.IInstallableUnit;
-import org.eclipse.equinox.p2.metadata.IVersionedId;
-import org.eclipse.equinox.p2.query.MatchQuery;
+import org.eclipse.equinox.p2.metadata.*;
+import org.eclipse.equinox.p2.metadata.expression.*;
 
 /**
  * A query that matches on the id and version of an {@link IInstallableUnit}.
  * @since 2.0
  */
-public class InstallableUnitQuery extends MatchQuery<IInstallableUnit> {
+public final class InstallableUnitQuery extends ExpressionQuery<IInstallableUnit> {
 	/**
 	 * A convenience query that will match any {@link IInstallableUnit}
 	 * it encounters.
 	 */
 	public static final InstallableUnitQuery ANY = new InstallableUnitQuery((String) null);
 
-	private String id;
-	private final VersionRange range;
+	private static final IExpression matchID = ExpressionUtil.parse("id == $0"); //$NON-NLS-1$
+	private static final IExpression matchIDAndVersion = ExpressionUtil.parse("id == $0 && version == $1"); //$NON-NLS-1$
+	private static final IExpression matchIDAndRange = ExpressionUtil.parse("id == $0 && version ~= $1"); //$NON-NLS-1$
+
+	private static IMatchExpression<IInstallableUnit> createMatchExpression(String id) {
+		return id == null ? ExpressionQuery.MATCH_ALL_UNITS : ExpressionUtil.getFactory().<IInstallableUnit> matchExpression(matchID, id);
+	}
+
+	private static IMatchExpression<IInstallableUnit> createMatchExpression(String id, VersionRange range) {
+		if (range == null || range.equals(VersionRange.emptyRange))
+			return createMatchExpression(id);
+		if (range.getMinimum().equals(range.getMaximum()))
+			return createMatchExpression(id, range.getMinimum());
+		return id == null ? ExpressionQuery.MATCH_ALL_UNITS : ExpressionUtil.getFactory().<IInstallableUnit> matchExpression(matchIDAndRange, id, range);
+	}
+
+	private static IMatchExpression<IInstallableUnit> createMatchExpression(String id, Version version) {
+		return version == null || version.equals(Version.emptyVersion) ? createMatchExpression(id) : ExpressionUtil.getFactory().<IInstallableUnit> matchExpression(matchIDAndVersion, id, version);
+	}
 
 	/**
 	 * Creates a query that will match any {@link IInstallableUnit} with the given
@@ -38,8 +51,7 @@ public class InstallableUnitQuery extends MatchQuery<IInstallableUnit> {
 	 * @param id The installable unit id to match, or <code>null</code> to match any id
 	 */
 	public InstallableUnitQuery(String id) {
-		this.id = id;
-		this.range = null;
+		super(IInstallableUnit.class, createMatchExpression(id));
 	}
 
 	/**
@@ -50,8 +62,7 @@ public class InstallableUnitQuery extends MatchQuery<IInstallableUnit> {
 	 * @param range The version range to match
 	 */
 	public InstallableUnitQuery(String id, VersionRange range) {
-		this.id = id;
-		this.range = range;
+		super(IInstallableUnit.class, createMatchExpression(id, range));
 	}
 
 	/**
@@ -62,8 +73,7 @@ public class InstallableUnitQuery extends MatchQuery<IInstallableUnit> {
 	 * @param version The precise version that a matching unit must have
 	 */
 	public InstallableUnitQuery(String id, Version version) {
-		this.id = id;
-		this.range = (version == null || Version.emptyVersion.equals(version)) ? null : new VersionRange(version, true, version, true);
+		super(IInstallableUnit.class, createMatchExpression(id, version));
 	}
 
 	/**
@@ -81,26 +91,7 @@ public class InstallableUnitQuery extends MatchQuery<IInstallableUnit> {
 	 * @return The installable unit it
 	 */
 	public String getId() {
-		return id;
+		Object[] params = getExpression().getParameters();
+		return params.length > 0 ? (String) params[0] : null;
 	}
-
-	/**
-	 * Returns the version range that this query will match against.
-	 * @return The installable unit version range.
-	 */
-	public VersionRange getRange() {
-		return range;
-	}
-
-	/* (non-Javadoc)
-	 * @see org.eclipse.equinox.p2.query2.Query#isMatch(java.lang.Object)
-	 */
-	public boolean isMatch(IInstallableUnit candidate) {
-		if (id != null && !id.equals(candidate.getId()))
-			return false;
-		if (range != null && !range.isIncluded(candidate.getVersion()))
-			return false;
-		return true;
-	}
-
 }
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/query/PatchQuery.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/query/PatchQuery.java
index d066db376..e341d8efc 100644
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/query/PatchQuery.java
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/metadata/query/PatchQuery.java
@@ -12,22 +12,16 @@ package org.eclipse.equinox.p2.metadata.query;
 
 import org.eclipse.equinox.internal.p2.metadata.query.IUPropertyQuery;
 import org.eclipse.equinox.p2.metadata.IInstallableUnit;
-import org.eclipse.equinox.p2.query.MatchQuery;
 
 /**
  * A query matching every {@link IInstallableUnit} that is a patch. 
  * @since 2.0
  */
-public final class PatchQuery extends MatchQuery<IInstallableUnit> {
+public final class PatchQuery extends ExpressionQuery<IInstallableUnit> {
 	private static final String PROP_TYPE_PATCH = "org.eclipse.equinox.p2.type.patch"; //$NON-NLS-1$
-	private IUPropertyQuery query;
 
 	public PatchQuery() {
-		query = new IUPropertyQuery(PROP_TYPE_PATCH, Boolean.TRUE.toString());
-	}
-
-	public boolean isMatch(IInstallableUnit candidate) {
-		return query.isMatch(candidate);
+		super(IInstallableUnit.class, IUPropertyQuery.createMatchExpression(PROP_TYPE_PATCH, Boolean.TRUE.toString()));
 	}
 
 	/**
diff --git a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/query/CollectionResult.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/query/CollectionResult.java
new file mode 100644
index 000000000..688fd651d
--- /dev/null
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/p2/query/CollectionResult.java
@@ -0,0 +1,53 @@
+/*******************************************************************************
+ * Copyright (c) 2010 Cloudsmith Inc. and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *     Cloudsmith Inc. - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.equinox.p2.query;
+
+import java.lang.reflect.Array;
+import java.util.*;
+import org.eclipse.core.runtime.IProgressMonitor;
+import org.eclipse.equinox.internal.p2.core.helpers.CollectionUtils;
+
+public class CollectionResult<T> implements IQueryResult<T> {
+	private final Collection<T> collection;
+
+	public CollectionResult(Collection<T> collection) {
+		this.collection = collection == null ? CollectionUtils.<T> emptySet() : collection;
+	}
+
+	public IQueryResult<T> query(IQuery<T> query, IProgressMonitor monitor) {
+		return query.perform(iterator());
+	}
+
+	public boolean isEmpty() {
+		return collection.isEmpty();
+	}
+
+	public Iterator<T> iterator() {
+		return collection.iterator();
+	}
+
+	public T[] toArray(Class<? extends T> clazz) {
+		int size = collection.size();
+		@SuppressWarnings("unchecked")
+		T[] result = (T[]) Array.newInstance(clazz, size);
+		if (size != 0)
+			collection.toArray(result);
+		return result;
+	}
+
+	public Set<T> toSet() {
+		return new HashSet<T>(collection);
+	}
+
+	public Set<T> unmodifiableSet() {
+		return collection instanceof Set<?> ? Collections.<T> unmodifiableSet((Set<T>) collection) : toSet();
+	}
+}