Skip to content

Tail Recursive Package Resolution #2066

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
forki merged 12 commits into from
Dec 13, 2016
Merged

Tail Recursive Package Resolution #2066

Changes from 1 commit
Commits
Show all changes
12 commits
Select commit Hold shift + click to select a range
74f8596
stackpack and debug & structured displays
cloudRoutine Dec 1, 2016
e1baab5
step and steploop can stand independently
cloudRoutine Dec 2, 2016
5a64291
reorganize step function
cloudRoutine Dec 2, 2016
14034ef
maintain lists of floating conflicts and steps
cloudRoutine Dec 3, 2016
65b29e7
tail recursive package resolution
cloudRoutine Dec 3, 2016
cd6d161
update mono check
cloudRoutine Dec 3, 2016
abaebbf
fix flag in outer loop stage
cloudRoutine Dec 3, 2016
fd1108f
more detailed verbose output
cloudRoutine Dec 4, 2016
677b862
additional flag to track an unlisted package search inner step loop
cloudRoutine Dec 5, 2016
804165c
use correct cli version on travis
cloudRoutine Dec 5, 2016
b5b1491
back to magic mode
cloudRoutine Dec 12, 2016
7d6f95c
don't run 'dotnet pack'
cloudRoutine Dec 12, 2016
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
maintain lists of floating conflicts and steps
  • Loading branch information
