387 lines
11 KiB
Nim
387 lines
11 KiB
Nim
## Integration Tests for Dependency Resolver
|
|
##
|
|
## These tests verify the complete end-to-end resolution pipeline:
|
|
## - Graph construction
|
|
## - CNF translation
|
|
## - CDCL solving
|
|
## - Solution conversion
|
|
## - Installation order computation
|
|
##
|
|
## Requirements: 5.1, 5.4, 5.5
|
|
|
|
import std/[unittest, tables, sets, options, strutils, sequtils, times]
|
|
import ../src/nip/resolver/[
|
|
resolver_integration,
|
|
dependency_graph,
|
|
variant_types,
|
|
cnf_translator,
|
|
cdcl_solver
|
|
]
|
|
import ../src/nip/manifest_parser
|
|
|
|
suite "Resolver Integration Tests":
|
|
|
|
# Helper to create a simple variant profile
|
|
proc makeVariant(flags: seq[string] = @[]): VariantProfile =
|
|
var domains = initTable[string, VariantDomain]()
|
|
if flags.len > 0:
|
|
var flagSet = initHashSet[string]()
|
|
for flag in flags:
|
|
flagSet.incl(flag)
|
|
domains["features"] = VariantDomain(
|
|
name: "features",
|
|
exclusivity: NonExclusive,
|
|
flags: flagSet
|
|
)
|
|
|
|
result = VariantProfile(
|
|
domains: domains,
|
|
hash: "test-hash-" & flags.join("-")
|
|
)
|
|
|
|
# Helper to create a package spec
|
|
proc makeSpec(name: string, flags: seq[string] = @[]): PackageSpec =
|
|
PackageSpec(
|
|
packageName: name,
|
|
versionConstraint: VersionConstraint(
|
|
operator: OpAny,
|
|
version: SemanticVersion(major: 1, minor: 0, patch: 0)
|
|
),
|
|
variantProfile: makeVariant(flags)
|
|
)
|
|
|
|
test "End-to-end resolution - simple chain":
|
|
## Test: A -> B -> C
|
|
## Expected: Resolves successfully with installation order [C, B, A]
|
|
##
|
|
## Requirements: 5.1, 5.4, 5.5
|
|
|
|
# Build graph: A -> B -> C
|
|
var graph = newDependencyGraph()
|
|
|
|
let variantA = makeVariant()
|
|
let variantB = makeVariant()
|
|
let variantC = makeVariant()
|
|
|
|
let termIdA = createTermId("A", variantA.hash)
|
|
let termIdB = createTermId("B", variantB.hash)
|
|
let termIdC = createTermId("C", variantC.hash)
|
|
|
|
graph.addTerm(PackageTerm(
|
|
id: termIdA,
|
|
packageName: "A",
|
|
variantProfile: variantA,
|
|
optional: false,
|
|
source: "test"
|
|
))
|
|
|
|
graph.addTerm(PackageTerm(
|
|
id: termIdB,
|
|
packageName: "B",
|
|
variantProfile: variantB,
|
|
optional: false,
|
|
source: "test"
|
|
))
|
|
|
|
graph.addTerm(PackageTerm(
|
|
id: termIdC,
|
|
packageName: "C",
|
|
variantProfile: variantC,
|
|
optional: false,
|
|
source: "test"
|
|
))
|
|
|
|
graph.addEdge(DependencyEdge(
|
|
fromTerm: termIdA,
|
|
toTerm: termIdB,
|
|
dependencyType: Required
|
|
))
|
|
|
|
graph.addEdge(DependencyEdge(
|
|
fromTerm: termIdB,
|
|
toTerm: termIdC,
|
|
dependencyType: Required
|
|
))
|
|
|
|
# Create resolution request
|
|
let request = ResolutionRequest(
|
|
rootPackages: @[makeSpec("A")],
|
|
constraints: @[]
|
|
)
|
|
|
|
# Resolve
|
|
let result = resolve(request, graph)
|
|
|
|
# Verify success
|
|
check result.success
|
|
check result.packages.len == 3
|
|
|
|
# Verify installation order (dependencies first)
|
|
check result.installOrder.len == 3
|
|
check result.installOrder[0] == "C" # No dependencies
|
|
check result.installOrder[1] == "B" # Depends on C
|
|
check result.installOrder[2] == "A" # Depends on B
|
|
|
|
test "End-to-end resolution - diamond dependency":
|
|
## Test: A -> B, A -> C, B -> D, C -> D
|
|
## Expected: Resolves successfully with D first, then B and C, then A
|
|
##
|
|
## Requirements: 5.1, 5.4, 5.5
|
|
|
|
var graph = newDependencyGraph()
|
|
|
|
let variantA = makeVariant()
|
|
let variantB = makeVariant()
|
|
let variantC = makeVariant()
|
|
let variantD = makeVariant()
|
|
|
|
let termIdA = createTermId("A", variantA.hash)
|
|
let termIdB = createTermId("B", variantB.hash)
|
|
let termIdC = createTermId("C", variantC.hash)
|
|
let termIdD = createTermId("D", variantD.hash)
|
|
|
|
# Add terms
|
|
for (id, name, variant) in [(termIdA, "A", variantA), (termIdB, "B", variantB),
|
|
(termIdC, "C", variantC), (termIdD, "D", variantD)]:
|
|
graph.addTerm(PackageTerm(
|
|
id: id,
|
|
packageName: name,
|
|
variantProfile: variant,
|
|
optional: false,
|
|
source: "test"
|
|
))
|
|
|
|
# Add edges
|
|
graph.addEdge(DependencyEdge(fromTerm: termIdA, toTerm: termIdB, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termIdA, toTerm: termIdC, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termIdB, toTerm: termIdD, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termIdC, toTerm: termIdD, dependencyType: Required))
|
|
|
|
let request = ResolutionRequest(
|
|
rootPackages: @[makeSpec("A")],
|
|
constraints: @[]
|
|
)
|
|
|
|
let result = resolve(request, graph)
|
|
|
|
check result.success
|
|
check result.packages.len == 4
|
|
|
|
# D must come before B and C
|
|
let dIndex = result.installOrder.find("D")
|
|
let bIndex = result.installOrder.find("B")
|
|
let cIndex = result.installOrder.find("C")
|
|
let aIndex = result.installOrder.find("A")
|
|
|
|
check dIndex < bIndex
|
|
check dIndex < cIndex
|
|
check bIndex < aIndex
|
|
check cIndex < aIndex
|
|
|
|
test "Conflict reporting - circular dependency":
|
|
## Test: A -> B -> C -> A (cycle)
|
|
## Expected: Reports circular dependency conflict
|
|
##
|
|
## Requirements: 5.1, 5.5
|
|
|
|
var graph = newDependencyGraph()
|
|
|
|
let variantA = makeVariant()
|
|
let variantB = makeVariant()
|
|
let variantC = makeVariant()
|
|
|
|
let termIdA = createTermId("A", variantA.hash)
|
|
let termIdB = createTermId("B", variantB.hash)
|
|
let termIdC = createTermId("C", variantC.hash)
|
|
|
|
# Add terms
|
|
for (id, name, variant) in [(termIdA, "A", variantA), (termIdB, "B", variantB),
|
|
(termIdC, "C", variantC)]:
|
|
graph.addTerm(PackageTerm(
|
|
id: id,
|
|
packageName: name,
|
|
variantProfile: variant,
|
|
optional: false,
|
|
source: "test"
|
|
))
|
|
|
|
# Create cycle: A -> B -> C -> A
|
|
graph.addEdge(DependencyEdge(fromTerm: termIdA, toTerm: termIdB, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termIdB, toTerm: termIdC, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termIdC, toTerm: termIdA, dependencyType: Required))
|
|
|
|
let request = ResolutionRequest(
|
|
rootPackages: @[makeSpec("A")],
|
|
constraints: @[]
|
|
)
|
|
|
|
let result = resolve(request, graph)
|
|
|
|
check not result.success
|
|
check result.conflict.conflictType == CircularDependency
|
|
check result.conflict.packages.len > 0
|
|
|
|
test "Solution correctness - all dependencies satisfied":
|
|
## Test: Verify that the solution satisfies all dependencies
|
|
## A -> B, A -> C, B -> D
|
|
##
|
|
## Requirements: 5.1, 5.4
|
|
|
|
var graph = newDependencyGraph()
|
|
|
|
let variantA = makeVariant()
|
|
let variantB = makeVariant()
|
|
let variantC = makeVariant()
|
|
let variantD = makeVariant()
|
|
|
|
let termIdA = createTermId("A", variantA.hash)
|
|
let termIdB = createTermId("B", variantB.hash)
|
|
let termIdC = createTermId("C", variantC.hash)
|
|
let termIdD = createTermId("D", variantD.hash)
|
|
|
|
# Add terms
|
|
for (id, name, variant) in [(termIdA, "A", variantA), (termIdB, "B", variantB),
|
|
(termIdC, "C", variantC), (termIdD, "D", variantD)]:
|
|
graph.addTerm(PackageTerm(
|
|
id: id,
|
|
packageName: name,
|
|
variantProfile: variant,
|
|
optional: false,
|
|
source: "test"
|
|
))
|
|
|
|
# Add edges
|
|
graph.addEdge(DependencyEdge(fromTerm: termIdA, toTerm: termIdB, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termIdA, toTerm: termIdC, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termIdB, toTerm: termIdD, dependencyType: Required))
|
|
|
|
let request = ResolutionRequest(
|
|
rootPackages: @[makeSpec("A")],
|
|
constraints: @[]
|
|
)
|
|
|
|
let result = resolve(request, graph)
|
|
|
|
check result.success
|
|
|
|
# Verify all packages are present
|
|
let packageNames = result.packages.mapIt(it.packageName).toHashSet
|
|
check "A" in packageNames
|
|
check "B" in packageNames
|
|
check "C" in packageNames
|
|
check "D" in packageNames
|
|
|
|
# Verify installation order is valid (dependencies before dependents)
|
|
var orderMap = initTable[string, int]()
|
|
for i, name in result.installOrder:
|
|
orderMap[name] = i
|
|
|
|
# A depends on B and C
|
|
check orderMap["B"] < orderMap["A"]
|
|
check orderMap["C"] < orderMap["A"]
|
|
|
|
# B depends on D
|
|
check orderMap["D"] < orderMap["B"]
|
|
|
|
test "Performance - large graph (50 packages)":
|
|
## Test: Resolution should complete in reasonable time for large graphs
|
|
## Create a chain of 50 packages
|
|
##
|
|
## Requirements: 5.1, 5.4
|
|
|
|
var graph = newDependencyGraph()
|
|
|
|
# Create chain: P0 -> P1 -> P2 -> ... -> P49
|
|
var prevTermId: Option[PackageTermId] = none(PackageTermId)
|
|
|
|
for i in 0..<50:
|
|
let variant = makeVariant()
|
|
let termId = createTermId("P" & $i, variant.hash)
|
|
|
|
graph.addTerm(PackageTerm(
|
|
id: termId,
|
|
packageName: "P" & $i,
|
|
variantProfile: variant,
|
|
optional: false,
|
|
source: "test"
|
|
))
|
|
|
|
if prevTermId.isSome:
|
|
graph.addEdge(DependencyEdge(
|
|
fromTerm: prevTermId.get(),
|
|
toTerm: termId,
|
|
dependencyType: Required
|
|
))
|
|
|
|
prevTermId = some(termId)
|
|
|
|
let request = ResolutionRequest(
|
|
rootPackages: @[makeSpec("P0")],
|
|
constraints: @[]
|
|
)
|
|
|
|
# Measure resolution time
|
|
let startTime = cpuTime()
|
|
let result = resolve(request, graph)
|
|
let endTime = cpuTime()
|
|
let elapsedMs = (endTime - startTime) * 1000.0
|
|
|
|
check result.success
|
|
check result.packages.len == 50
|
|
check result.installOrder.len == 50
|
|
|
|
# Should complete in under 1 second for 50 packages
|
|
check elapsedMs < 1000.0
|
|
|
|
echo "Resolution time for 50 packages: ", elapsedMs.formatFloat(ffDecimal, 2), " ms"
|
|
|
|
test "Empty graph resolution":
|
|
## Test: Resolving with an empty graph should fail
|
|
## The root package must be in the graph to be resolved
|
|
##
|
|
## Requirements: 5.1, 5.5
|
|
|
|
let graph = newDependencyGraph()
|
|
let request = ResolutionRequest(
|
|
rootPackages: @[makeSpec("A")],
|
|
constraints: @[]
|
|
)
|
|
|
|
let result = resolve(request, graph)
|
|
|
|
# Should fail because root package is not in graph
|
|
check not result.success
|
|
check result.conflict.conflictType == Unsatisfiable
|
|
check result.conflict.packages.len == 1
|
|
check result.conflict.packages[0] == "A"
|
|
|
|
test "Single package resolution":
|
|
## Test: Resolving a single package with no dependencies
|
|
##
|
|
## Requirements: 5.1, 5.4
|
|
|
|
var graph = newDependencyGraph()
|
|
|
|
let variant = makeVariant()
|
|
let termId = createTermId("A", variant.hash)
|
|
|
|
graph.addTerm(PackageTerm(
|
|
id: termId,
|
|
packageName: "A",
|
|
variantProfile: variant,
|
|
optional: false,
|
|
source: "test"
|
|
))
|
|
|
|
let request = ResolutionRequest(
|
|
rootPackages: @[makeSpec("A")],
|
|
constraints: @[]
|
|
)
|
|
|
|
let result = resolve(request, graph)
|
|
|
|
check result.success
|
|
check result.packages.len == 1
|
|
check result.packages[0].packageName == "A"
|
|
check result.installOrder == @["A"]
|