Modules/businessdev.ALbuild.Feeds/Private/Resolve-BcDependencyGraph.ps1
|
function Resolve-BcDependencyGraph { <# .SYNOPSIS Solves an AL dependency graph against feeds and a pinned baseline (backtracking). .DESCRIPTION Internal solver. Given root dependencies, a pinned set (Microsoft first-party apps and anything already installed in the target build), the target platform/application versions and a set of feed providers, it finds a mutually-compatible assignment of versions - not a greedy "latest >= min", but a real constraint solve with backtracking. It is pure with respect to its inputs: all feed access happens through the providers' FindCandidates method, so the solver is fully unit-testable with in-memory fixture providers. Each provider must expose: FindCandidates([string]$appId, [string]$name, [string]$publisher, [string]$minVersion) returning candidate records (BcPackageManifest, or any record exposing Id/Version/ Dependencies/Platform/Application/Kind/PackageId/ProviderName/Provider). Candidates are normalised into [BcPackageManifest] at the boundary, so fixtures may return plain hashtables. .OUTPUTS Hashtable: @{ Resolved = <ordered BcPackageManifest[]>; Assignments = <id->BcPackageManifest> }. Throws a descriptive error when the graph cannot be satisfied. #> [Diagnostics.CodeAnalysis.SuppressMessageAttribute('PSReviewUnusedParameter', '', Justification = 'Parameters are consumed inside nested script blocks (closures) which the analyzer does not trace.')] [CmdletBinding()] [OutputType([hashtable])] param( [Parameter(Mandatory)] [AllowEmptyCollection()] [object[]] $RootDependencies, [Parameter(Mandatory)] [hashtable] $Pinned, [Parameter(Mandatory)] [object[]] $Providers, [string] $TargetPlatform = '', [string] $TargetApplication = '', [ValidateSet('LowestCompatible', 'Latest')] [string] $Select = 'Latest', [int] $MaxDepth = 200 ) # Tell each provider what build we are resolving for, so an indirect metapackage can pick the # runtime sub-package build closest to the target. Best-effort: fixtures need not carry these. foreach ($provider in $Providers) { try { $provider.TargetPlatform = $TargetPlatform $provider.TargetApplication = $TargetApplication } catch { # Best-effort: in-memory test fixtures need not expose these properties. Write-Verbose "Provider '$($provider.Name)' does not accept a target build: $($_.Exception.Message)" } } $compatible = { param($candidate) if ($TargetApplication -and $candidate.Application) { if ((Compare-BcVersion $candidate.Application $TargetApplication) -gt 0) { return $false } } if ($TargetPlatform -and $candidate.Platform) { if ((Compare-BcVersion $candidate.Platform $TargetPlatform) -gt 0) { return $false } } return $true } # Compute the highest minimum required for an id across the active constraint set. $requiredMinFor = { param($constraints, $id) $min = '0.0.0.0' foreach ($c in $constraints) { if ($c.Id -eq $id -and (Compare-BcVersion $c.MinVersion $min) -gt 0) { $min = $c.MinVersion } } return $min } $firstUnsatisfied = { param($constraints, $assignments) foreach ($c in $constraints) { $assigned = $assignments[$c.Id] if (-not $assigned -or (Compare-BcVersion $assigned.Version $c.MinVersion) -lt 0) { return $c } } return $null } $solve = { param($constraints, $assignments, $depth) if ($depth -gt $MaxDepth) { throw "Dependency resolution exceeded maximum depth ($MaxDepth); the graph may contain a cycle." } $next = & $firstUnsatisfied $constraints $assignments if (-not $next) { return $assignments } # Pinned ids cannot be upgraded; if they are too low it is an unsatisfiable conflict here. if ($Pinned.ContainsKey($next.Id)) { $conflicts.Add("App '$($next.Name)' ($($next.Id)) requires version >= $($next.MinVersion), but the target build provides $($Pinned[$next.Id]).") return $null } # Microsoft first-party apps (and the Platform/Application) ship with the Business Central # build: they are provided by the target, never downloaded from a third-party feed. Pin them # to the target on first encounter; a target older than the requirement is a hard conflict. if ($next.IsMicrosoft()) { $targetVersion = if ($TargetApplication) { $TargetApplication } else { $next.MinVersion } if ((Compare-BcVersion $targetVersion $next.MinVersion) -lt 0) { $conflicts.Add("Microsoft app '$($next.Name)' ($($next.Id)) requires version >= $($next.MinVersion), but the target build provides $targetVersion.") return $null } $label = if ($next.Name) { $next.Name } else { $next.Id } Write-ALbuildLog -Level Verbose " $label is provided by the Business Central build (pinned to $targetVersion)." $newAssignments = @{} foreach ($k in $assignments.Keys) { $newAssignments[$k] = $assignments[$k] } $newAssignments[$next.Id] = [BcPackageManifest]::NewPinned($next.Id, $targetVersion) return & $solve $constraints $newAssignments ($depth + 1) } $min = & $requiredMinFor $constraints $next.Id # Stream one progress line per dependency as it is resolved, so large graphs do not look # hung while feeds are queried (each lookup is one or more network round-trips). if (-not $announced.ContainsKey($next.Id)) { $announced[$next.Id] = $true $label = if ($next.Name) { $next.Name } else { $next.Id } Write-ALbuildLog -Level Information " Resolving $label (>= $min)..." } # The exact package id(s) this dependency was declared with (e.g. read from a parent's nuspec), # so providers can locate it verbatim rather than reconstructing it from publisher/name. $hints = @($constraints | Where-Object { $_.Id -eq $next.Id -and $_.PackageId } | ForEach-Object { $_.PackageId } | Select-Object -Unique) $candidates = @() foreach ($provider in $Providers) { $found = $provider.FindCandidates($next.Id, $next.Name, $next.Publisher, $min, $hints) foreach ($cand in $found) { $candidates += [BcPackageManifest]::FromObject($cand) } } $candidates = @($candidates | Where-Object { (Compare-BcVersion $_.Version $min) -ge 0 -and (& $compatible $_) }) if ($candidates.Count -eq 0) { $conflicts.Add("No compatible package found for '$($next.Name)' ($($next.Id)) version >= $min (target application '$TargetApplication', platform '$TargetPlatform').") return $null } # De-duplicate by version, preferring an installable package (apps/runtime) over a symbol-only # one for the same version: symbols compile but cannot be published/installed into a container, # so a real app must win when both feeds carry it. $installable = { param($c) @('apps', 'runtime') -contains "$($c.Kind)" } $byVersion = [ordered]@{} foreach ($cand in $candidates) { $existing = $byVersion[$cand.Version] if ((-not $existing) -or ((& $installable $cand) -and -not (& $installable $existing))) { $byVersion[$cand.Version] = $cand } } # Order so an installable package always beats a symbol-only one, then by selection strategy # (newest first for Latest). This keeps the build on real apps from the apps/runtime feeds and # only falls back to a symbol-only package (e.g. Microsoft first-party) when no real app exists. $descending = ($Select -eq 'Latest') $sortKeys = @( @{ Expression = { if (& $installable $_) { 0 } else { 1 } } } @{ Expression = { ConvertTo-BcVersion $_.Version }; Descending = $descending } ) $ordered = @($byVersion.Values | Sort-Object -Property $sortKeys) foreach ($cand in $ordered) { $newAssignments = @{} foreach ($k in $assignments.Keys) { $newAssignments[$k] = $assignments[$k] } $newAssignments[$next.Id] = $cand $newConstraints = @($constraints) foreach ($dep in @($cand.Dependencies)) { $newConstraints += [BcPackageDependency]::FromObject($dep) } $result = & $solve $newConstraints $newAssignments ($depth + 1) if ($result) { return $result } } return $null } # Collects human-readable reasons when a branch fails (local to this invocation). $conflicts = [System.Collections.Generic.List[string]]::new() # Tracks which dependencies have already been announced, so progress is logged once per id. $announced = @{} # Seed constraints with the roots; assignments start with the pinned baseline. $constraints = @() foreach ($r in $RootDependencies) { $constraints += [BcPackageDependency]::FromObject($r) } $assignments = @{} foreach ($k in $Pinned.Keys) { $assignments[$k] = [BcPackageManifest]::NewPinned($k, "$($Pinned[$k])") } $solution = & $solve $constraints $assignments 0 if (-not $solution) { $detail = if ($conflicts.Count -gt 0) { [Environment]::NewLine + (($conflicts | Select-Object -Unique) -join [Environment]::NewLine) } else { '' } throw "Unable to resolve dependencies.$detail" } # Project the non-pinned assignments and order them topologically (dependencies first). $resolved = @($solution.Values | Where-Object { -not $_.Pinned }) $ordered = [System.Collections.Generic.List[BcPackageManifest]]::new() $visited = @{} $visit = { param($node) if ($visited.ContainsKey($node.Id)) { return } $visited[$node.Id] = $true foreach ($dep in @($node.Dependencies)) { $depNode = $resolved | Where-Object { $_.Id -eq $dep.Id } | Select-Object -First 1 if ($depNode) { & $visit $depNode } } $ordered.Add($node) } foreach ($node in $resolved) { & $visit $node } return @{ Resolved = $ordered.ToArray(); Assignments = $solution } } |