373 lines
17 KiB
Nim
373 lines
17 KiB
Nim
## Unit Tests for Topological Sort
|
|
##
|
|
## Tests for the topological sorting implementation using Kahn's algorithm.
|
|
## Topological sort produces an ordering where dependencies come before dependents.
|
|
|
|
import std/[unittest, options, sequtils]
|
|
import ../src/nip/resolver/dependency_graph
|
|
import ../src/nip/resolver/variant_types
|
|
|
|
suite "Topological Sort Tests":
|
|
|
|
test "Simple chain produces correct order":
|
|
## Test topological sort on a simple chain: A -> B -> C
|
|
|
|
var graph = newDependencyGraph()
|
|
var profile = newVariantProfile()
|
|
profile.addFlag("optimization", "lto")
|
|
profile.calculateHash()
|
|
|
|
# Create terms
|
|
let termAId = createTermId("packageA", profile.hash)
|
|
let termBId = createTermId("packageB", profile.hash)
|
|
let termCId = createTermId("packageC", profile.hash)
|
|
|
|
let termA = PackageTerm(id: termAId, packageName: "packageA", variantProfile: profile, optional: false, source: "nix")
|
|
let termB = PackageTerm(id: termBId, packageName: "packageB", variantProfile: profile, optional: false, source: "nix")
|
|
let termC = PackageTerm(id: termCId, packageName: "packageC", variantProfile: profile, optional: false, source: "nix")
|
|
|
|
graph.addTerm(termA)
|
|
graph.addTerm(termB)
|
|
graph.addTerm(termC)
|
|
|
|
# Create edges: A -> B -> C
|
|
graph.addEdge(DependencyEdge(fromTerm: termAId, toTerm: termBId, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termBId, toTerm: termCId, dependencyType: Required))
|
|
|
|
# Perform topological sort
|
|
let sorted = graph.topologicalSort()
|
|
|
|
# Check that all nodes are present
|
|
check sorted.len == 3
|
|
|
|
# Check that dependencies come before dependents
|
|
# For installation order: dependencies first (C, then B, then A)
|
|
let posA = sorted.find(termAId)
|
|
let posB = sorted.find(termBId)
|
|
let posC = sorted.find(termCId)
|
|
|
|
# Dependencies must come before dependents
|
|
check posC < posB # C before B (B depends on C)
|
|
check posB < posA # B before A (A depends on B)
|
|
|
|
test "Diamond produces valid order":
|
|
## Test topological sort on diamond: A -> B,C -> D
|
|
|
|
var graph = newDependencyGraph()
|
|
var profile = newVariantProfile()
|
|
profile.addFlag("optimization", "lto")
|
|
profile.calculateHash()
|
|
|
|
# Create terms
|
|
let termAId = createTermId("packageA", profile.hash)
|
|
let termBId = createTermId("packageB", profile.hash)
|
|
let termCId = createTermId("packageC", profile.hash)
|
|
let termDId = createTermId("packageD", profile.hash)
|
|
|
|
let termA = PackageTerm(id: termAId, packageName: "packageA", variantProfile: profile, optional: false, source: "nix")
|
|
let termB = PackageTerm(id: termBId, packageName: "packageB", variantProfile: profile, optional: false, source: "nix")
|
|
let termC = PackageTerm(id: termCId, packageName: "packageC", variantProfile: profile, optional: false, source: "nix")
|
|
let termD = PackageTerm(id: termDId, packageName: "packageD", variantProfile: profile, optional: false, source: "nix")
|
|
|
|
graph.addTerm(termA)
|
|
graph.addTerm(termB)
|
|
graph.addTerm(termC)
|
|
graph.addTerm(termD)
|
|
|
|
# Create edges: A -> B, A -> C, B -> D, C -> D
|
|
graph.addEdge(DependencyEdge(fromTerm: termAId, toTerm: termBId, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termAId, toTerm: termCId, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termBId, toTerm: termDId, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termCId, toTerm: termDId, dependencyType: Required))
|
|
|
|
# Perform topological sort
|
|
let sorted = graph.topologicalSort()
|
|
|
|
# Check that all nodes are present
|
|
check sorted.len == 4
|
|
|
|
# Check that dependencies come before dependents
|
|
# Installation order: D first (no deps), then B and C (depend on D), then A (depends on B and C)
|
|
let posA = sorted.find(termAId)
|
|
let posB = sorted.find(termBId)
|
|
let posC = sorted.find(termCId)
|
|
let posD = sorted.find(termDId)
|
|
|
|
# D must come before both B and C (B and C depend on D)
|
|
check posD < posB
|
|
check posD < posC
|
|
|
|
# Both B and C must come before A (A depends on B and C)
|
|
check posB < posA
|
|
check posC < posA
|
|
|
|
test "Cycle raises error":
|
|
## Test that topological sort raises error on cyclic graph
|
|
|
|
var graph = newDependencyGraph()
|
|
var profile = newVariantProfile()
|
|
profile.addFlag("optimization", "lto")
|
|
profile.calculateHash()
|
|
|
|
# Create terms
|
|
let termAId = createTermId("packageA", profile.hash)
|
|
let termBId = createTermId("packageB", profile.hash)
|
|
|
|
let termA = PackageTerm(id: termAId, packageName: "packageA", variantProfile: profile, optional: false, source: "nix")
|
|
let termB = PackageTerm(id: termBId, packageName: "packageB", variantProfile: profile, optional: false, source: "nix")
|
|
|
|
graph.addTerm(termA)
|
|
graph.addTerm(termB)
|
|
|
|
# Create cycle: A -> B -> A
|
|
graph.addEdge(DependencyEdge(fromTerm: termAId, toTerm: termBId, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termBId, toTerm: termAId, dependencyType: Required))
|
|
|
|
# Topological sort should raise error
|
|
expect(ValueError):
|
|
discard graph.topologicalSort()
|
|
|
|
test "Empty graph returns empty list":
|
|
## Test topological sort on empty graph
|
|
|
|
let graph = newDependencyGraph()
|
|
let sorted = graph.topologicalSort()
|
|
|
|
check sorted.len == 0
|
|
|
|
test "Single node":
|
|
## Test topological sort on single node
|
|
|
|
var graph = newDependencyGraph()
|
|
var profile = newVariantProfile()
|
|
profile.addFlag("optimization", "lto")
|
|
profile.calculateHash()
|
|
|
|
let termId = createTermId("packageA", profile.hash)
|
|
let term = PackageTerm(id: termId, packageName: "packageA", variantProfile: profile, optional: false, source: "nix")
|
|
|
|
graph.addTerm(term)
|
|
|
|
let sorted = graph.topologicalSort()
|
|
|
|
check sorted.len == 1
|
|
check sorted[0] == termId
|
|
|
|
test "Multiple independent nodes":
|
|
## Test topological sort on graph with no edges
|
|
|
|
var graph = newDependencyGraph()
|
|
var profile = newVariantProfile()
|
|
profile.addFlag("optimization", "lto")
|
|
profile.calculateHash()
|
|
|
|
# Create three independent terms
|
|
let termAId = createTermId("packageA", profile.hash)
|
|
let termBId = createTermId("packageB", profile.hash)
|
|
let termCId = createTermId("packageC", profile.hash)
|
|
|
|
let termA = PackageTerm(id: termAId, packageName: "packageA", variantProfile: profile, optional: false, source: "nix")
|
|
let termB = PackageTerm(id: termBId, packageName: "packageB", variantProfile: profile, optional: false, source: "nix")
|
|
let termC = PackageTerm(id: termCId, packageName: "packageC", variantProfile: profile, optional: false, source: "nix")
|
|
|
|
graph.addTerm(termA)
|
|
graph.addTerm(termB)
|
|
graph.addTerm(termC)
|
|
|
|
# No edges - all independent
|
|
|
|
let sorted = graph.topologicalSort()
|
|
|
|
# All nodes should be present
|
|
check sorted.len == 3
|
|
check termAId in sorted
|
|
check termBId in sorted
|
|
check termCId in sorted
|
|
|
|
test "Complex graph with multiple paths":
|
|
## Test topological sort on complex graph with multiple dependency paths
|
|
|
|
var graph = newDependencyGraph()
|
|
var profile = newVariantProfile()
|
|
profile.addFlag("optimization", "lto")
|
|
profile.calculateHash()
|
|
|
|
# Create terms: A -> B -> D, A -> C -> D, B -> E, C -> E
|
|
let termAId = createTermId("packageA", profile.hash)
|
|
let termBId = createTermId("packageB", profile.hash)
|
|
let termCId = createTermId("packageC", profile.hash)
|
|
let termDId = createTermId("packageD", profile.hash)
|
|
let termEId = createTermId("packageE", profile.hash)
|
|
|
|
let termA = PackageTerm(id: termAId, packageName: "packageA", variantProfile: profile, optional: false, source: "nix")
|
|
let termB = PackageTerm(id: termBId, packageName: "packageB", variantProfile: profile, optional: false, source: "nix")
|
|
let termC = PackageTerm(id: termCId, packageName: "packageC", variantProfile: profile, optional: false, source: "nix")
|
|
let termD = PackageTerm(id: termDId, packageName: "packageD", variantProfile: profile, optional: false, source: "nix")
|
|
let termE = PackageTerm(id: termEId, packageName: "packageE", variantProfile: profile, optional: false, source: "nix")
|
|
|
|
graph.addTerm(termA)
|
|
graph.addTerm(termB)
|
|
graph.addTerm(termC)
|
|
graph.addTerm(termD)
|
|
graph.addTerm(termE)
|
|
|
|
# Create edges
|
|
graph.addEdge(DependencyEdge(fromTerm: termAId, toTerm: termBId, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termAId, toTerm: termCId, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termBId, toTerm: termDId, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termCId, toTerm: termDId, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termBId, toTerm: termEId, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termCId, toTerm: termEId, dependencyType: Required))
|
|
|
|
# Perform topological sort
|
|
let sorted = graph.topologicalSort()
|
|
|
|
# Check that all nodes are present
|
|
check sorted.len == 5
|
|
|
|
# Check dependency constraints
|
|
# Installation order: D and E first (no deps), then B and C (depend on D and E), then A (depends on B and C)
|
|
let posA = sorted.find(termAId)
|
|
let posB = sorted.find(termBId)
|
|
let posC = sorted.find(termCId)
|
|
let posD = sorted.find(termDId)
|
|
let posE = sorted.find(termEId)
|
|
|
|
# D and E must come before B and C (B and C depend on D and E)
|
|
check posD < posB
|
|
check posD < posC
|
|
check posE < posB
|
|
check posE < posC
|
|
|
|
# B and C must come before A (A depends on B and C)
|
|
check posB < posA
|
|
check posC < posA
|
|
|
|
suite "Topological Sort Property Tests":
|
|
|
|
test "Property: Dependencies always come before dependents":
|
|
## Property-based test: For any valid dependency graph,
|
|
## the topological sort must place all dependencies before their dependents.
|
|
##
|
|
## This property validates Requirements 9.1, 9.2, 9.3:
|
|
## - 9.1: Produce valid installation order
|
|
## - 9.2: Dependencies installed before dependents
|
|
## - 9.3: Handle complex dependency patterns
|
|
|
|
# Test with multiple graph structures
|
|
for iteration in 1..20:
|
|
var graph = newDependencyGraph()
|
|
var profile = newVariantProfile()
|
|
profile.addFlag("optimization", "lto")
|
|
profile.addFlag("iteration", $iteration)
|
|
profile.calculateHash()
|
|
|
|
# Create a random graph structure
|
|
# We'll test different patterns: chains, diamonds, trees
|
|
let pattern = iteration mod 4
|
|
|
|
case pattern:
|
|
of 0:
|
|
# Chain: A -> B -> C -> D
|
|
let termAId = createTermId("packageA", profile.hash)
|
|
let termBId = createTermId("packageB", profile.hash)
|
|
let termCId = createTermId("packageC", profile.hash)
|
|
let termDId = createTermId("packageD", profile.hash)
|
|
|
|
graph.addTerm(PackageTerm(id: termAId, packageName: "packageA", variantProfile: profile, optional: false, source: "nix"))
|
|
graph.addTerm(PackageTerm(id: termBId, packageName: "packageB", variantProfile: profile, optional: false, source: "nix"))
|
|
graph.addTerm(PackageTerm(id: termCId, packageName: "packageC", variantProfile: profile, optional: false, source: "nix"))
|
|
graph.addTerm(PackageTerm(id: termDId, packageName: "packageD", variantProfile: profile, optional: false, source: "nix"))
|
|
|
|
graph.addEdge(DependencyEdge(fromTerm: termAId, toTerm: termBId, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termBId, toTerm: termCId, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termCId, toTerm: termDId, dependencyType: Required))
|
|
|
|
of 1:
|
|
# Diamond: A -> B,C -> D
|
|
let termAId = createTermId("packageA", profile.hash)
|
|
let termBId = createTermId("packageB", profile.hash)
|
|
let termCId = createTermId("packageC", profile.hash)
|
|
let termDId = createTermId("packageD", profile.hash)
|
|
|
|
graph.addTerm(PackageTerm(id: termAId, packageName: "packageA", variantProfile: profile, optional: false, source: "nix"))
|
|
graph.addTerm(PackageTerm(id: termBId, packageName: "packageB", variantProfile: profile, optional: false, source: "nix"))
|
|
graph.addTerm(PackageTerm(id: termCId, packageName: "packageC", variantProfile: profile, optional: false, source: "nix"))
|
|
graph.addTerm(PackageTerm(id: termDId, packageName: "packageD", variantProfile: profile, optional: false, source: "nix"))
|
|
|
|
graph.addEdge(DependencyEdge(fromTerm: termAId, toTerm: termBId, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termAId, toTerm: termCId, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termBId, toTerm: termDId, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termCId, toTerm: termDId, dependencyType: Required))
|
|
|
|
of 2:
|
|
# Tree: A -> B,C; B -> D,E; C -> F,G
|
|
let termAId = createTermId("packageA", profile.hash)
|
|
let termBId = createTermId("packageB", profile.hash)
|
|
let termCId = createTermId("packageC", profile.hash)
|
|
let termDId = createTermId("packageD", profile.hash)
|
|
let termEId = createTermId("packageE", profile.hash)
|
|
let termFId = createTermId("packageF", profile.hash)
|
|
let termGId = createTermId("packageG", profile.hash)
|
|
|
|
graph.addTerm(PackageTerm(id: termAId, packageName: "packageA", variantProfile: profile, optional: false, source: "nix"))
|
|
graph.addTerm(PackageTerm(id: termBId, packageName: "packageB", variantProfile: profile, optional: false, source: "nix"))
|
|
graph.addTerm(PackageTerm(id: termCId, packageName: "packageC", variantProfile: profile, optional: false, source: "nix"))
|
|
graph.addTerm(PackageTerm(id: termDId, packageName: "packageD", variantProfile: profile, optional: false, source: "nix"))
|
|
graph.addTerm(PackageTerm(id: termEId, packageName: "packageE", variantProfile: profile, optional: false, source: "nix"))
|
|
graph.addTerm(PackageTerm(id: termFId, packageName: "packageF", variantProfile: profile, optional: false, source: "nix"))
|
|
graph.addTerm(PackageTerm(id: termGId, packageName: "packageG", variantProfile: profile, optional: false, source: "nix"))
|
|
|
|
graph.addEdge(DependencyEdge(fromTerm: termAId, toTerm: termBId, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termAId, toTerm: termCId, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termBId, toTerm: termDId, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termBId, toTerm: termEId, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termCId, toTerm: termFId, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termCId, toTerm: termGId, dependencyType: Required))
|
|
|
|
else:
|
|
# Complex: Multiple paths and shared dependencies
|
|
let termAId = createTermId("packageA", profile.hash)
|
|
let termBId = createTermId("packageB", profile.hash)
|
|
let termCId = createTermId("packageC", profile.hash)
|
|
let termDId = createTermId("packageD", profile.hash)
|
|
let termEId = createTermId("packageE", profile.hash)
|
|
|
|
graph.addTerm(PackageTerm(id: termAId, packageName: "packageA", variantProfile: profile, optional: false, source: "nix"))
|
|
graph.addTerm(PackageTerm(id: termBId, packageName: "packageB", variantProfile: profile, optional: false, source: "nix"))
|
|
graph.addTerm(PackageTerm(id: termCId, packageName: "packageC", variantProfile: profile, optional: false, source: "nix"))
|
|
graph.addTerm(PackageTerm(id: termDId, packageName: "packageD", variantProfile: profile, optional: false, source: "nix"))
|
|
graph.addTerm(PackageTerm(id: termEId, packageName: "packageE", variantProfile: profile, optional: false, source: "nix"))
|
|
|
|
graph.addEdge(DependencyEdge(fromTerm: termAId, toTerm: termBId, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termAId, toTerm: termCId, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termBId, toTerm: termDId, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termCId, toTerm: termDId, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termBId, toTerm: termEId, dependencyType: Required))
|
|
graph.addEdge(DependencyEdge(fromTerm: termCId, toTerm: termEId, dependencyType: Required))
|
|
|
|
# Perform topological sort
|
|
let sorted = graph.topologicalSort()
|
|
|
|
# Property: For each node in sorted order, all its dependencies must come before it
|
|
for i, termId in sorted:
|
|
let outgoingEdges = graph.getOutgoingEdges(termId)
|
|
|
|
for edge in outgoingEdges:
|
|
# edge.toTerm is a dependency of termId
|
|
# It must appear before termId in the sorted list
|
|
let dependencyPos = sorted.find(edge.toTerm)
|
|
|
|
# Check: dependency position < dependent position
|
|
if dependencyPos >= i:
|
|
checkpoint("Iteration: " & $iteration)
|
|
checkpoint("Pattern: " & $pattern)
|
|
checkpoint("Dependent: " & $termId)
|
|
checkpoint("Dependency: " & $edge.toTerm)
|
|
checkpoint("Dependent position: " & $i)
|
|
checkpoint("Dependency position: " & $dependencyPos)
|
|
checkpoint("Sorted order: " & $sorted)
|
|
fail()
|
|
|
|
check dependencyPos < i
|