Bug 306279 - [planner] p2 installs unexpected non-greedy dependencies

Non greedy requirements are now managed in the Projector, which allows a more flexible way to manage them. Fixes the issue reported in the bug report.

6 files changed, 306 insertions, 68 deletions

diff --git a/bundles/org.eclipse.equinox.p2.director/src/org/eclipse/equinox/internal/p2/director/Explanation.java b/bundles/org.eclipse.equinox.p2.director/src/org/eclipse/equinox/internal/p2/director/Explanation.java
index 6dea4fcf6..a1a168541 100644
--- a/bundles/org.eclipse.equinox.p2.director/src/org/eclipse/equinox/internal/p2/director/Explanation.java
+++ b/bundles/org.eclipse.equinox.p2.director/src/org/eclipse/equinox/internal/p2/director/Explanation.java
@@ -10,12 +10,9 @@
  ******************************************************************************/
 package org.eclipse.equinox.internal.p2.director;
 
-import org.eclipse.equinox.p2.metadata.IInstallableUnitPatch;
-
 import java.util.Arrays;
 import org.eclipse.core.runtime.*;
-import org.eclipse.equinox.p2.metadata.IInstallableUnit;
-import org.eclipse.equinox.p2.metadata.IRequirement;
+import org.eclipse.equinox.p2.metadata.*;
 import org.eclipse.osgi.util.NLS;
 
 public abstract class Explanation implements Comparable<Explanation> {
@@ -151,6 +148,30 @@ public abstract class Explanation implements Comparable<Explanation> {
 		}
 	}
 