@cloudRoutine
cloudRoutine committed Dec 3, 2016
commit 14034ef8e0be95c339da2fc93e407a054dc847a0
101 changes: 51 additions & 50 deletions src/Paket.Core/PackageResolver.fs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -606,13 +606,13 @@ type private StepFlags (ready:bool,useUnlisted:bool,hasUnlisted:bool,forceBreak:

// While looping to evaluate a package resolution the 'dive conflict' is the one
// being actively processed. When this conflict needs to pause its evaluation
// to spawn a new child diveConflict it "floats" with it throughout the recursive
// to spawn a new child currentConflict it "floats" with it throughout the recursive
// evaluation. When the child diver has finished evaluating it will fuse with
// the floater to make a new conflictState that will resume the dive.
type private Stage =
| Step of diveConflict : ConflictState * floatConflict : ConflictState option
| Outer of diveConflict : ConflictState * floatConflict : ConflictState option
| Inner of diveConflict : ConflictState * floatConflict : ConflictState option
| Step of currentConflict : ConflictState * priorConflictSteps : (ConflictState * ResolverStep) list
| Outer of currentConflict : ConflictState * priorConflictSteps : (ConflictState * ResolverStep) list
| Inner of currentConflict : ConflictState * priorConflictSteps : (ConflictState * ResolverStep) list


/// Resolves all direct and transitive dependencies
Expand All @@ -639,32 +639,32 @@ let Resolve (getVersionsF, getPackageDetailsF, groupName:GroupName, globalStrate
flags.FirstTrial || Set.isEmpty conflictState.Conflicts


let rec step (stage:Stage) (currentStep:ResolverStep, floatStepOpt:ResolverStep option)
let rec step (stage:Stage) (currentStep:ResolverStep)
(stackpack:StackPack) (currentRequirement:PackageRequirement)
compatibleVersions (flags:StepFlags) =

let fuseConflicts diveConflict floatConflictOpt =
match diveConflict, floatConflictOpt with
| diveConflict, Some floatConflict ->
let fuseConflicts currentConflict priorConflictSteps =
match currentConflict, priorConflictSteps with
| currentConflict, (lastConflict,lastStep)::priorConflictSteps ->
let continueConflict =
{ diveConflict with VersionsToExplore = floatConflict.VersionsToExplore }
{ currentConflict with VersionsToExplore = lastConflict.VersionsToExplore }

step (Inner(continueConflict,None)) (currentStep,floatStepOpt) stackpack
step (Inner(continueConflict,priorConflictSteps)) lastStep stackpack
currentRequirement compatibleVersions flags
| diveConflict, None -> diveConflict
| currentConflict, [] -> currentConflict

match stage with
| Step (diveConflict, floatConflictOpt) ->
| Step (currentConflict, priorConflictSteps) ->
if Set.isEmpty currentStep.OpenRequirements then
let diveConflict =
{ diveConflict with
let currentConflict =
{ currentConflict with
Status = Resolution.Ok (cleanupNames currentStep.CurrentResolution) }

match diveConflict, floatConflictOpt, floatStepOpt with
| diveConflict, Some floatConflict, Some floatStep ->
match currentConflict, priorConflictSteps with
| currentConflict, (lastConflict,lastStep)::priorConflictSteps ->
let continueConflict = {
diveConflict with
VersionsToExplore = floatConflict.VersionsToExplore
currentConflict with
VersionsToExplore = lastConflict.VersionsToExplore
}
match continueConflict.Status with
| Resolution.Conflict (_,conflicts,_,_)
Expand All @@ -677,13 +677,13 @@ let Resolve (getVersionsF, getPackageDetailsF, groupName:GroupName, globalStrate
let flags =
StepFlags(flags.Ready,flags.UseUnlisted,flags.HasUnlisted,true,flags.FirstTrial)

step (Inner(continueConflict,None)) (floatStep,floatStepOpt) stackpack
step (Inner(continueConflict,priorConflictSteps)) lastStep stackpack
currentRequirement compatibleVersions flags
| _ ->
step (Inner(continueConflict,None)) (floatStep,floatStepOpt) stackpack
step (Inner(continueConflict,priorConflictSteps)) lastStep stackpack
currentRequirement compatibleVersions flags

| diveConflict, _, _ -> diveConflict
| currentConflict, [] -> currentConflict

else
verbosefn " %d packages in resolution. %d requirements left"
Expand All @@ -695,36 +695,36 @@ let Resolve (getVersionsF, getPackageDetailsF, groupName:GroupName, globalStrate
let conflicts =
getConflicts currentStep currentRequirement stackpack.KnownConflicts

let diveConflict =
let currentConflict =
if Set.isEmpty conflicts then
let getVersionsF = getVersionsF currentRequirement.Sources ResolverStrategy.Max groupName
{ diveConflict with
{ currentConflict with
Status = Resolution.Conflict(currentStep,Set.empty,currentRequirement,getVersionsF)}
else
let getVersionsF = getVersionsF currentRequirement.Sources ResolverStrategy.Max groupName
{ diveConflict with
{ currentConflict with
Status = Resolution.Conflict(currentStep,conflicts,Seq.head conflicts,getVersionsF)}

if not (Set.isEmpty conflicts) then
fuseConflicts diveConflict floatConflictOpt
fuseConflicts currentConflict priorConflictSteps
else
let compatibleVersions,globalOverride,tryRelaxed =
getCompatibleVersions currentStep groupName currentRequirement getVersionsF
diveConflict.GlobalOverride
currentConflict.GlobalOverride
globalStrategyForDirectDependencies
globalStrategyForTransitives

let diveConflict = {
diveConflict with
let currentConflict = {
currentConflict with
Conflicts = conflicts
TryRelaxed = tryRelaxed
GlobalOverride = globalOverride
}
let conflictState, stackpack =
if Seq.isEmpty compatibleVersions then
boostConflicts currentStep.FilteredVersions currentRequirement stackpack diveConflict
boostConflicts currentStep.FilteredVersions currentRequirement stackpack currentConflict
else
diveConflict, stackpack
currentConflict, stackpack
let flags =
StepFlags
( ready = false
Expand All @@ -733,37 +733,37 @@ let Resolve (getVersionsF, getPackageDetailsF, groupName:GroupName, globalStrate
, forceBreak = flags.ForceBreak
, firstTrial = flags.FirstTrial
)
step (Outer (conflictState,floatConflictOpt)) (currentStep,floatStepOpt) stackpack
step (Outer (conflictState,priorConflictSteps)) currentStep stackpack
currentRequirement compatibleVersions flags
| Outer (diveConflict, floatConflictOpt) ->
| Outer (currentConflict, priorConflictSteps) ->
if flags.Ready then
fuseConflicts diveConflict floatConflictOpt
fuseConflicts currentConflict priorConflictSteps
else
let flags = StepFlags(flags.Ready,flags.UseUnlisted,flags.HasUnlisted,false,true)

let diveConflict = { diveConflict with VersionsToExplore = compatibleVersions }
let currentConflict = { currentConflict with VersionsToExplore = compatibleVersions }

step (Inner (diveConflict, floatConflictOpt)) (currentStep,floatStepOpt) stackpack
step (Inner (currentConflict, priorConflictSteps)) currentStep stackpack
currentRequirement compatibleVersions flags

| Inner (diveConflict, floatConflictOpt)->
if not (keepLooping flags diveConflict) then
| Inner (currentConflict, priorConflictSteps)->
if not (keepLooping flags currentConflict) then
let flags =
if not flags.UseUnlisted
&& flags.HasUnlisted
&& not diveConflict.Status.IsDone then
&& not currentConflict.Status.IsDone then
StepFlags(flags.Ready,true,flags.HasUnlisted,flags.ForceBreak,flags.FirstTrial)
else
StepFlags(true,flags.UseUnlisted,flags.HasUnlisted,flags.ForceBreak,flags.FirstTrial)

step (Outer(diveConflict, floatConflictOpt)) (currentStep,floatStepOpt) stackpack
step (Outer(currentConflict, priorConflictSteps)) currentStep stackpack
currentRequirement compatibleVersions flags
else
let flags = StepFlags(flags.Ready,flags.UseUnlisted,flags.HasUnlisted,flags.ForceBreak,false)
let (version,sources) & versionToExplore = Seq.head diveConflict.VersionsToExplore
let (version,sources) & versionToExplore = Seq.head currentConflict.VersionsToExplore

let diveConflict =
{ diveConflict with VersionsToExplore = Seq.tail diveConflict.VersionsToExplore }
let currentConflict =
{ currentConflict with VersionsToExplore = Seq.tail currentConflict.VersionsToExplore }

let packageDetails = {
GroupName = groupName
Expand All @@ -776,7 +776,7 @@ let Resolve (getVersionsF, getPackageDetailsF, groupName:GroupName, globalStrate
}
match getExploredPackage packageDetails getPackageDetailsF stackpack with
| stackpack, None ->
step (Inner(diveConflict, floatConflictOpt)) (currentStep,floatStepOpt) stackpack
step (Inner(currentConflict, priorConflictSteps)) currentStep stackpack
currentRequirement compatibleVersions flags

| stackpack, Some exploredPackage ->
Expand All @@ -785,12 +785,12 @@ let Resolve (getVersionsF, getPackageDetailsF, groupName:GroupName, globalStrate
StepFlags(flags.Ready,flags.UseUnlisted,hasUnlisted,flags.ForceBreak,flags.FirstTrial)
if exploredPackage.Unlisted && not flags.UseUnlisted then
tracefn " unlisted"
step (Inner (diveConflict, floatConflictOpt)) (currentStep,floatStepOpt) stackpack
step (Inner (currentConflict, priorConflictSteps)) currentStep stackpack
currentRequirement compatibleVersions flags
else
let nextStep =
{ Relax = currentStep.Relax
FilteredVersions = Map.add currentRequirement.Name ([versionToExplore],diveConflict.GlobalOverride) currentStep.FilteredVersions
FilteredVersions = Map.add currentRequirement.Name ([versionToExplore],currentConflict.GlobalOverride) currentStep.FilteredVersions
CurrentResolution = Map.add exploredPackage.Name exploredPackage currentStep.CurrentResolution
ClosedRequirements = Set.add currentRequirement currentStep.ClosedRequirements
OpenRequirements = calcOpenRequirements(exploredPackage,globalFrameworkRestrictions,versionToExplore,currentRequirement,currentStep)
Expand All @@ -799,7 +799,8 @@ let Resolve (getVersionsF, getPackageDetailsF, groupName:GroupName, globalStrate
failwithf "The resolver confused itself. The new open requirements are the same as the old ones.\n\
This will result in an endless loop.%sCurrent Requirement: %A%sRequirements: %A"
Environment.NewLine currentRequirement Environment.NewLine nextStep.OpenRequirements
step (Step(diveConflict,Some diveConflict)) (nextStep,Some currentStep) stackpack currentRequirement compatibleVersions flags

step (Step(currentConflict, (currentConflict,currentStep)::priorConflictSteps)) nextStep stackpack currentRequirement compatibleVersions flags


let startingStep = {
Expand All @@ -817,7 +818,7 @@ let Resolve (getVersionsF, getPackageDetailsF, groupName:GroupName, globalStrate
Resolution.Conflict(startingStep,Set.empty,currentRequirement,getVersionsF)


let diveConflict : ConflictState = {
let currentConflict : ConflictState = {
Status = (status : Resolution)
LastConflictReported = DateTime.Now
TryRelaxed = false
Expand All @@ -841,13 +842,13 @@ let Resolve (getVersionsF, getPackageDetailsF, groupName:GroupName, globalStrate
, firstTrial = true
)

match step (Step(diveConflict,None)) (startingStep,None) stackpack currentRequirement Seq.empty flags with
match step (Step(currentConflict,[])) (startingStep) stackpack currentRequirement Seq.empty flags with
| { Status = Resolution.Conflict _ } as conflict ->
if conflict.TryRelaxed then
stackpack.KnownConflicts.Clear()
stackpack.ConflictHistory.Clear()
(step (Step(conflict,None))
({startingStep with Relax=true},None)
(step (Step(conflict,[]))
{startingStep with Relax=true}
stackpack currentRequirement Seq.empty flags).Status
else
conflict.Status
Expand Down