From 1c6a939a88a462660e26c888a25a1ec617847b7c Mon Sep 17 00:00:00 2001 From: Pascal Rapicault Date: Mon, 18 Feb 2013 23:09:58 -0500 Subject: Extract optimization function to a new class --- .../internal/p2/director/OptimizationFunction.java | 151 +++++++++++++++++++++ .../equinox/internal/p2/director/Projector.java | 119 ++-------------- 2 files changed, 159 insertions(+), 111 deletions(-) create mode 100644 bundles/org.eclipse.equinox.p2.director/src/org/eclipse/equinox/internal/p2/director/OptimizationFunction.java (limited to 'bundles/org.eclipse.equinox.p2.director') diff --git a/bundles/org.eclipse.equinox.p2.director/src/org/eclipse/equinox/internal/p2/director/OptimizationFunction.java b/bundles/org.eclipse.equinox.p2.director/src/org/eclipse/equinox/internal/p2/director/OptimizationFunction.java new file mode 100644 index 000000000..55cc3811f --- /dev/null +++ b/bundles/org.eclipse.equinox.p2.director/src/org/eclipse/equinox/internal/p2/director/OptimizationFunction.java @@ -0,0 +1,151 @@ +/******************************************************************************* + * Copyright (c) 2013 Rapicorp 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: + * Rapicorp, Inc. - initial API and implementation + ******************************************************************************/ +package org.eclipse.equinox.internal.p2.director; + +import java.math.BigInteger; +import java.util.*; +import java.util.Map.Entry; +import org.eclipse.core.runtime.NullProgressMonitor; +import org.eclipse.equinox.internal.p2.core.helpers.CollectionUtils; +import org.eclipse.equinox.internal.p2.director.Projector.AbstractVariable; +import org.eclipse.equinox.p2.metadata.*; +import org.eclipse.equinox.p2.query.*; +import org.sat4j.pb.tools.WeightedObject; + +public class OptimizationFunction { + + private IQueryable picker; + private IInstallableUnit selectionContext; + private Map> slice; //The IUs that have been considered to be part of the problem + private int numberOfInstalledIUs; + private IQueryable lastState; + private List abstractVariables; + + // private IInstallableUnit[] alreadyExistingRoots; + // private IQueryable beingInstalled; + + public OptimizationFunction(IQueryable lastState, List abstractVariables, IQueryable picker, IInstallableUnit selectionContext, Map> slice) { + this.lastState = lastState; + this.abstractVariables = abstractVariables; + this.picker = picker; + this.selectionContext = selectionContext; + this.slice = slice; + } + + //Create an optimization function favoring the highest version of each IU + public List> createOptimizationFunction(IInstallableUnit metaIu, Collection newRoots) { + numberOfInstalledIUs = sizeOf(lastState); + List> weightedObjects = new ArrayList>(); + + Set transitiveClosure; + if (newRoots.isEmpty()) { + transitiveClosure = CollectionUtils.emptySet(); + } else { + IQueryable queryable = new Slicer(picker, selectionContext, false).slice(newRoots.toArray(new IInstallableUnit[newRoots.size()]), new NullProgressMonitor()); + if (queryable == null) { + transitiveClosure = CollectionUtils.emptySet(); + } else { + transitiveClosure = queryable.query(QueryUtil.ALL_UNITS, new NullProgressMonitor()).toSet(); + } + } + + Set>> s = slice.entrySet(); + final BigInteger POWER = BigInteger.valueOf(numberOfInstalledIUs > 0 ? numberOfInstalledIUs + 1 : 2); + + BigInteger maxWeight = POWER; + for (Entry> entry : s) { + List conflictingEntries = new ArrayList(entry.getValue().values()); + if (conflictingEntries.size() == 1) { + IInstallableUnit iu = conflictingEntries.get(0); + if (iu != metaIu) { + weightedObjects.add(WeightedObject.newWO(iu, POWER)); + } + continue; + } + // IUs are sorted from highest version to lowest. + Collections.sort(conflictingEntries, Collections.reverseOrder()); + BigInteger weight = POWER; + // have we already found a version that is already installed? + boolean foundInstalled = false; + // have we already found a version that is in the new roots? + boolean foundRoot = false; + for (IInstallableUnit iu : conflictingEntries) { + if (!foundRoot && isInstalled(iu) && !transitiveClosure.contains(iu)) { + foundInstalled = true; + weightedObjects.add(WeightedObject.newWO(iu, BigInteger.ONE)); + } else if (!foundInstalled && !foundRoot && isRoot(iu, newRoots)) { + foundRoot = true; + weightedObjects.add(WeightedObject.newWO(iu, BigInteger.ONE)); + } else { + weightedObjects.add(WeightedObject.newWO(iu, weight)); + } + weight = weight.multiply(POWER); + } + if (weight.compareTo(maxWeight) > 0) + maxWeight = weight; + } + + // no need to add one here, since maxWeight is strictly greater than the + // maximal weight used so far. + maxWeight = maxWeight.multiply(POWER).multiply(BigInteger.valueOf(s.size())); + + // Add the abstract variables + BigInteger abstractWeight = maxWeight.negate(); + for (AbstractVariable var : abstractVariables) { + weightedObjects.add(WeightedObject.newWO(var, abstractWeight)); + } + + maxWeight = maxWeight.multiply(POWER).add(BigInteger.ONE); + + BigInteger optionalWeight = maxWeight.negate(); + long countOptional = 1; + List requestedPatches = new ArrayList(); + Collection reqs = metaIu.getRequirements(); + for (IRequirement req : reqs) { + if (req.getMin() > 0 || !req.isGreedy()) + continue; + IQueryResult matches = picker.query(QueryUtil.createMatchQuery(req.getMatches()), null); + for (Iterator iterator = matches.iterator(); iterator.hasNext();) { + IInstallableUnit match = iterator.next(); + if (match instanceof IInstallableUnitPatch) { + requestedPatches.add(match); + countOptional = countOptional + 1; + } else { + weightedObjects.add(WeightedObject.newWO(match, optionalWeight)); + } + } + } + + BigInteger patchWeight = maxWeight.multiply(POWER).multiply(BigInteger.valueOf(countOptional)).negate(); + for (Iterator iterator = requestedPatches.iterator(); iterator.hasNext();) { + weightedObjects.add(WeightedObject.newWO(iterator.next(), patchWeight)); + } + return weightedObjects; + } + + protected boolean isInstalled(IInstallableUnit iu) { + return !lastState.query(QueryUtil.createIUQuery(iu), null).isEmpty(); + } + + private boolean isRoot(IInstallableUnit iu, Collection newRoots) { + return newRoots.contains(iu); + } + + /** + * Efficiently compute the size of a queryable + */ + private int sizeOf(IQueryable installedIUs) { + IQueryResult qr = installedIUs.query(QueryUtil.createIUAnyQuery(), null); + if (qr instanceof Collector) + return ((Collector) qr).size(); + return qr.toUnmodifiableSet().size(); + } + +} 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 fc1d28eea..59e8eb271 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 @@ -1,5 +1,5 @@ /******************************************************************************* - * Copyright (c) 2007, 2012 IBM Corporation and others. All rights reserved. This + * Copyright (c) 2007, 2013 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 @@ -10,10 +10,10 @@ * Alban Browaeys - Optimized string concatenation in bug 251357 * Jed Anderson - switch from opb files to API calls to DependencyHelper in bug 200380 * Sonatype, Inc. - ongoing development + * Rapicorp, Inc. - split the optimization function ******************************************************************************/ package org.eclipse.equinox.internal.p2.director; -import java.math.BigInteger; import java.util.*; import java.util.Map.Entry; import org.eclipse.core.runtime.*; @@ -73,8 +73,6 @@ public class Projector { private IInstallableUnit entryPoint; private Map> fragments = new HashMap>(); - private int numberOfInstalledIUs; - //Non greedy things private Set nonGreedyIUs; //All the IUs that would satisfy non greedy dependencies private Map nonGreedyVariables = new HashMap(); @@ -166,14 +164,14 @@ public class Projector { this.considerMetaRequirements = considerMetaRequirements; } - protected boolean isInstalled(IInstallableUnit iu) { - return !lastState.query(QueryUtil.createIUQuery(iu), null).isEmpty(); - } + // protected boolean isInstalled(IInstallableUnit iu) { + // return !lastState.query(QueryUtil.createIUQuery(iu), null).isEmpty(); + // } @SuppressWarnings("unchecked") public void encode(IInstallableUnit entryPointIU, IInstallableUnit[] alreadyExistingRoots, IQueryable installedIUs, Collection newRoots, IProgressMonitor monitor) { alreadyInstalledIUs = Arrays.asList(alreadyExistingRoots); - numberOfInstalledIUs = sizeOf(installedIUs); + // numberOfInstalledIUs = sizeOf(installedIUs); lastState = installedIUs; this.entryPoint = entryPointIU; try { @@ -257,111 +255,10 @@ public class Projector { } - /** - * Efficiently compute the size of a queryable - */ - private int sizeOf(IQueryable installedIUs) { - IQueryResult qr = installedIUs.query(QueryUtil.createIUAnyQuery(), null); - if (qr instanceof Collector) - return ((Collector) qr).size(); - return qr.toUnmodifiableSet().size(); - } - //Create an optimization function favoring the highest version of each IU private void createOptimizationFunction(IInstallableUnit metaIu, Collection newRoots) { - - List> weightedObjects = new ArrayList>(); - - Set transitiveClosure; - if (newRoots.isEmpty()) { - transitiveClosure = CollectionUtils.emptySet(); - } else { - IQueryable queryable = new Slicer(picker, selectionContext, false).slice(newRoots.toArray(new IInstallableUnit[newRoots.size()]), new NullProgressMonitor()); - if (queryable == null) { - transitiveClosure = CollectionUtils.emptySet(); - } else { - transitiveClosure = queryable.query(QueryUtil.ALL_UNITS, new NullProgressMonitor()).toSet(); - } - } - - Set>> s = slice.entrySet(); - final BigInteger POWER = BigInteger.valueOf(numberOfInstalledIUs > 0 ? numberOfInstalledIUs + 1 : 2); - - BigInteger maxWeight = POWER; - for (Entry> entry : s) { - List conflictingEntries = new ArrayList(entry.getValue().values()); - if (conflictingEntries.size() == 1) { - IInstallableUnit iu = conflictingEntries.get(0); - if (iu != metaIu) { - weightedObjects.add(WeightedObject.newWO(iu, POWER)); - } - continue; - } - // IUs are sorted from highest version to lowest. - Collections.sort(conflictingEntries, Collections.reverseOrder()); - BigInteger weight = POWER; - // have we already found a version that is already installed? - boolean foundInstalled = false; - // have we already found a version that is in the new roots? - boolean foundRoot = false; - for (IInstallableUnit iu : conflictingEntries) { - if (!foundRoot && isInstalled(iu) && !transitiveClosure.contains(iu)) { - foundInstalled = true; - weightedObjects.add(WeightedObject.newWO(iu, BigInteger.ONE)); - } else if (!foundInstalled && !foundRoot && isRoot(iu, newRoots)) { - foundRoot = true; - weightedObjects.add(WeightedObject.newWO(iu, BigInteger.ONE)); - } else { - weightedObjects.add(WeightedObject.newWO(iu, weight)); - } - weight = weight.multiply(POWER); - } - if (weight.compareTo(maxWeight) > 0) - maxWeight = weight; - } - - // no need to add one here, since maxWeight is strictly greater than the - // maximal weight used so far. - maxWeight = maxWeight.multiply(POWER).multiply(BigInteger.valueOf(s.size())); - - // Add the abstract variables - BigInteger abstractWeight = maxWeight.negate(); - for (AbstractVariable var : abstractVariables) { - weightedObjects.add(WeightedObject.newWO(var, abstractWeight)); - } - - maxWeight = maxWeight.multiply(POWER).add(BigInteger.ONE); - - BigInteger optionalWeight = maxWeight.negate(); - long countOptional = 1; - List requestedPatches = new ArrayList(); - Collection reqs = metaIu.getRequirements(); - for (IRequirement req : reqs) { - if (req.getMin() > 0 || !req.isGreedy()) - continue; - IQueryResult matches = picker.query(QueryUtil.createMatchQuery(req.getMatches()), null); - for (Iterator iterator = matches.iterator(); iterator.hasNext();) { - IInstallableUnit match = iterator.next(); - if (match instanceof IInstallableUnitPatch) { - requestedPatches.add(match); - countOptional = countOptional + 1; - } else { - weightedObjects.add(WeightedObject.newWO(match, optionalWeight)); - } - } - } - - BigInteger patchWeight = maxWeight.multiply(POWER).multiply(BigInteger.valueOf(countOptional)).negate(); - for (Iterator iterator = requestedPatches.iterator(); iterator.hasNext();) { - weightedObjects.add(WeightedObject.newWO(iterator.next(), patchWeight)); - } - if (!weightedObjects.isEmpty()) { - createObjectiveFunction(weightedObjects); - } - } - - private boolean isRoot(IInstallableUnit iu, Collection newRoots) { - return newRoots.contains(iu); + List> weights = new OptimizationFunction(lastState, abstractVariables, picker, selectionContext, slice).createOptimizationFunction(metaIu, newRoots); + createObjectiveFunction(weights); } private void createObjectiveFunction(List> weightedObjects) { -- cgit v1.2.3