in src/NuGet.Core/NuGet.Commands/RestoreCommand/DependencyGraphResolver.cs [313:750]
private static async Task<(bool Success, RestoreTargetGraph RestoreTargetGraph)> CreateRestoreTargetGraphAsync(
FrameworkRuntimeDefinition frameworkRuntimeDefinition,
RuntimeGraph? runtimeGraph,
bool isCentralPackageTransitivePinningEnabled,
HashSet<LibraryRange> unresolvedPackages,
HashSet<ResolvedDependencyKey> resolvedPackages,
Dictionary<LibraryDependencyIndex, ResolvedDependencyGraphItem> resolvedDependencyGraphItems,
RemoteWalkContext context)
{
bool success = true;
// Stores results of analyzing the graph including conflicts, cycles, and downgrades
AnalyzeResult<RemoteResolveResult> analyzeResult = new();
// Stores the list of items in as a flat list
HashSet<GraphItem<RemoteResolveResult>> flattenedGraphItems = new();
// Stores the list of graph nodes which point to their outer and inner nodes which represent the graph as a tree
List<GraphNode<RemoteResolveResult>> graphNodes = new();
// Stores the list of nodes by their LibraryRangeIndex for faster lookup
Dictionary<LibraryRangeIndex, GraphNode<RemoteResolveResult>> nodesById = new();
// Keeps track of visited items to detect when we come across a dependency that was already visited. Any time a dependency is seen again, we need to determine if there was a downgrade or conflict.
HashSet<LibraryDependencyIndex> visitedItems = new();
// Stores the items to process, starting with the project itself and its children
Queue<(LibraryDependencyIndex, LibraryRangeIndex, GraphNode<RemoteResolveResult>)> itemsToFlatten = new();
Dictionary<LibraryRangeIndex, GraphNode<RemoteResolveResult>> versionConflicts = new();
// Stores the list of downgrades
Dictionary<LibraryRangeIndex, (LibraryRangeIndex FromParentLibraryRangeIndex, LibraryDependency FromLibraryDependency, LibraryRangeIndex ToParentLibraryRangeIndex, LibraryDependencyIndex ToLibraryDependencyIndex, bool IsCentralTransitive)> downgrades = new();
// Get the resolved item for the project
ResolvedDependencyGraphItem projectResolvedDependencyGraphItem = resolvedDependencyGraphItems[LibraryDependencyIndex.Project];
// Create a node representing the root for the project
GraphNode<RemoteResolveResult> rootGraphNode = new GraphNode<RemoteResolveResult>(projectResolvedDependencyGraphItem.LibraryDependency.LibraryRange)
{
Item = projectResolvedDependencyGraphItem.Item
};
graphNodes.Add(rootGraphNode);
// Enqueue the project to be processed
itemsToFlatten.Enqueue((LibraryDependencyIndex.Project, projectResolvedDependencyGraphItem.LibraryRangeIndex, rootGraphNode));
nodesById.Add(projectResolvedDependencyGraphItem.LibraryRangeIndex, rootGraphNode);
while (itemsToFlatten.Count > 0)
{
(LibraryDependencyIndex currentLibraryDependencyIndex, LibraryRangeIndex currentLibraryRangeIndex, GraphNode<RemoteResolveResult> currentGraphNode) = itemsToFlatten.Dequeue();
// If there was no dependency in the resolved graph with the same name, it can be skipped and left out of the final graph
if (!resolvedDependencyGraphItems.TryGetValue(currentLibraryDependencyIndex, out ResolvedDependencyGraphItem? resolvedDependencyGraphItem))
{
continue;
}
flattenedGraphItems.Add(resolvedDependencyGraphItem.Item);
for (int i = 0; i < resolvedDependencyGraphItem.Item.Data.Dependencies.Count; i++)
{
LibraryDependency childLibraryDependency = resolvedDependencyGraphItem.Item.Data.Dependencies[i];
if (childLibraryDependency.LibraryRange.VersionRange == null)
{
continue;
}
if (StringComparer.OrdinalIgnoreCase.Equals(childLibraryDependency.Name, resolvedDependencyGraphItem.Item.Key.Name) || StringComparer.OrdinalIgnoreCase.Equals(childLibraryDependency.Name, rootGraphNode.Key.Name))
{
// A cycle exists since the current child dependency has the same name as its parent or as the root node
GraphNode<RemoteResolveResult> nodeWithCycle = new(childLibraryDependency.LibraryRange)
{
OuterNode = currentGraphNode,
Disposition = Disposition.Cycle
};
analyzeResult.Cycles.Add(nodeWithCycle);
continue;
}
LibraryDependencyIndex childLibraryDependencyIndex = resolvedDependencyGraphItem.GetDependencyIndexForDependencyAt(i);
if (!resolvedDependencyGraphItems.TryGetValue(childLibraryDependencyIndex, out ResolvedDependencyGraphItem? childResolvedDependencyGraphItem))
{
// If there was no dependency in the resolved graph with the same name as this child dependency, it can be skipped and left out of the final graph
continue;
}
LibraryRangeIndex childResolvedLibraryRangeIndex = childResolvedDependencyGraphItem.LibraryRangeIndex;
LibraryDependency childResolvedLibraryDependency = childResolvedDependencyGraphItem.LibraryDependency;
// Determine if this dependency has already been visited
if (!visitedItems.Add(childLibraryDependencyIndex))
{
LibraryRangeIndex currentRangeIndex = resolvedDependencyGraphItem.GetRangeIndexForDependencyAt(i);
if (resolvedDependencyGraphItem.Path.Contains(currentRangeIndex))
{
// If the dependency exists in the its own path, then a cycle exists
analyzeResult.Cycles.Add(
new GraphNode<RemoteResolveResult>(childLibraryDependency.LibraryRange)
{
OuterNode = currentGraphNode,
Disposition = Disposition.Cycle
});
continue;
}
// Verify downgrades only if the resolved dependency has a lower version than what was defined
if (!RemoteDependencyWalker.IsGreaterThanOrEqualTo(childResolvedLibraryDependency.LibraryRange.VersionRange, childLibraryDependency.LibraryRange.VersionRange))
{
// It is not a downgrade if: the dependency is transitive and is suppressed its parent or any of those parents' parent because the suppressions is an aggregate of everything suppressed above.
// For example, A -> B (PrivateAssets=All) -> C
// When processing C, it is not suppressed but its parent is, which is tracked in ResolvedDependencyGraphItem.Suppressions
if ((childLibraryDependencyIndex != LibraryDependencyIndex.Project && childLibraryDependency.SuppressParent == LibraryIncludeFlags.All)
|| resolvedDependencyGraphItem.Suppressions.Count > 0 && resolvedDependencyGraphItem.Suppressions[0].Contains(childLibraryDependencyIndex))
{
continue;
}
// Get the resolved version in case a floating version like 1.* was specified
NuGetVersion? resolvedVersion = childResolvedDependencyGraphItem.Item.Data.Match?.Library?.Version;
if (resolvedVersion != null && childLibraryDependency.LibraryRange.VersionRange.Satisfies(resolvedVersion))
{
// Ignore the lower version if the resolved version satisfies the range of the dependency. This can happen when a floating version like 1.* was specified
// and the resolved version is 1.2.3, which satisfies the range of 1.*
continue;
}
// This lower version could be a downgrade if it hasn't already been seen
if (!downgrades.ContainsKey(childResolvedLibraryRangeIndex))
{
// Determine if any parents have actually eclipsed this version
if (childResolvedDependencyGraphItem.ParentPathsThatHaveBeenEclipsed != null)
{
bool hasBeenEclipsedByParent = false;
foreach (LibraryRangeIndex parent in childResolvedDependencyGraphItem.ParentPathsThatHaveBeenEclipsed)
{
if (resolvedDependencyGraphItem.Path.Contains(parent))
{
hasBeenEclipsedByParent = true;
break;
}
}
if (hasBeenEclipsedByParent)
{
continue;
}
}
// Look through all of the parent nodes to see if any are a downgrade
bool foundParentDowngrade = false;
if (childResolvedDependencyGraphItem.Parents != null)
{
foreach (LibraryRangeIndex parentLibraryRangeIndex in childResolvedDependencyGraphItem.Parents)
{
if (resolvedDependencyGraphItem.Path.Contains(parentLibraryRangeIndex) && !resolvedDependencyGraphItem.IsRootPackageReference)
{
downgrades.Add(
childResolvedLibraryRangeIndex,
(
FromParentLibraryRangeIndex: resolvedDependencyGraphItem.LibraryRangeIndex,
FromLibraryDependency: childLibraryDependency,
ToParentLibraryRangeIndex: parentLibraryRangeIndex,
ToLibraryDependencyIndex: childLibraryDependencyIndex,
IsCentralTransitive: isCentralPackageTransitivePinningEnabled ? childResolvedDependencyGraphItem.IsCentrallyPinnedTransitivePackage : false
));
foundParentDowngrade = true;
break;
}
}
}
// It is a downgrade if central transitive pinning is not being used or if the child is not a direct package reference
if (!foundParentDowngrade && (!isCentralPackageTransitivePinningEnabled || !childResolvedDependencyGraphItem.IsRootPackageReference))
{
downgrades.Add(
childResolvedLibraryRangeIndex,
(
FromParentLibraryRangeIndex: resolvedDependencyGraphItem.LibraryRangeIndex,
FromLibraryDependency: childLibraryDependency,
ToParentLibraryRangeIndex: childResolvedDependencyGraphItem.Path[childResolvedDependencyGraphItem.Path.Length - 1],
ToLibraryDependencyIndex: childLibraryDependencyIndex,
IsCentralTransitive: isCentralPackageTransitivePinningEnabled ? childResolvedDependencyGraphItem.IsCentrallyPinnedTransitivePackage : false
));
}
}
// Ignore this child dependency since it was a downgrade
continue;
}
// If it wasn't a downgrade, then it was a version conflict like A -> B [1.0.0] but B 1.0.0 was not in the resolved graph
if (versionConflicts.ContainsKey(childResolvedLibraryRangeIndex) && !nodesById.ContainsKey(currentRangeIndex))
{
GraphNode<RemoteResolveResult> nodeWithConflict = new(childResolvedLibraryDependency.LibraryRange)
{
Item = childResolvedDependencyGraphItem.Item,
Disposition = Disposition.Acceptable,
OuterNode = currentGraphNode,
};
currentGraphNode.InnerNodes.Add(nodeWithConflict);
nodesById.Add(currentRangeIndex, nodeWithConflict);
continue;
}
// Ignore this child dependency since it was not a cycle, downgrade, or version conflict but was already visited
continue;
}
// Create a GraphNode for the item
GraphNode<RemoteResolveResult> newGraphNode = new(childResolvedLibraryDependency.LibraryRange)
{
Item = childResolvedDependencyGraphItem.Item
};
if (childResolvedDependencyGraphItem.IsCentrallyPinnedTransitivePackage && !childResolvedDependencyGraphItem.IsRootPackageReference)
{
// If this child is transitively pinned, the GraphNode needs to have certain properties set
newGraphNode.Disposition = Disposition.Accepted;
newGraphNode.Item.IsCentralTransitive = true;
// Treat the transitively pinned dependency as a child of the root node
newGraphNode.OuterNode = rootGraphNode;
rootGraphNode.InnerNodes.Add(newGraphNode);
}
else
{
// Set properties for the node to represent a parent/child relationship
newGraphNode.OuterNode = currentGraphNode;
currentGraphNode.InnerNodes.Add(newGraphNode);
}
if (!childResolvedDependencyGraphItem.IsRootPackageReference && isCentralPackageTransitivePinningEnabled && childLibraryDependency.SuppressParent != LibraryIncludeFlags.All && !downgrades.ContainsKey(childResolvedLibraryRangeIndex) && !RemoteDependencyWalker.IsGreaterThanOrEqualTo(childResolvedDependencyGraphItem.LibraryDependency.LibraryRange.VersionRange, childLibraryDependency.LibraryRange.VersionRange))
{
// This is a downgrade if:
// 1. This is not a direct dependency
// 2. This is a central transitive pinned dependency
// 3. This is a transitive dependency which is not PrivateAssets=All
// 4. This has not already been detected
// 5. The version is lower
downgrades.Add(
childResolvedDependencyGraphItem.LibraryRangeIndex,
(
FromParentLibraryRangeIndex: currentLibraryRangeIndex,
FromLibraryDependency: childLibraryDependency,
ToParentLibraryRangeIndex: LibraryRangeIndex.Project,
ToLibraryDependencyIndex: childLibraryDependencyIndex,
IsCentralTransitive: true
));
}
// This is a version conflict if:
// 1. The node is not a project and isn't unresolved
// 2. The conflict has not already been detected
// 3. The dependency is transitive and doesn't have PrivateAssets=All
// 4. The dependency has a version specified
// 5. The version range is not satisfied by the resolved version
// 6. A corresponding downgrade was not detected
if (newGraphNode.Item.Key.Type != LibraryType.Project
&& newGraphNode.Item.Key.Type != LibraryType.ExternalProject
&& newGraphNode.Item.Key.Type != LibraryType.Unresolved
&& !versionConflicts.ContainsKey(childResolvedLibraryRangeIndex)
&& childLibraryDependency.SuppressParent != LibraryIncludeFlags.All
&& childLibraryDependency.LibraryRange.VersionRange != null
&& !childLibraryDependency.LibraryRange.VersionRange!.Satisfies(newGraphNode.Item.Key.Version)
&& !downgrades.ContainsKey(childResolvedLibraryRangeIndex))
{
// Remove the existing node so it can be replaced with a node representing the conflict
currentGraphNode.InnerNodes.Remove(newGraphNode);
GraphNode<RemoteResolveResult> conflictingNode = new(childLibraryDependency.LibraryRange)
{
Disposition = Disposition.Acceptable,
Item = new GraphItem<RemoteResolveResult>(
new LibraryIdentity(
childLibraryDependency.Name,
childLibraryDependency.LibraryRange.VersionRange.MinVersion!,
LibraryType.Package)),
OuterNode = currentGraphNode,
};
// Add the conflict node to the parent
currentGraphNode.InnerNodes.Add(conflictingNode);
// Track the version conflict for later
versionConflicts.Add(childResolvedLibraryRangeIndex, conflictingNode);
// Process the next child
continue;
}
// Add the node to the lookup for later
nodesById.Add(childResolvedLibraryRangeIndex, newGraphNode);
// Enqueue the child for processing
itemsToFlatten.Enqueue((childLibraryDependencyIndex, childResolvedLibraryRangeIndex, newGraphNode));
if (newGraphNode.Item.Key.Type == LibraryType.Unresolved)
{
// Keep track of unresolved packages and fail the restore
unresolvedPackages.Add(childResolvedLibraryDependency.LibraryRange);
success = false;
}
else
{
// Keep track of the resolved packages
resolvedPackages.Add(new ResolvedDependencyKey(
parent: newGraphNode.OuterNode.Item.Key,
range: newGraphNode.Key.VersionRange,
child: newGraphNode.Item.Key));
}
}
} // End of walking all declared dependencies for cycles, downgrades, and conflicts
// Add applicable version conflicts to the analyze results
if (versionConflicts.Count > 0)
{
foreach (KeyValuePair<LibraryRangeIndex, GraphNode<RemoteResolveResult>> versionConflict in versionConflicts)
{
if (nodesById.TryGetValue(versionConflict.Key, out GraphNode<RemoteResolveResult>? selected))
{
analyzeResult.VersionConflicts.Add(
new VersionConflictResult<RemoteResolveResult>
{
Conflicting = versionConflict.Value,
Selected = selected,
});
}
}
}
// Add applicable downgrades to the analyze results
if (downgrades.Count > 0)
{
foreach ((LibraryRangeIndex FromParentLibraryRangeIndex, LibraryDependency FromLibraryDependency, LibraryRangeIndex ToParentLibraryRangeIndex, LibraryDependencyIndex ToLibraryDependencyIndex, bool IsCentralTransitive) downgrade in downgrades.Values)
{
// Ignore the downgrade if a node was not created for its from or to, or if it never ended up in the resolved graph. Sometimes a downgrade is detected but later during graph
// resolution it is resolved so this verifies if the downgrade ended up in the final graph
if (!nodesById.TryGetValue(downgrade.FromParentLibraryRangeIndex, out GraphNode<RemoteResolveResult>? fromParentNode)
|| !nodesById.TryGetValue(downgrade.ToParentLibraryRangeIndex, out GraphNode<RemoteResolveResult>? toParentNode)
|| !resolvedDependencyGraphItems.TryGetValue(downgrade.ToLibraryDependencyIndex, out ResolvedDependencyGraphItem? toResolvedDependencyGraphItem))
{
continue;
}
// Add the downgrade
analyzeResult.Downgrades.Add(new DowngradeResult<RemoteResolveResult>
{
DowngradedFrom = new GraphNode<RemoteResolveResult>(downgrade.FromLibraryDependency.LibraryRange)
{
Item = new GraphItem<RemoteResolveResult>(
new LibraryIdentity(
downgrade.FromLibraryDependency.Name,
downgrade.FromLibraryDependency.LibraryRange.VersionRange?.MinVersion!,
LibraryType.Package)),
OuterNode = fromParentNode
},
DowngradedTo = new GraphNode<RemoteResolveResult>(toResolvedDependencyGraphItem.LibraryDependency.LibraryRange)
{
Item = new GraphItem<RemoteResolveResult>(toResolvedDependencyGraphItem.Item.Key)
{
IsCentralTransitive = downgrade.IsCentralTransitive
},
OuterNode = downgrade.IsCentralTransitive ? rootGraphNode : toParentNode,
}
});
}
}
// If central transitive pinning is enabled, we need to add all of its parent nodes. This has to happen at the end after all of the nodes in graph have been created
if (isCentralPackageTransitivePinningEnabled)
{
foreach (KeyValuePair<LibraryDependencyIndex, ResolvedDependencyGraphItem> resolvedDependencyGraphItemEntry in resolvedDependencyGraphItems)
{
ResolvedDependencyGraphItem resolvedDependencyGraphItem = resolvedDependencyGraphItemEntry.Value;
// Skip this item if:
// 1. It is not pinned
// 2. It is a direct package reference
// 3. It has not parents
// 4. A node was not created for it
if (!resolvedDependencyGraphItem.IsCentrallyPinnedTransitivePackage
|| resolvedDependencyGraphItem.IsRootPackageReference
|| resolvedDependencyGraphItem.Parents == null
|| resolvedDependencyGraphItem.Parents.Count == 0
|| !nodesById.TryGetValue(resolvedDependencyGraphItem.LibraryRangeIndex, out GraphNode<RemoteResolveResult>? currentNode))
{
continue;
}
// Get the corresponding node in the graph for each parent and add it the list of parent nodes
foreach (LibraryRangeIndex parentLibraryRangeIndex in resolvedDependencyGraphItem.Parents.NoAllocEnumerate())
{
if (!nodesById.TryGetValue(parentLibraryRangeIndex, out GraphNode<RemoteResolveResult>? parentNode))
{
// Skip nodes that weren't created
continue;
}
currentNode.ParentNodes.Add(parentNode);
}
}
}
// Get the list of packages to install
HashSet<RemoteMatch> packagesToInstall = await context.GetUnresolvedRemoteMatchesAsync();
// Create a RestoreTargetGraph with all of the information
RestoreTargetGraph restoreTargetGraph = new(
Array.Empty<ResolverConflict>(),
frameworkRuntimeDefinition.TargetAlias,
frameworkRuntimeDefinition.Framework,
string.IsNullOrWhiteSpace(frameworkRuntimeDefinition.RuntimeIdentifier) ? null : frameworkRuntimeDefinition.RuntimeIdentifier,
runtimeGraph,
graphNodes,
install: packagesToInstall,
flattened: flattenedGraphItems,
unresolved: unresolvedPackages,
analyzeResult,
resolvedDependencies: resolvedPackages);
return (success, restoreTargetGraph);
}