+	public static class MissingGreedyIU extends Explanation {
+		public final IInstallableUnit iu;
+
+		public MissingGreedyIU(IInstallableUnit iu) {
+			this.iu = iu;
+		}
+
+		public int orderValue() {
+			return 3;
+		}
+
+		public int shortAnswer() {
+			return MISSING_REQUIREMENT;
+		}
+
+		public String toString() {
+			return NLS.bind(Messages.Explanation_missingNonGreedyRequired, iu);
+		}
+
+		public IStatus toStatus() {
+			return new Status(IStatus.ERROR, DirectorActivator.PI_DIRECTOR, NLS.bind(Messages.Explanation_missingNonGreedyRequired, getUserReadableName(iu)));
+		}
+	}
+
 	public static class Singleton extends Explanation {
 		public final IInstallableUnit[] ius;
 
diff --git a/bundles/org.eclipse.equinox.p2.director/src/org/eclipse/equinox/internal/p2/director/Messages.java b/bundles/org.eclipse.equinox.p2.director/src/org/eclipse/equinox/internal/p2/director/Messages.java
index c561d4a40..4b3e7f89b 100644
--- a/bundles/org.eclipse.equinox.p2.director/src/org/eclipse/equinox/internal/p2/director/Messages.java
+++ b/bundles/org.eclipse.equinox.p2.director/src/org/eclipse/equinox/internal/p2/director/Messages.java
@@ -37,6 +37,7 @@ public class Messages extends NLS {
 	public static String Explanation_hardDependency;
 	public static String Explanation_patchedHardDependency;
 	public static String Explanation_missingRequired;
+	public static String Explanation_missingNonGreedyRequired;
 	public static String Explanation_missingRequiredFilter;
 	public static String Explanation_optionalDependency;
 	public static String Explanation_rootMissing;
diff --git a/bundles/org.eclipse.equinox.p2.director/src/org/eclipse/equinox/internal/p2/director/Projector.java b/bundles/org.eclipse.equinox.p2.director/src/org/eclipse/equinox/internal/p2/director/Projector.java
index 1b16a88ce..dd6da9485 100644
--- a/bundles/org.eclipse.equinox.p2.director/src/org/eclipse/equinox/internal/p2/director/Projector.java
+++ b/bundles/org.eclipse.equinox.p2.director/src/org/eclipse/equinox/internal/p2/director/Projector.java
@@ -25,8 +25,7 @@ import org.eclipse.equinox.p2.metadata.*;
 import org.eclipse.equinox.p2.metadata.expression.IMatchExpression;
 import org.eclipse.equinox.p2.query.*;
 import org.eclipse.osgi.util.NLS;
-import org.sat4j.pb.IPBSolver;
-import org.sat4j.pb.SolverFactory;
+import org.sat4j.pb.*;
 import org.sat4j.pb.tools.DependencyHelper;
 import org.sat4j.pb.tools.WeightedObject;
 import org.sat4j.specs.*;
@@ -64,9 +63,25 @@ public class Projector {
 
 	private int numberOfInstalledIUs;
 
+	//Non greedy things
+	private Set<IInstallableUnit> nonGreedyIUs; //All the IUs that would satisfy non greedy dependencies
+	private Map<IInstallableUnit, AbstractVariable> nonGreedyVariables = new HashMap<IInstallableUnit, AbstractVariable>();
+	private Map<AbstractVariable, List<Object>> nonGreedyProvider = new HashMap<AbstractVariable, List<Object>>(); //Keeps track of all the "object" that provide an IU that is non greedly requested  
+
 	static class AbstractVariable {
+		//		private String name;
+
+		public AbstractVariable(String name) {
+			//						this.name = name;
+		}
+
+		public AbstractVariable() {
+			// TODO Auto-generated constructor stub
+		}
+
 		public String toString() {
 			return "AbstractVariable: " + hashCode(); //$NON-NLS-1$
+			//			return name == null ? "AbstractVariable: " + hashCode() : name; //$NON-NLS-1$
 		}
 	}
 
@@ -127,7 +142,7 @@ public class Projector {
 
 	}
 
-	public Projector(IQueryable<IInstallableUnit> q, Map<String, String> context, boolean considerMetaRequirements) {
+	public Projector(IQueryable<IInstallableUnit> q, Map<String, String> context, Set<IInstallableUnit> nonGreedyIUs, boolean considerMetaRequirements) {
 		picker = q;
 		noopVariables = new HashMap<IInstallableUnit, AbstractVariable>();
 		slice = new HashMap<String, Map<Version, IInstallableUnit>>();
@@ -135,6 +150,7 @@ public class Projector {
 		abstractVariables = new ArrayList<AbstractVariable>();
 		result = new MultiStatus(DirectorActivator.PI_DIRECTOR, IStatus.OK, Messages.Planner_Problems_resolving_plan, null);
 		assumptions = new ArrayList<Object>();
+		this.nonGreedyIUs = nonGreedyIUs;
 		this.considerMetaRequirements = considerMetaRequirements;
 	}
 
@@ -155,7 +171,7 @@ public class Projector {
 			}
 			IPBSolver solver;
 			if (DEBUG_ENCODING) {
-				solver = SolverFactory.newOPBStringSolver();
+				solver = new UserFriendlyPBStringSolver<Object>();
 			} else {
 				solver = SolverFactory.newEclipseP2();
 			}
@@ -163,6 +179,7 @@ public class Projector {
 			IQueryResult<IInstallableUnit> queryResult = picker.query(QueryUtil.createIUAnyQuery(), null);
 			if (DEBUG_ENCODING) {
 				dependencyHelper = new DependencyHelper<Object, Explanation>(solver, false);
+				((UserFriendlyPBStringSolver<Object>) solver).setMapping(dependencyHelper.getMappingToDomain());
 			} else {
 				dependencyHelper = new DependencyHelper<Object, Explanation>(solver);
 			}
@@ -187,6 +204,8 @@ public class Projector {
 
 			createMustHave(entryPointIU, alreadyExistingRoots);
 
+			createConstraintsForNonGreedy();
+
 			createOptimizationFunction(entryPointIU, newRoots);
 			if (DEBUG) {
 				long stop = System.currentTimeMillis();
@@ -202,6 +221,19 @@ public class Projector {
 		}
 	}
 
+	private void createConstraintsForNonGreedy() throws ContradictionException {
+		for (IInstallableUnit iu : nonGreedyIUs) {
+			AbstractVariable var = getNonGreedyVariable(iu);
+			List<Object> providers = nonGreedyProvider.get(var);
+			if (providers == null || providers.size() == 0) {
+				dependencyHelper.setFalse(var, new Explanation.MissingGreedyIU(iu));
+			} else {
+				createImplication(var, providers, Explanation.OPTIONAL_REQUIREMENT);//FIXME
+			}
+		}
+
+	}
+
 	/**
 	 * Efficiently compute the size of a queryable
 	 */
@@ -278,7 +310,7 @@ public class Projector {
 		List<IInstallableUnit> requestedPatches = new ArrayList<IInstallableUnit>();
 		Collection<IRequirement> reqs = metaIu.getRequirements();
 		for (IRequirement req : reqs) {
-			if (req.getMin() > 0)
+			if (req.getMin() > 0 || !req.isGreedy())
 				continue;
 			IQueryResult<IInstallableUnit> matches = picker.query(QueryUtil.createMatchQuery(req.getMatches()), null);
 			for (Iterator<IInstallableUnit> iterator = matches.iterator(); iterator.hasNext();) {
@@ -385,28 +417,72 @@ public class Projector {
 			if (matches.isEmpty()) {
 				missingRequirement(iu, req);
 			} else {
-				IInstallableUnit reqIu = matches.get(0);
-				Explanation explanation;
-				if (isRootIu) {
-					if (alreadyInstalledIUs.contains(reqIu)) {
-						explanation = new Explanation.IUInstalled(reqIu);
+				if (req.isGreedy()) {
+					IInstallableUnit reqIu = matches.get(0);
+					Explanation explanation;
+					if (isRootIu) {
+						if (alreadyInstalledIUs.contains(reqIu)) {
+							explanation = new Explanation.IUInstalled(reqIu);
+						} else {
+							explanation = new Explanation.IUToInstall(reqIu);
+						}
 					} else {
-						explanation = new Explanation.IUToInstall(reqIu);
+						explanation = new Explanation.HardRequirement(iu, req);
+					}
+					createImplication(iu, matches, explanation);
+					IInstallableUnit current;
+					for (Iterator<IInstallableUnit> it = matches.iterator(); it.hasNext();) {
+						current = it.next();
+						if (nonGreedyIUs.contains(current)) {
+							addNonGreedyProvider(getNonGreedyVariable(current), iu);
+						}
 					}
 				} else {
-					explanation = new Explanation.HardRequirement(iu, req);
+					List<Object> newConstraint = new ArrayList<Object>(matches.size());
+					IInstallableUnit current;
+					for (Iterator<IInstallableUnit> it = matches.iterator(); it.hasNext();) {
+						current = it.next();
+						newConstraint.add(getNonGreedyVariable(current));
+					}
+					createImplication(new Object[] {iu}, newConstraint, new Explanation.HardRequirement(iu, req)); // FIXME
 				}
-				createImplication(iu, matches, explanation);
 			}
 		} else {
 			if (!matches.isEmpty()) {
-				AbstractVariable abs = getAbstractVariable();
-				createImplication(new Object[] {abs, iu}, matches, Explanation.OPTIONAL_REQUIREMENT);
+				IInstallableUnit current;
+				AbstractVariable abs;
+				if (req.isGreedy()) {
+					abs = getAbstractVariable(req);
+					createImplication(new Object[] {abs, iu}, matches, Explanation.OPTIONAL_REQUIREMENT);
+					for (Iterator<IInstallableUnit> it = matches.iterator(); it.hasNext();) {
+						current = it.next();
+						if (nonGreedyIUs.contains(current)) {
+							addNonGreedyProvider(getNonGreedyVariable(current), abs);
+						}
+					}
+				} else {
+					abs = getAbstractVariable(req, false);
+					List<Object> newConstraint = new ArrayList<Object>();
+					for (Iterator<IInstallableUnit> it = matches.iterator(); it.hasNext();) {
+						current = it.next();
+						newConstraint.add(getNonGreedyVariable(current));
+					}
+					createImplication(new Object[] {abs, iu}, newConstraint, Explanation.OPTIONAL_REQUIREMENT);
+				}
 				optionalAbstractRequirements.add(abs);
 			}
 		}
 	}
 
+	private void addNonGreedyProvider(AbstractVariable nonGreedyVariable, Object o) {
+		List<Object> providers = nonGreedyProvider.get(nonGreedyVariable);
+		if (providers == null) {
+			providers = new ArrayList<Object>();
+			nonGreedyProvider.put(nonGreedyVariable, providers);
+		}
+		providers.add(o);
+	}
+
 	private void expandRequirements(Collection<IRequirement> reqs, IInstallableUnit iu, boolean isRootIu) throws ContradictionException {
 		if (reqs.isEmpty())
 			return;
@@ -506,23 +582,57 @@ public class Projector {
 						if (matches.isEmpty()) {
 							missingRequirement(patch, req);
 						} else {
-							IInstallableUnit reqIu = matches.get(0);
-							Explanation explanation;
-							if (isRootIu) {
-								if (alreadyInstalledIUs.contains(reqIu)) {
-									explanation = new Explanation.IUInstalled(reqIu);
+							IInstallableUnit current;
+							if (req.isGreedy()) {
+								IInstallableUnit reqIu = matches.get(0);
+								Explanation explanation;
+								if (isRootIu) {
+									if (alreadyInstalledIUs.contains(reqIu)) {
+										explanation = new Explanation.IUInstalled(reqIu);
+									} else {
+										explanation = new Explanation.IUToInstall(reqIu);
+									}
 								} else {
-									explanation = new Explanation.IUToInstall(reqIu);
+									explanation = new Explanation.PatchedHardRequirement(iu, req, patch);
+								}
+								createImplication(new Object[] {patch, iu}, matches, explanation);
+								for (Iterator<IInstallableUnit> it = matches.iterator(); it.hasNext();) {
+									current = it.next();
+									if (nonGreedyIUs.contains(current)) {
+										addNonGreedyProvider(getNonGreedyVariable(current), iu);
+									}
 								}
 							} else {
-								explanation = new Explanation.PatchedHardRequirement(iu, req, patch);
+								List<Object> newConstraint = new ArrayList<Object>();
+								for (Iterator<IInstallableUnit> it = matches.iterator(); it.hasNext();) {
+									current = it.next();
+									newConstraint.add(getNonGreedyVariable(current));
+								}
+								createImplication(new Object[] {iu}, newConstraint, new Explanation.HardRequirement(iu, req)); // FIXME
 							}
-							createImplication(new Object[] {patch, iu}, matches, explanation);
 						}
 					} else {
 						if (!matches.isEmpty()) {
-							AbstractVariable abs = getAbstractVariable();
-							createImplication(new Object[] {patch, abs, iu}, matches, Explanation.OPTIONAL_REQUIREMENT);
+							IInstallableUnit current;
+							AbstractVariable abs;
+							if (req.isGreedy()) {
+								abs = getAbstractVariable(req);
+								createImplication(new Object[] {patch, abs, iu}, matches, Explanation.OPTIONAL_REQUIREMENT);
+								for (Iterator<IInstallableUnit> it = matches.iterator(); it.hasNext();) {
+									current = it.next();
+									if (nonGreedyIUs.contains(current)) {
+										addNonGreedyProvider(getNonGreedyVariable(current), abs);
+									}
+								}
+							} else {
+								abs = getAbstractVariable(req, false);
+								List<Object> newConstraint = new ArrayList<Object>(matches.size());
+								for (Iterator<IInstallableUnit> it = matches.iterator(); it.hasNext();) {
+									current = it.next();
+									newConstraint.add(getNonGreedyVariable(current));
+								}
+								createImplication(new Object[] {patch, abs, iu}, newConstraint, Explanation.OPTIONAL_REQUIREMENT);
+							}
 							optionalAbstractRequirements.add(abs);
 						}
 					}
@@ -548,39 +658,79 @@ public class Projector {
 						if (matches.isEmpty()) {
 							dependencyHelper.implication(new Object[] {iu}).implies(patch).named(new Explanation.HardRequirement(iu, null));
 						} else {
+							// manage non greedy IUs
+							IInstallableUnit current;
+							List<Object> nonGreedys = new ArrayList<Object>();
+							for (Iterator<IInstallableUnit> it = matches.iterator(); it.hasNext();) {
+								current = it.next();
+								if (nonGreedyIUs.contains(current)) {
+									nonGreedys.add(getNonGreedyVariable(current));
+								}
+							}
 							matches.add(patch);
-							IInstallableUnit reqIu = matches.get(0);///(IInstallableUnit) picker.query(new CapabilityQuery(req), new Collector(), null).iterator().next();
-
-							Explanation explanation;
-							if (isRootIu) {
-								if (alreadyInstalledIUs.contains(reqIu)) {
-									explanation = new Explanation.IUInstalled(reqIu);
+							if (req.isGreedy()) {
+								IInstallableUnit reqIu = matches.get(0);///(IInstallableUnit) picker.query(new CapabilityQuery(req), new Collector(), null).iterator().next();
+								Explanation explanation;
+								if (isRootIu) {
+									if (alreadyInstalledIUs.contains(reqIu)) {
+										explanation = new Explanation.IUInstalled(reqIu);
+									} else {
+										explanation = new Explanation.IUToInstall(reqIu);
+									}
 								} else {
-									explanation = new Explanation.IUToInstall(reqIu);
+									explanation = new Explanation.HardRequirement(iu, req);
+								}
+
+								// Fix: make sure we collect all patches that will impact this IU-req, not just one
+								pending = new Pending();
+								pending.left = iu;
+								pending.explanation = explanation;
+								pending.matches = matches;
+								nonPatchedRequirements.put(req, pending);
+								for (Iterator<IInstallableUnit> it = matches.iterator(); it.hasNext();) {
+									current = it.next();
+									if (nonGreedyIUs.contains(current)) {
+										addNonGreedyProvider(getNonGreedyVariable(current), iu);
+									}
 								}
 							} else {
-								explanation = new Explanation.HardRequirement(iu, req);
+								List<Object> newConstraint = new ArrayList<Object>(matches.size());
+								for (Iterator<IInstallableUnit> it = matches.iterator(); it.hasNext();) {
+									current = it.next();
+									newConstraint.add(getNonGreedyVariable(current));
+								}
+								createImplication(new Object[] {iu}, newConstraint, new Explanation.HardRequirement(iu, req)); // FIXME
 							}
-
-							// Fix: make sure we collect all patches that will impact this IU-req, not just one
-							pending = new Pending();
-							pending.left = iu;
-							pending.explanation = explanation;
-							pending.matches = matches;
-							nonPatchedRequirements.put(req, pending);
 						}
 					} else {
 						if (!matches.isEmpty()) {
-							AbstractVariable abs = getAbstractVariable();
+							IInstallableUnit current;
+							AbstractVariable abs;
 							matches.add(patch);
-
-							// Fix: make sure we collect all patches that will impact this IU-req, not just one
-							pending = new Pending();
-							pending.left = new Object[] {abs, iu};
-							pending.explanation = Explanation.OPTIONAL_REQUIREMENT;
-							pending.matches = matches;
-							nonPatchedRequirements.put(req, pending);
-
+							if (req.isGreedy()) {
+								abs = getAbstractVariable(req);
+								// Fix: make sure we collect all patches that will impact this IU-req, not just one
+								pending = new Pending();
+								pending.left = new Object[] {abs, iu};
+								pending.explanation = Explanation.OPTIONAL_REQUIREMENT;
+								pending.matches = matches;
+								nonPatchedRequirements.put(req, pending);
+								for (Iterator<IInstallableUnit> it = matches.iterator(); it.hasNext();) {
+									current = it.next();
+									if (nonGreedyIUs.contains(current)) {
+										addNonGreedyProvider(getNonGreedyVariable(current), abs);
+									}
+								}
+							} else {
+								abs = getAbstractVariable(req, false);
+								List<Object> newConstraint = new ArrayList<Object>(matches.size());
+								for (Iterator<IInstallableUnit> it = matches.iterator(); it.hasNext();) {
+									current = it.next();
+									newConstraint.add(getNonGreedyVariable(current));
+								}
+								newConstraint.add(patch);
+								createImplication(new Object[] {abs, iu}, newConstraint, new Explanation.HardRequirement(iu, req)); // FIXME
+							}
 							optionalAbstractRequirements.add(abs);
 						}
 					}
@@ -617,27 +767,69 @@ public class Projector {
 						createImplication(iu, requiredPatches, new Explanation.HardRequirement(iu, req));
 					}
 				} else {
+					// manage non greedy IUs
+					IInstallableUnit current;
+					List<Object> nonGreedys = new ArrayList<Object>(matches.size());
+					for (Iterator<IInstallableUnit> it = matches.iterator(); it.hasNext();) {
+						current = it.next();
+						if (nonGreedyIUs.contains(current)) {
+							nonGreedys.add(getNonGreedyVariable(current));
+						}
+					}
 					if (!requiredPatches.isEmpty())
 						matches.addAll(requiredPatches);
-					IInstallableUnit reqIu = matches.get(0);//(IInstallableUnit) picker.query(new CapabilityQuery(req), new Collector(), null).iterator().next();
-					Explanation explanation;
-					if (isRootIu) {
-						if (alreadyInstalledIUs.contains(reqIu)) {
-							explanation = new Explanation.IUInstalled(reqIu);
+					if (req.isGreedy()) {
+						IInstallableUnit reqIu = matches.get(0);
+						Explanation explanation;
+						if (isRootIu) {
+							if (alreadyInstalledIUs.contains(reqIu)) {
+								explanation = new Explanation.IUInstalled(reqIu);
+							} else {
+								explanation = new Explanation.IUToInstall(reqIu);
+							}
 						} else {
-							explanation = new Explanation.IUToInstall(reqIu);
+							explanation = new Explanation.HardRequirement(iu, req);
+						}
+						createImplication(iu, matches, explanation);
+						for (Iterator<IInstallableUnit> it = matches.iterator(); it.hasNext();) {
+							current = it.next();
+							if (nonGreedyIUs.contains(current)) {
+								addNonGreedyProvider(getNonGreedyVariable(current), iu);
+							}
 						}
 					} else {
-						explanation = new Explanation.HardRequirement(iu, req);
+						List<Object> newConstraint = new ArrayList<Object>(matches.size());
+						for (Iterator<IInstallableUnit> it = matches.iterator(); it.hasNext();) {
+							current = it.next();
+							newConstraint.add(getNonGreedyVariable(current));
+						}
+						createImplication(new Object[] {iu}, newConstraint, new Explanation.HardRequirement(iu, req)); // FIXME
 					}
-					createImplication(iu, matches, explanation);
 				}
 			} else {
 				if (!matches.isEmpty()) {
+					IInstallableUnit current;
 					if (!requiredPatches.isEmpty())
 						matches.addAll(requiredPatches);
-					AbstractVariable abs = getAbstractVariable();
-					createImplication(new Object[] {abs, iu}, matches, Explanation.OPTIONAL_REQUIREMENT);
+					AbstractVariable abs;
+					if (req.isGreedy()) {
+						abs = getAbstractVariable(req);
+						createImplication(new Object[] {abs, iu}, matches, Explanation.OPTIONAL_REQUIREMENT);
+						for (Iterator<IInstallableUnit> it = matches.iterator(); it.hasNext();) {
+							current = it.next();
+							if (nonGreedyIUs.contains(current)) {
+								addNonGreedyProvider(getNonGreedyVariable(current), iu);
+							}
+						}
+					} else {
+						abs = getAbstractVariable(req, false);
+						List<Object> newConstraint = new ArrayList<Object>(matches.size());
+						for (Iterator<IInstallableUnit> it = matches.iterator(); it.hasNext();) {
+							current = it.next();
+							newConstraint.add(getNonGreedyVariable(current));
+						}
+						createImplication(new Object[] {abs, iu}, newConstraint, new Explanation.HardRequirement(iu, req)); // FIXME
+					}
 					optionalAbstractRequirements.add(abs);
 				}
 			}
@@ -820,21 +1012,36 @@ public class Projector {
 		dependencyHelper.atMost(1, (Object[]) vars).named(Explanation.OPTIONAL_REQUIREMENT);
 	}
 
-	private AbstractVariable getAbstractVariable() {
-		AbstractVariable abstractVariable = new AbstractVariable();
-		abstractVariables.add(abstractVariable);
+	private AbstractVariable getAbstractVariable(IRequirement req) {
+		return getAbstractVariable(req, true);
+	}
+
+	private AbstractVariable getAbstractVariable(IRequirement req, boolean appearInOptFunction) {
+		AbstractVariable abstractVariable = DEBUG_ENCODING ? new AbstractVariable("Abs_" + req.toString()) : new AbstractVariable(); //$NON-NLS-1$
+		if (appearInOptFunction) {
+			abstractVariables.add(abstractVariable);
+		}
 		return abstractVariable;
 	}
 
 	private AbstractVariable getNoOperationVariable(IInstallableUnit iu) {
 		AbstractVariable v = noopVariables.get(iu);
 		if (v == null) {
-			v = new AbstractVariable();
+			v = DEBUG_ENCODING ? new AbstractVariable("Noop_" + iu.toString()) : new AbstractVariable(); //$NON-NLS-1$
 			noopVariables.put(iu, v);
 		}
 		return v;
 	}
 
+	private AbstractVariable getNonGreedyVariable(IInstallableUnit iu) {
+		AbstractVariable v = nonGreedyVariables.get(iu);
+		if (v == null) {
+			v = DEBUG_ENCODING ? new AbstractVariable("NG_" + iu.toString()) : new AbstractVariable(); //$NON-NLS-1$
+			nonGreedyVariables.put(iu, v);
+		}
+		return v;
+	}
+
 	public IStatus invokeSolver(IProgressMonitor monitor) {
 		if (result.getSeverity() == IStatus.ERROR)
 			return result;
diff --git a/bundles/org.eclipse.equinox.p2.director/src/org/eclipse/equinox/internal/p2/director/SimplePlanner.java b/bundles/org.eclipse.equinox.p2.director/src/org/eclipse/equinox/internal/p2/director/SimplePlanner.java
index 192fdfe67..bc34b2bb9 100644
--- a/bundles/org.eclipse.equinox.p2.director/src/org/eclipse/equinox/internal/p2/director/SimplePlanner.java
+++ b/bundles/org.eclipse.equinox.p2.director/src/org/eclipse/equinox/internal/p2/director/SimplePlanner.java
@@ -296,12 +296,13 @@ public class SimplePlanner implements IPlanner {
 
 			Slicer slicer = new Slicer(new QueryableArray(availableIUs), newSelectionContext, satisfyMetaRequirements(profileChangeRequest.getProfileProperties()));
 			IQueryable<IInstallableUnit> slice = slicer.slice(new IInstallableUnit[] {(IInstallableUnit) updatedPlan[0]}, sub.newChild(ExpandWork / 4));
+			slicer.getNonGreedyIUs();
 			if (slice == null) {
 				IProvisioningPlan plan = engine.createPlan(profile, context);
 				plan.setStatus(slicer.getStatus());
 				return plan;
 			}
-			Projector projector = new Projector(slice, newSelectionContext, satisfyMetaRequirements(profileChangeRequest.getProfileProperties()));
+			Projector projector = new Projector(slice, newSelectionContext, slicer.getNonGreedyIUs(), satisfyMetaRequirements(profileChangeRequest.getProfileProperties()));
 			projector.encode((IInstallableUnit) updatedPlan[0], (IInstallableUnit[]) updatedPlan[1], profile, profileChangeRequest.getAdditions(), sub.newChild(ExpandWork / 4));
 			IStatus s = projector.invokeSolver(sub.newChild(ExpandWork / 4));
 			if (s.getSeverity() == IStatus.CANCEL) {
diff --git a/bundles/org.eclipse.equinox.p2.director/src/org/eclipse/equinox/internal/p2/director/Slicer.java b/bundles/org.eclipse.equinox.p2.director/src/org/eclipse/equinox/internal/p2/director/Slicer.java
index fa32c6b70..dff0c135f 100644
--- a/bundles/org.eclipse.equinox.p2.director/src/org/eclipse/equinox/internal/p2/director/Slicer.java
+++ b/bundles/org.eclipse.equinox.p2.director/src/org/eclipse/equinox/internal/p2/director/Slicer.java
@@ -7,6 +7,7 @@
  * 
  *  Contributors:
  *      IBM Corporation - initial API and implementation
+ *      Sonatype, Inc. - ongoing development
  *******************************************************************************/
 package org.eclipse.equinox.internal.p2.director;
 
@@ -30,6 +31,7 @@ public class Slicer {
 
 	private LinkedList<IInstallableUnit> toProcess;
 	private Set<IInstallableUnit> considered; //IUs to add to the slice
+	private Set<IInstallableUnit> nonGreedyIUs = new HashSet<IInstallableUnit>(); //IUs that are brought in by non greedy dependencies
 
 	public Slicer(IQueryable<IInstallableUnit> input, Map<String, String> context, boolean considerMetaRequirements) {
 		this(input, InstallableUnit.contextIU(context), considerMetaRequirements);
@@ -119,6 +121,7 @@ public class Slicer {
 				continue;
 
 			if (!isGreedy(req)) {
+				nonGreedyIUs.addAll(possibilites.query(QueryUtil.createMatchQuery(req.getMatches()), null).toUnmodifiableSet());
 				continue;
 			}
 
@@ -186,4 +189,8 @@ public class Slicer {
 		if (considered.add(match))
 			toProcess.addLast(match);
 	}
+
+	Set<IInstallableUnit> getNonGreedyIUs() {
+		return nonGreedyIUs;
+	}
 }
diff --git a/bundles/org.eclipse.equinox.p2.director/src/org/eclipse/equinox/internal/p2/director/messages.properties b/bundles/org.eclipse.equinox.p2.director/src/org/eclipse/equinox/internal/p2/director/messages.properties
index e89ea2452..e52f3df51 100644
--- a/bundles/org.eclipse.equinox.p2.director/src/org/eclipse/equinox/internal/p2/director/messages.properties
+++ b/bundles/org.eclipse.equinox.p2.director/src/org/eclipse/equinox/internal/p2/director/messages.properties
@@ -23,6 +23,7 @@ Explanation_fromPatch=From Patch: {0}
 Explanation_hardDependency=Cannot satisfy dependency: {0} depends on: {1}
 Explanation_patchedHardDependency=Cannot satisfy patched ({0}) dependency: {1} depends on: {2}
 Explanation_missingRequired=Missing requirement: {0} requires ''{1}'' but it could not be found
+Explanation_missingNonGreedyRequired=Missing non greedy requirement: ''{0}'' is required non greedily but it could not be found
 Explanation_missingRequiredFilter=Missing requirement for filter {0}: {1} requires ''{2}'' but it could not be found
 Explanation_optionalDependency=Optional dependency
 Explanation_rootMissing=Cannot complete the install because one or more required items could not be found.