411 lines
14 KiB
Nim
411 lines
14 KiB
Nim
## Unit Tests for Graph Builder
|
|
##
|
|
## Tests for the dependency graph builder which constructs complete
|
|
## dependency graphs from package demands.
|
|
|
|
import std/[unittest, options, tables, sequtils]
|
|
import ../src/nip/resolver/graph_builder
|
|
import ../src/nip/resolver/dependency_graph
|
|
import ../src/nip/resolver/variant_types
|
|
|
|
suite "Graph Builder Tests":
|
|
|
|
test "Build simple chain (A → B → C)":
|
|
## Test building a simple dependency chain
|
|
|
|
# Create variant profiles
|
|
var profileA = newVariantProfile()
|
|
profileA.addFlag("optimization", "lto")
|
|
profileA.calculateHash()
|
|
|
|
var profileB = newVariantProfile()
|
|
profileB.addFlag("optimization", "lto")
|
|
profileB.calculateHash()
|
|
|
|
var profileC = newVariantProfile()
|
|
profileC.addFlag("optimization", "lto")
|
|
profileC.calculateHash()
|
|
|
|
# Create demands
|
|
let demandA = VariantDemand(
|
|
packageName: "packageA",
|
|
variantProfile: profileA,
|
|
optional: false
|
|
)
|
|
|
|
let demandB = VariantDemand(
|
|
packageName: "packageB",
|
|
variantProfile: profileB,
|
|
optional: false
|
|
)
|
|
|
|
let demandC = VariantDemand(
|
|
packageName: "packageC",
|
|
variantProfile: profileC,
|
|
optional: false
|
|
)
|
|
|
|
# Create dependency map: A -> B, B -> C, C -> []
|
|
let dependencyMap = {
|
|
"packageA": @[demandB],
|
|
"packageB": @[demandC],
|
|
"packageC": @[]
|
|
}.toTable()
|
|
|
|
# Build graph
|
|
let buildResult = buildSimpleGraph(@[demandA], dependencyMap)
|
|
check buildResult.conflicts.len == 0
|
|
check buildResult.warnings.len == 0
|
|
|
|
let graph = buildResult.graph
|
|
check graph.getStats().terms == 3
|
|
check graph.getStats().edges == 2
|
|
|
|
# Verify chain structure
|
|
let rootTerms = graph.getRootTerms()
|
|
check rootTerms.len == 1 # Only A should be root
|
|
|
|
let leafTerms = graph.getLeafTerms()
|
|
check leafTerms.len == 1 # Only C should be leaf
|
|
|
|
test "Build diamond (A → B,C → D)":
|
|
## Test building a diamond dependency structure
|
|
|
|
# Create variant profiles (all compatible)
|
|
var profile = newVariantProfile()
|
|
profile.addFlag("optimization", "lto")
|
|
profile.calculateHash()
|
|
|
|
# Create demands
|
|
let demandA = VariantDemand(packageName: "packageA", variantProfile: profile, optional: false)
|
|
let demandB = VariantDemand(packageName: "packageB", variantProfile: profile, optional: false)
|
|
let demandC = VariantDemand(packageName: "packageC", variantProfile: profile, optional: false)
|
|
let demandD = VariantDemand(packageName: "packageD", variantProfile: profile, optional: false)
|
|
|
|
# Create dependency map: A -> [B,C], B -> D, C -> D, D -> []
|
|
let dependencyMap = {
|
|
"packageA": @[demandB, demandC],
|
|
"packageB": @[demandD],
|
|
"packageC": @[demandD],
|
|
"packageD": @[]
|
|
}.toTable()
|
|
|
|
# Build graph
|
|
let buildResult = buildSimpleGraph(@[demandA], dependencyMap)
|
|
check buildResult.conflicts.len == 0
|
|
|
|
let graph = buildResult.graph
|
|
check graph.getStats().terms == 4
|
|
check graph.getStats().edges == 4 # A->B, A->C, B->D, C->D
|
|
|
|
# Verify diamond structure
|
|
let rootTerms = graph.getRootTerms()
|
|
check rootTerms.len == 1 # Only A should be root
|
|
|
|
let leafTerms = graph.getLeafTerms()
|
|
check leafTerms.len == 1 # Only D should be leaf
|
|
|
|
# D should have 2 incoming edges (from B and C)
|
|
let dTerms = graph.getTermsByPackage("packageD")
|
|
check dTerms.len == 1
|
|
let dIncoming = graph.getIncomingEdges(dTerms[0].id)
|
|
check dIncoming.len == 2
|
|
|
|
test "Build multiple roots":
|
|
## Test building graph with multiple root packages
|
|
|
|
var profile = newVariantProfile()
|
|
profile.addFlag("optimization", "lto")
|
|
profile.calculateHash()
|
|
|
|
# Create demands
|
|
let demandA = VariantDemand(packageName: "packageA", variantProfile: profile, optional: false)
|
|
let demandB = VariantDemand(packageName: "packageB", variantProfile: profile, optional: false)
|
|
let demandC = VariantDemand(packageName: "packageC", variantProfile: profile, optional: false)
|
|
|
|
# Create dependency map: A -> C, B -> C, C -> []
|
|
let dependencyMap = {
|
|
"packageA": @[demandC],
|
|
"packageB": @[demandC],
|
|
"packageC": @[]
|
|
}.toTable()
|
|
|
|
# Build graph with multiple roots
|
|
let buildResult = buildSimpleGraph(@[demandA, demandB], dependencyMap)
|
|
check buildResult.conflicts.len == 0
|
|
|
|
let graph = buildResult.graph
|
|
check graph.getStats().terms == 3
|
|
check graph.getStats().edges == 2 # A->C, B->C
|
|
|
|
# Should have 2 root terms (A and B)
|
|
let rootTerms = graph.getRootTerms()
|
|
check rootTerms.len == 2
|
|
|
|
# Should have 1 leaf term (C)
|
|
let leafTerms = graph.getLeafTerms()
|
|
check leafTerms.len == 1
|
|
|
|
test "Circular dependency detection":
|
|
## Test detection of circular dependencies
|
|
|
|
var profile = newVariantProfile()
|
|
profile.addFlag("optimization", "lto")
|
|
profile.calculateHash()
|
|
|
|
# Create demands
|
|
let demandA = VariantDemand(packageName: "packageA", variantProfile: profile, optional: false)
|
|
let demandB = VariantDemand(packageName: "packageB", variantProfile: profile, optional: false)
|
|
|
|
# Create circular dependency: A -> B -> A
|
|
let dependencyMap = {
|
|
"packageA": @[demandB],
|
|
"packageB": @[demandA]
|
|
}.toTable()
|
|
|
|
# Build graph
|
|
let buildResult = buildSimpleGraph(@[demandA], dependencyMap)
|
|
|
|
let graph = buildResult.graph
|
|
check graph.getStats().terms == 2
|
|
check graph.getStats().edges == 2
|
|
|
|
# Graph should detect the cycle
|
|
check graph.hasCycle()
|
|
|
|
let cycles = graph.findCycles()
|
|
check cycles.len > 0
|
|
|
|
test "Variant unification during build":
|
|
## Test that variant unification happens during graph building
|
|
|
|
# Create compatible variant profiles
|
|
var profile1 = newVariantProfile()
|
|
profile1.addFlag("optimization", "lto")
|
|
profile1.calculateHash()
|
|
|
|
var profile2 = newVariantProfile()
|
|
profile2.addFlag("security", "hardened")
|
|
profile2.calculateHash()
|
|
|
|
# Create demands for same package with different variants
|
|
let demandA = VariantDemand(packageName: "packageA", variantProfile: profile1, optional: false)
|
|
let demandShared1 = VariantDemand(packageName: "shared", variantProfile: profile1, optional: false)
|
|
let demandShared2 = VariantDemand(packageName: "shared", variantProfile: profile2, optional: false)
|
|
|
|
# Create dependency map: A -> shared, B -> shared
|
|
let dependencyMap = {
|
|
"packageA": @[demandShared1],
|
|
"packageB": @[demandShared2],
|
|
"shared": @[]
|
|
}.toTable()
|
|
|
|
# Build graph with both A and B as roots
|
|
let demandB = VariantDemand(packageName: "packageB", variantProfile: profile2, optional: false)
|
|
let buildResult = buildSimpleGraph(@[demandA, demandB], dependencyMap)
|
|
check buildResult.conflicts.len == 0
|
|
|
|
let graph = buildResult.graph
|
|
|
|
# Should have unified the "shared" package
|
|
let sharedTerms = graph.getTermsByPackage("shared")
|
|
check sharedTerms.len == 1 # Should be unified into single term
|
|
|
|
# The unified variant should have both flags
|
|
let unifiedProfile = sharedTerms[0].variantProfile
|
|
check unifiedProfile.hasDomain("optimization")
|
|
check unifiedProfile.hasDomain("security")
|
|
|
|
test "Handle missing package gracefully":
|
|
## Test handling of missing packages in dependency map
|
|
|
|
var profile = newVariantProfile()
|
|
profile.addFlag("optimization", "lto")
|
|
profile.calculateHash()
|
|
|
|
let demandA = VariantDemand(packageName: "packageA", variantProfile: profile, optional: false)
|
|
let demandMissing = VariantDemand(packageName: "missing", variantProfile: profile, optional: false)
|
|
|
|
# Create dependency map where A depends on missing package
|
|
let dependencyMap = {
|
|
"packageA": @[demandMissing]
|
|
# "missing" is not in the map
|
|
}.toTable()
|
|
|
|
# Build graph
|
|
let buildResult = buildSimpleGraph(@[demandA], dependencyMap)
|
|
|
|
# Should create terms for both A and missing (missing gets added as a demand)
|
|
let graph = buildResult.graph
|
|
let aTerms = graph.getTermsByPackage("packageA")
|
|
check aTerms.len == 1
|
|
|
|
let missingTerms = graph.getTermsByPackage("missing")
|
|
check missingTerms.len == 1 # Missing package is added as a term
|
|
|
|
# There should be an edge from A to missing since A depends on missing
|
|
let aOutgoing = graph.getOutgoingEdges(aTerms[0].id)
|
|
check aOutgoing.len == 1 # Edge from A to missing
|
|
check aOutgoing[0].toTerm == missingTerms[0].id
|
|
|
|
test "Handle variant conflicts":
|
|
## Test handling of variant conflicts during unification
|
|
|
|
# Create conflicting variant profiles (exclusive flags)
|
|
var profile1 = newVariantProfile()
|
|
profile1.addDomain(newVariantDomain("libc", Exclusive))
|
|
profile1.addFlag("libc", "glibc") # Exclusive flag
|
|
profile1.calculateHash()
|
|
|
|
var profile2 = newVariantProfile()
|
|
profile2.addDomain(newVariantDomain("libc", Exclusive))
|
|
profile2.addFlag("libc", "musl") # Conflicting exclusive flag
|
|
profile2.calculateHash()
|
|
|
|
# Create demands for same package with conflicting variants
|
|
let demandShared1 = VariantDemand(packageName: "shared", variantProfile: profile1, optional: false)
|
|
let demandShared2 = VariantDemand(packageName: "shared", variantProfile: profile2, optional: false)
|
|
|
|
let demandA = VariantDemand(packageName: "packageA", variantProfile: profile1, optional: false)
|
|
let demandB = VariantDemand(packageName: "packageB", variantProfile: profile2, optional: false)
|
|
|
|
# Create dependency map: A -> shared, B -> shared
|
|
let dependencyMap = {
|
|
"packageA": @[demandShared1],
|
|
"packageB": @[demandShared2],
|
|
"shared": @[]
|
|
}.toTable()
|
|
|
|
# Build graph
|
|
let buildResult = buildSimpleGraph(@[demandA, demandB], dependencyMap)
|
|
|
|
# Should detect variant conflict
|
|
check buildResult.conflicts.len > 0
|
|
check buildResult.warnings.len > 0
|
|
|
|
# Conflicted package should not appear in graph
|
|
let graph = buildResult.graph
|
|
let sharedTerms = graph.getTermsByPackage("shared")
|
|
check sharedTerms.len == 0 # Conflicted package excluded
|
|
|
|
test "Validate graph structure":
|
|
## Test graph validation functionality
|
|
|
|
var profile = newVariantProfile()
|
|
profile.addFlag("optimization", "lto")
|
|
profile.calculateHash()
|
|
|
|
let demandA = VariantDemand(packageName: "packageA", variantProfile: profile, optional: false)
|
|
let demandB = VariantDemand(packageName: "packageB", variantProfile: profile, optional: false)
|
|
|
|
let dependencyMap = {
|
|
"packageA": @[demandB],
|
|
"packageB": @[]
|
|
}.toTable()
|
|
|
|
let buildResult = buildSimpleGraph(@[demandA], dependencyMap)
|
|
let graph = buildResult.graph
|
|
|
|
# Graph should be valid
|
|
let isValid = validateGraph(graph)
|
|
check isValid
|
|
|
|
test "Get root and leaf terms":
|
|
## Test identification of root and leaf terms
|
|
|
|
var profile = newVariantProfile()
|
|
profile.addFlag("optimization", "lto")
|
|
profile.calculateHash()
|
|
|
|
# Create chain: root -> middle -> leaf
|
|
let demandRoot = VariantDemand(packageName: "root", variantProfile: profile, optional: false)
|
|
let demandMiddle = VariantDemand(packageName: "middle", variantProfile: profile, optional: false)
|
|
let demandLeaf = VariantDemand(packageName: "leaf", variantProfile: profile, optional: false)
|
|
|
|
let dependencyMap = {
|
|
"root": @[demandMiddle],
|
|
"middle": @[demandLeaf],
|
|
"leaf": @[]
|
|
}.toTable()
|
|
|
|
let buildResult = buildSimpleGraph(@[demandRoot], dependencyMap)
|
|
let graph = buildResult.graph
|
|
|
|
# Check root terms
|
|
let rootTerms = getRootTerms(graph)
|
|
check rootTerms.len == 1
|
|
let rootTerm = graph.getTerm(rootTerms[0]).get
|
|
check rootTerm.packageName == "root"
|
|
|
|
# Check leaf terms
|
|
let leafTerms = getLeafTerms(graph)
|
|
check leafTerms.len == 1
|
|
let leafTerm = graph.getTerm(leafTerms[0]).get
|
|
check leafTerm.packageName == "leaf"
|
|
|
|
test "Property: Graph Completeness":
|
|
## **Property 3: Graph Completeness**
|
|
## **Validates: Requirements 3.1, 3.5**
|
|
##
|
|
## For any set of package demands, the resulting dependency graph
|
|
## should contain all reachable packages and their dependencies.
|
|
|
|
# Test with various graph structures
|
|
for i in 1..10:
|
|
var profile = newVariantProfile()
|
|
profile.addFlag("test", "property" & $i)
|
|
profile.calculateHash()
|
|
|
|
# Create a chain of dependencies: pkg1 -> pkg2 -> pkg3 -> ... -> pkgN
|
|
let chainLength = (i mod 5) + 2 # Chain length between 2 and 6
|
|
var demands: seq[VariantDemand] = @[]
|
|
var dependencyMap = initTable[string, seq[VariantDemand]]()
|
|
|
|
# Build chain
|
|
for j in 1..chainLength:
|
|
let pkgName = "pkg" & $j
|
|
let demand = VariantDemand(
|
|
packageName: pkgName,
|
|
variantProfile: profile,
|
|
optional: false
|
|
)
|
|
demands.add(demand)
|
|
|
|
# Each package depends on the next one (except the last)
|
|
if j < chainLength:
|
|
let nextPkgName = "pkg" & $(j + 1)
|
|
let nextDemand = VariantDemand(
|
|
packageName: nextPkgName,
|
|
variantProfile: profile,
|
|
optional: false
|
|
)
|
|
dependencyMap[pkgName] = @[nextDemand]
|
|
else:
|
|
dependencyMap[pkgName] = @[] # Last package has no dependencies
|
|
|
|
# Build graph from first package only
|
|
let buildResult = buildSimpleGraph(@[demands[0]], dependencyMap)
|
|
let graph = buildResult.graph
|
|
|
|
# Property: Graph should contain all packages in the chain
|
|
check graph.getStats().terms == chainLength
|
|
|
|
# Property: Graph should have exactly (chainLength - 1) edges
|
|
check graph.getStats().edges == chainLength - 1
|
|
|
|
# Property: Each package in the chain should be present
|
|
for j in 1..chainLength:
|
|
let pkgName = "pkg" & $j
|
|
let terms = graph.getTermsByPackage(pkgName)
|
|
check terms.len == 1 # Each package should appear exactly once
|
|
|
|
# Property: Graph should be acyclic
|
|
check not graph.hasCycle()
|
|
|
|
# Property: Graph should have exactly one root (pkg1)
|
|
let rootTerms = graph.getRootTerms()
|
|
check rootTerms.len == 1
|
|
|
|
# Property: Graph should have exactly one leaf (last package)
|
|
let leafTerms = graph.getLeafTerms()
|
|
check leafTerms.len == 1 |