302201 : Unify the two query approaches used in p2

25 files changed, 1065 insertions, 103 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/ObjectMatchQuery.java b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/query/ObjectMatchQuery.java
deleted file mode 100644
index f48e50aac..000000000
--- a/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/query/ObjectMatchQuery.java
+++ /dev/null
@@ -1,22 +0,0 @@
-/*******************************************************************************
- * 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.query;
-
-import org.eclipse.equinox.p2.query.MatchQuery;
-
-/**
- * Special implementation for use without generic support
- */
-public abstract class ObjectMatchQuery extends MatchQuery<Object> {
-	public boolean isMatch(Object candidate) {
-		return true;
-	}
-}
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) {