|
// Copyright (c) .NET Foundation. All rights reserved.
// Licensed under the Apache License, Version 2.0. See License.txt in the project root for license information.
#nullable disable
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
namespace NuGet.Resolver
{
/// <summary>
/// This class is responsible for finding the best combination of compatible items. The caller
/// supplies a collection of groups, a sorting function (to determine priority within a group), and
/// a function to determine whether two items are incompatible. The solution (if found) will contain
/// exactly 1 item from each group.
/// </summary>
/// <remarks>Created by Aaron Marten</remarks>
/// <typeparam name="T">The type of item to evaluate.</typeparam>
public class CombinationSolver<T>
{
private readonly T[] _solution;
/// <summary>
/// The initial domains are the full/initial candidate sets we start with when
/// attempting to discover a solution. They need to be stored and referred to
/// as the algorithm executes to re-initialize the current/working domains.
/// </summary>
private readonly IList<IEnumerable<T>> _initialDomains;
/// <summary>
/// The current domains are initialized with the initial domains. As we progress
/// through the algorithm, we may remove elements from the current domain as we
/// discover that an item cannot be part of the solution. If we need to backtrack,
/// we may reset the current domain to the corresponding initial domain.
/// </summary>
private readonly List<HashSet<T>> _currentDomains;
private readonly List<List<T>> _currentDomainsSorted;
/// <summary>
/// The subset of past indexes where a conflict was found. Used to calculate the biggest and safest
/// (i.e. not missing a better solution) jump we can make in MoveBackward.
/// </summary>
private readonly List<HashSet<int>> _conflictSet;
/// <summary>
/// For each position, maintain a stack of past indexes that forward checked (and found/removed conflicts)
/// from the position.
/// </summary>
private readonly List<Stack<int>> _pastForwardChecking;
/// <summary>
/// For each position, maintain a stack of forward/future indexes where conflicts were found.
/// </summary>
private readonly List<Stack<int>> _futureForwardChecking;
/// <summary>
/// For each position, maintain a Stack of sets of items that were 'reduced' from the domain. This allows us
/// to restore the items back into the domain on future iterations in case we need to back up, etc...
/// </summary>
private readonly List<Stack<Stack<T>>> _reductions;
private readonly IComparer<T> _prioritySorter;
private readonly Func<T, T, bool> _shouldRejectPair;
private CombinationSolver(IEnumerable<IEnumerable<T>> groupedItems,
IComparer<T> itemSorter,
Func<T, T, bool> shouldRejectPairFunc)
{
_prioritySorter = itemSorter;
_shouldRejectPair = shouldRejectPairFunc;
var initialDomains = groupedItems.ToList();
_initialDomains = groupedItems.ToList();
// Initialize various arrays required for the algorithm to run.
_currentDomains = initialDomains.Select(d => new HashSet<T>(d)).ToList();
_currentDomainsSorted = initialDomains.Select(d => new List<T>(d)).ToList();
foreach (var list in _currentDomainsSorted)
{
list.Sort(_prioritySorter);
}
_conflictSet = initialDomains.Select(d => new HashSet<int>()).ToList();
_pastForwardChecking = initialDomains.Select(d => new Stack<int>()).ToList();
_futureForwardChecking = initialDomains.Select(d => new Stack<int>()).ToList();
_reductions = initialDomains.Select(d => new Stack<Stack<T>>()).ToList();
_solution = new T[initialDomains.Count];
}
/// <summary>
/// Entry point for the combination evalutation phase of the algorithm. The algorithm
/// combines forward checking [FC] (i.e. trying to eliminate future possible combinations to evaluate)
/// with Conflict-directed Back Jumping.
/// Based off the FC-CBJ algorithm described in Prosser's Hybrid
/// Algorithms for the Constraint Satisfaction Problem:
/// http://archive.nyu.edu/bitstream/2451/14410/1/IS-90-10.pdf
/// </summary>
/// <param name="groupedItems">The candidate enlistment items grouped by product.</param>
/// <param name="itemSorter">
/// Function supplied by the caller to sort items in preferred/priority order. 'Higher
/// priority' items should come *first* in the sort.
/// </param>
/// <param name="shouldRejectPairFunc">
/// Function supplied by the caller to determine whether two items are
/// compatible or not.
/// </param>
/// <param name="diagnosticOutput">
/// Used to provide partial solutions to be used for diagnostic messages.
/// </param>
/// <returns>The 'best' solution (if one exists). Null otherwise.</returns>
public static IEnumerable<T> FindSolution(IEnumerable<IEnumerable<T>> groupedItems,
IComparer<T> itemSorter,
Func<T, T, bool> shouldRejectPairFunc,
Action<IEnumerable<T>> diagnosticOutput)
{
var solver = new CombinationSolver<T>(groupedItems,
itemSorter,
shouldRejectPairFunc);
return solver.FindSolution(diagnosticOutput);
}
private IEnumerable<T> FindSolution(Action<IEnumerable<T>> diagnosticOutput)
{
var consistent = true;
var i = 0;
var highest = -1;
var limit = 0;
while (true)
{
if (!consistent)
{
limit++;
if (limit > 10000)
{
return null;
}
}
i = consistent ? MoveForward(i, ref consistent) : MoveBackward(i, ref consistent);
if (diagnosticOutput != null && i > highest)
{
highest = i;
// if a diagnostic hook was passed in give it each new best solution as it occurs
// create a new list since this method reuses the solution array
diagnosticOutput(new List<T>(_solution));
}
if (i > _solution.Length)
{
Debug.Fail("Evaluated past the end of the array.");
throw new NuGetResolverException(Strings.FatalError);
}
else if (i == _solution.Length)
{
return _solution;
}
else if (i < 0)
{
// Impossible (no solution)
return null;
}
}
}
/// <summary>
/// Attempts to populate the element at position i with a consistent possibility
/// and move forward to the next element in the sequence.
/// </summary>
/// <param name="i">The position in the solution to attempt to populate.</param>
/// <param name="consistent">
/// Upon completion, set to true if the function was able to find a candidate to
/// populate position i with. False otherwise.
/// </param>
/// <returns>
/// The next position to evaluate if consistent is true. If false, return value is the value to move
/// back to.
/// </returns>
private int MoveForward(int i, ref bool consistent)
{
consistent = false;
//Call ToList so we can potentially remove the currentItem from currentDomains[i] as we're iterating
foreach (var currentItem in GetSortedList(i))
{
if (consistent)
{
break;
}
consistent = true;
_solution[i] = currentItem;
for (var j = i + 1; j < _currentDomains.Count && consistent; j++)
{
consistent = CheckForward(i, j);
if (!consistent)
{
_currentDomains[i].Remove(currentItem);
UndoReductions(i);
_conflictSet[i].UnionWith(_pastForwardChecking[j]);
}
}
}
return consistent ? i + 1 : i;
}
/// <summary>
/// Attempts to move back in the algorithm from position i.
/// </summary>
/// <param name="i">The position to unset / move back from.</param>
/// <param name="consistent">
/// True if backwards move was successful and algorithm can move forward again. False
/// if the algorithm should continue to move backwards.
/// </param>
/// <returns>The position that the call was able to safely move back to.</returns>
private int MoveBackward(int i, ref bool consistent)
{
if (i < 0
|| i >= _solution.Length)
{
Debug.Fail("MoveBackward called with invalid value for i.");
throw new NuGetResolverException(Strings.FatalError);
}
if (i == 0
&& !consistent)
{
//We're being asked to back up from the starting position. No solution is possible.
return -1;
}
var max = new Func<IEnumerable<int>, int>(enumerable => (enumerable == null || !enumerable.Any()) ? 0 : enumerable.Max());
//h is the index we can *safely* move back to
var h = Math.Max(max(_conflictSet[i]), max(_pastForwardChecking[i]));
_conflictSet[h] = new HashSet<int>(_conflictSet[i].Union(_pastForwardChecking[i]).Union(_conflictSet[h]).Except(new[] { h }));
for (var j = i; j > h; j--)
{
_conflictSet[j].Clear();
UndoReductions(j);
UpdateCurrentDomain(j);
}
UndoReductions(h);
_currentDomains[h].Remove(_solution[h]);
consistent = _currentDomains[h] != null && _currentDomains[h].Any();
return h;
}
/// <summary>
/// Performs forward checking between the already selected element at position i
/// and potential candidates at position j.
/// </summary>
/// <param name="i">The position of the current element.</param>
/// <param name="j">The position of the future domain to check against.</param>
/// <returns>
/// True if there are still remaining possibilities in the future domain. False if all possibilities
/// have been eliminated.
/// </returns>
private bool CheckForward(int i, int j)
{
var reductionAgainstFutureDomain = new Stack<T>();
foreach (var itemInFutureDomain in GetSortedList(j))
{
_solution[j] = itemInFutureDomain;
if (_shouldRejectPair(_solution[i], _solution[j]))
{
reductionAgainstFutureDomain.Push(itemInFutureDomain);
}
}
if (reductionAgainstFutureDomain.Count > 0)
{
//Remove the items from the future domain
_currentDomains[j].ExceptWith(reductionAgainstFutureDomain);
//Store the items we just removed as a 'reduction' against the future domain.
_reductions[j].Push(reductionAgainstFutureDomain);
//Record that we've done future forward checking/reduction from i=>j
_futureForwardChecking[i].Push(j);
//Likewise in the past array, store that we've done forward checking/reduction from j=>i
_pastForwardChecking[j].Push(i);
}
return _currentDomains[j].Count > 0;
}
/// <summary>
/// Undo reductions that were previously performed from position i.
/// </summary>
/// <param name="i">The position to undo reductions from.</param>
private void UndoReductions(int i)
{
foreach (var j in _futureForwardChecking[i])
{
var reduction = _reductions[j].Pop();
_currentDomains[j].UnionWith(reduction);
var pfc = _pastForwardChecking[j].Pop();
Debug.Assert(i == pfc);
}
_futureForwardChecking[i].Clear();
}
/// <summary>
/// Reinitialize the current domain to its initial value and apply any reductions against it.
/// </summary>
/// <param name="i">The position of the domain to update.</param>
private void UpdateCurrentDomain(int i)
{
// Initialize it to the original domain values. Since currentDomain[i] will be
// manipulated throughout the algorithm, it is critical to create a *new* set at this
// point to avoid having initialDomains[i] be tampered with.
_currentDomains[i] = new HashSet<T>(_initialDomains[i]);
//Remove any current reduction items
foreach (var reduction in _reductions[i])
{
_currentDomains[i].ExceptWith(reduction);
}
}
private IEnumerable<T> GetSortedList(int pos)
{
var subSet = _currentDomains[pos];
var sorted = _currentDomainsSorted[pos];
if (subSet.Count == sorted.Count)
{
foreach (var item in sorted)
{
yield return item;
}
}
else
{
foreach (var item in sorted)
{
if (subSet.Contains(item))
{
yield return item;
}
}
}
yield break;
}
}
}
|