org.eclipse.equinox.p2.cudf/src/main/java/org/eclipse/equinox/p2/cudf/solver/Slicer.java

/*******************************************************************************
 *  Copyright (c) 2007, 2009 IBM Corporation 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:
 *      IBM Corporation - initial API and implementation
 *******************************************************************************/
package org.eclipse.equinox.p2.cudf.solver;

import java.util.*;
import org.eclipse.core.runtime.*;
import org.eclipse.equinox.p2.cudf.Log;
import org.eclipse.equinox.p2.cudf.Main;
import org.eclipse.equinox.p2.cudf.metadata.*;
import org.eclipse.equinox.p2.cudf.query.*;
import org.eclipse.osgi.util.NLS;

public class Slicer {
	private static boolean TIMING = false; //SET THIS TO FALSE FOR THE COMPETITION
	private QueryableArray possibilites;

	private LinkedList toProcess;
	private Set considered; //IUs to add to the slice
	private TwoTierMap slice; //The IUs that have been considered to be part of the problem

	private MultiStatus result;

	public Slicer(QueryableArray input) {
		possibilites = input;
		slice = new TwoTierMap();
		result = new MultiStatus(Main.PLUGIN_ID, IStatus.OK, Messages.Planner_Problems_resolving_plan, null);
	}

	private void handleExtraRequirements(List extraRequirements) {
		if (extraRequirements != null)
			for (Iterator iterator = extraRequirements.iterator(); iterator.hasNext();) {
				expandRequirement(null, (IRequiredCapability) iterator.next());
			}
	}

	public QueryableArray slice(InstallableUnit ius, List extraRequirements) {
		try {
			IProgressMonitor monitor = new NullProgressMonitor();
			long start = 0;
			if (TIMING) {
				start = System.currentTimeMillis();
			}

			considered = new HashSet(possibilites.getSize());
			considered.add(ius);
			toProcess = new LinkedList(considered);
			handleExtraRequirements(extraRequirements);
			while (!toProcess.isEmpty()) {
				if (monitor.isCanceled()) {
					result.merge(Status.CANCEL_STATUS);
					throw new OperationCanceledException();
				}
				processIU((InstallableUnit) toProcess.removeFirst());
			}
			if (TIMING) {
				long stop = System.currentTimeMillis();
				Log.println("# Slicing complete: " + (stop - start)); //$NON-NLS-1$
			}
		} catch (IllegalStateException e) {
			result.add(new Status(IStatus.ERROR, Main.PLUGIN_ID, e.getMessage(), e));
		}
		//		if (Tracing.DEBUG && result.getSeverity() != IStatus.OK)
		//			LogHelper.log(result);
		if (result.getSeverity() == IStatus.ERROR)
			return null;
		return new QueryableArray((InstallableUnit[]) considered.toArray(new InstallableUnit[considered.size()]));
	}

	public MultiStatus getStatus() {
		return result;
	}

	protected void processIU(InstallableUnit iu) {
		slice.put(iu.getId(), iu.getVersion(), iu);

		addHighestVersion(iu);
		IRequiredCapability[] reqs = getRequiredCapabilities(iu);
		if (reqs.length == 0) {
			return;
		}
		for (int i = 0; i < reqs.length; i++) {
			expandRequirement(iu, reqs[i]);
		}
	}

	//Get the highest version available for the given IU 
	private void addHighestVersion(InstallableUnit iu) {
		Collector matches = possibilites.query(new CapabilityQuery(new RequiredCapability(iu.getId(), VersionRange.emptyRange, 1)), new Collector(), null);
		if (matches.size() == 1 || matches.size() == 0)
			return;

		InstallableUnit highestVersion = iu;
		for (Iterator iterator = matches.iterator(); iterator.hasNext();) {
			InstallableUnit candidate = (InstallableUnit) iterator.next();
			if (candidate.getId().equals(iu.getId())) {
				if (candidate.getVersion().getMajor() > highestVersion.getVersion().getMajor())
					highestVersion = candidate;
			}
		}
		//We only need to 
		if (highestVersion != iu)
			considered.add(highestVersion);

	}

	private IRequiredCapability[] getRequiredCapabilities(InstallableUnit iu) {
		return iu.getRequiredCapabilities();
	}

	private void expandRequirement(InstallableUnit iu, IRequiredCapability req) {
		if (req.isNegation())
			return;
		Collector matches = possibilites.query(new CapabilityQuery(req), new Collector(), null);
		int validMatches = 0;
		for (Iterator iterator = matches.iterator(); iterator.hasNext();) {
			InstallableUnit match = (InstallableUnit) iterator.next();
			validMatches++;
			if (!slice.containsKey(match.getId(), match.getVersion()))
				consider(match);
		}

		if (validMatches == 0) {
			if (req.isOptional()) {
				if (TIMING)
					Log.println("No IU found to satisfy optional dependency of " + iu + " on req " + req); //$NON-NLS-1$//$NON-NLS-2$
			} else {
				result.add(new Status(IStatus.WARNING, Main.PLUGIN_ID, NLS.bind(Messages.Planner_Unsatisfied_dependency, iu, req)));
			}
		}
	}

	private void consider(InstallableUnit match) {
		if (considered.add(match))
			toProcess.addLast(match);
	}
}