1 files changed, 341 insertions, 0 deletions
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
new file mode 100644
index 000000000..75f47dd94
--- /dev/null
+++ b/bundles/org.eclipse.equinox.p2.metadata/src/org/eclipse/equinox/internal/p2/metadata/expression/Expression.java
@@ -0,0 +1,341 @@
+/*******************************************************************************
+ * 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.*;
+import org.eclipse.equinox.p2.metadata.expression.*;
+
+/**
+ * The base class of the expression tree.
+ */
+public abstract class Expression implements IExpression, Comparable<Expression>, IExpressionConstants {
+
+	static final Expression[] emptyArray = new Expression[0];
+
+	public static void appendOperand(StringBuffer bld, Variable rootVariable, Expression operand, int priority) {
+		if (priority < operand.getPriority()) {
+			bld.append('(');
+			operand.toString(bld, rootVariable);
+			bld.append(')');
+		} else
+			operand.toString(bld, rootVariable);
+	}
+
+	public static Expression[] assertLength(Expression[] operands, int minLength, int maxLength, String operand) {
+		if (operands == null)
+			operands = emptyArray;
+		if (operands.length < minLength)
+			throw new IllegalArgumentException("Not enough operands for " + operand); //$NON-NLS-1$
+		if (operands.length > maxLength)
+			throw new IllegalArgumentException("Too many operands for " + operand); //$NON-NLS-1$
+		return operands;
+	}
+
+	public static Expression[] assertLength(Expression[] operands, int length, String operand) {
+		if (operands == null)
+			operands = emptyArray;
+		if (operands.length < length)
+			throw new IllegalArgumentException("Not enough operands for " + operand); //$NON-NLS-1$
+		return operands;
+	}
+
+	public static int compare(Expression[] arr1, Expression[] arr2) {
+		int max = arr1.length;
+		if (max > arr2.length)
+			max = arr2.length;
+		for (int idx = 0; idx < max; ++idx) {
+			int cmp = arr1[idx].compareTo(arr2[idx]);
+			if (cmp != 0)
+				return cmp;
+		}
+		if (max == arr2.length) {
+			if (max < arr1.length)
+				return 1;
+			return 0;
+		}
+		return -1;
+	}
+
+	public static boolean equals(Expression[] arr1, Expression[] arr2) {
+		int idx = arr1.length;
+		if (idx != arr2.length)
+			return false;
+		while (--idx >= 0)
+			if (!arr1[idx].equals(arr2[idx]))
+				return false;
+		return true;
+	}
+
+	public static int hashCode(Expression[] arr) {
+		int idx = arr.length;
+		int result = 1;
+		while (--idx >= 0)
+			result = 31 * result + arr[idx].hashCode();
+		return result;
+	}
+
+	public static void elementsToString(StringBuffer bld, Variable rootVariable, Expression[] elements) {
+		int top = elements.length;
+		if (top > 0) {
+			elements[0].toString(bld, rootVariable);
+			for (int idx = 1; idx < top; ++idx) {
+				bld.append(", "); //$NON-NLS-1$
+				appendOperand(bld, rootVariable, elements[idx], PRIORITY_MAX);
+			}
+		}
+	}
+
+	/**
+	 * Let the visitor visit this instance and all expressions that this
+	 * instance contains.
+	 * @param visitor The visiting visitor.
+	 * @return <code>true</code> if the visitor should continue visiting, <code>false</code> otherwise.
+	 */
+	public boolean accept(IExpressionVisitor visitor) {
+		return visitor.visit(this);
+	}
+
+	public int compareTo(Expression e) {
+		int cmp = getPriority() - e.getPriority();
+		if (cmp == 0) {
+			int e1 = getExpressionType();
+			int e2 = e.getExpressionType();
+			cmp = e1 > e2 ? 1 : (e1 == e2 ? 0 : -1);
+		}
+		return cmp;
+	}
+
+	public boolean equals(Object e) {
+		if (e == this)
+			return true;
+		if (e == null || getClass() != e.getClass())
+			return false;
+		return getExpressionType() == ((Expression) e).getExpressionType();
+	}
+
+	/**
+	 * Evaluate this expression with given context and variables.
+	 * @param context The evaluation context
+	 * @return The result of the evaluation.
+	 */
+	public abstract Object evaluate(IEvaluationContext context);
+
+	public Iterator<?> evaluateAsIterator(IEvaluationContext context) {
+		Object value = evaluate(context);
+		if (!(value instanceof Iterator<?>))
+			value = RepeatableIterator.create(value);
+		return (Iterator<?>) value;
+	}
+
+	public abstract String getOperator();
+
+	public abstract int getPriority();
+
+	public boolean isRootVariable() {
+		return false;
+	}
+
+	public final String toLDAPString() {
+		StringBuffer bld = new StringBuffer();
+		toLDAPString(bld);
+		return bld.toString();
+	}
+
+	public void toLDAPString(StringBuffer buf) {
+		throw new UnsupportedOperationException();
+	}
+
+	public final String toString() {
+		StringBuffer bld = new StringBuffer();
+		toString(bld);
+		return bld.toString();
+	}
+
+	public void toString(StringBuffer bld) {
+		toString(bld, ExpressionFactory.THIS);
+	}
+
+	public abstract void toString(StringBuffer bld, Variable rootVariable);
+
+	private static class Compacter {
+		private Expression base;
+
+		private List<Expression> parts;
+
+		private int op;
+
+		Compacter(Expression base, int op) {
+			this.base = base;
+			this.op = op;
+		}
+
+		Expression getResultingFilter() {
+			if (parts == null)
+				return base;
+
+			int partsOp = op == TYPE_AND ? TYPE_OR : TYPE_AND;
+			return addFilter(base, normalize(parts, partsOp), op);
+		}
+
+		boolean merge(Expression b) {
+			Expression[] aArr;
+			Expression[] bArr;
+			if (base.getExpressionType() == op)
+				aArr = getFilterImpls(base);
+			else
+				aArr = new Expression[] {base};
+
+			if (b.getExpressionType() == op)
+				bArr = getFilterImpls(b);
+			else
+				bArr = new Expression[] {b};
+
+			List<Expression> common = null;
+			List<Expression> onlyA = null;
+
+			int atop = aArr.length;
+			int btop = bArr.length;
+			int aidx;
+			int bidx;
+			for (aidx = 0; aidx < atop; ++aidx) {
+				Expression af = aArr[aidx];
+				for (bidx = 0; bidx < btop; ++bidx) {
+					Expression bf = bArr[bidx];
+					if (af.equals(bf)) {
+						if (common == null)
+							common = new ArrayList<Expression>();
+						common.add(af);
+						break;
+					}
+				}
+				if (bidx == btop) {
+					if (onlyA == null)
+						onlyA = new ArrayList<Expression>();
+					onlyA.add(af);
+				}
+			}
+			if (common == null)
+				// Nothing in common
+				return false;
+
+			if (onlyA == null && parts == null)
+				return true;
+
+			List<Expression> onlyB = null;
+			for (bidx = 0; bidx < btop; ++bidx) {
+				Expression bf = bArr[bidx];
+				for (aidx = 0; aidx < atop; ++aidx)
+					if (bf.equals(aArr[aidx]))
+						break;
+				if (aidx == atop) {
+					if (onlyB == null)
+						onlyB = new ArrayList<Expression>();
+					onlyB.add(bf);
+				}
+			}
+
+			if (onlyB == null && parts == null) {
+				// All of B is already covered by base
+				base = b;
+				return true;
+			}
+
+			if (parts == null)
+				parts = new ArrayList<Expression>();
+
+			if (onlyA != null) {
+				base = normalize(common, op);
+				Expression af = normalize(onlyA, op);
+				if (!parts.contains(af))
+					parts.add(af);
+			}
+			Expression bf = normalize(onlyB, op);
+			if (!parts.contains(bf))
+				parts.add(bf);
+			return true;
+		}
+	}
+
+	static Expression addFilter(Expression base, Expression subFilter, int expressionType) {
+		if (base.equals(subFilter))
+			return base;
+
+		ArrayList<Expression> filters = new ArrayList<Expression>(2);
+		filters.add(base);
+		filters.add(subFilter);
+		return normalize(filters, expressionType);
+	}
+
+	static Expression normalize(List<Expression> operands, int op) {
+		int top = operands.size();
+		if (top == 1)
+			return operands.get(0);
+
+		// a | (b | c) becomes a | b | c
+		// a & (b & c) becomes a & b & c
+		//
+		for (int idx = 0; idx < top; ++idx) {
+			Expression f = operands.get(idx);
+			if (f.getExpressionType() != op)
+				continue;
+
+			Expression[] sfs = getFilterImpls(f);
+			operands.remove(idx);
+			--top;
+			for (int ndx = 0; ndx < sfs.length; ++ndx) {
+				Expression nf = sfs[ndx];
+				if (!operands.contains(nf))
+					operands.add(nf);
+			}
+		}
+		top = operands.size();
+		if (top == 1)
+			return operands.get(0);
+
+		Collections.sort(operands);
+		List<Compacter> splits = new ArrayList<Compacter>();
+		int reverseOp = op == TYPE_AND ? TYPE_OR : TYPE_AND;
+
+		for (int idx = 0; idx < top; ++idx)
+			merge(splits, operands.get(idx), reverseOp);
+
+		operands.clear();
+		top = splits.size();
+		for (int idx = 0; idx < top; ++idx) {
+			Expression filter = splits.get(idx).getResultingFilter();
+			if (!operands.contains(filter))
+				operands.add(filter);
+		}
+		top = operands.size();
+		if (top == 1)
+			return operands.get(0);
+
+		Collections.sort(operands);
+		Expression[] expArray = operands.toArray(new Expression[top]);
+		return op == TYPE_AND ? new And(expArray) : new Or(expArray);
+	}
+
+	static void merge(List<Compacter> splits, Expression base, int op) {
+		int top = splits.size();
+		for (int idx = 0; idx < top; ++idx) {
+			Compacter split = splits.get(idx);
+			if (split.merge(base))
+				return;
+		}
+		splits.add(new Compacter(base, op));
+	}
+
+	static Expression[] getFilterImpls(Expression expression) {
+		if (expression instanceof NAry)
+			return ((NAry) expression).operands;
+		throw new IllegalArgumentException();
+	}
+}