251 lines
8.1 KiB
Nim
251 lines
8.1 KiB
Nim
## Property-Based Tests for Conflict Minimality
|
|
##
|
|
## This module tests the property that minimal conflict extraction
|
|
## produces the smallest possible set of conflicting incompatibilities.
|
|
##
|
|
## Property: Conflict Minimality
|
|
## For any set of incompatibilities that cause a conflict,
|
|
## the extracted minimal set should be a subset of the original set,
|
|
## and removing any incompatibility from the minimal set should
|
|
## result in a non-conflicting set (or at least a smaller conflict).
|
|
##
|
|
## Requirements:
|
|
## - 7.5: Provide minimal conflicting requirements
|
|
|
|
import std/[unittest, random, sequtils, options, algorithm]
|
|
import ../src/nip/resolver/conflict_detection
|
|
import ../src/nip/resolver/solver_types
|
|
import ../src/nip/manifest_parser
|
|
|
|
suite "Conflict Minimality Properties":
|
|
|
|
test "Property: Minimal conflict is subset of original":
|
|
## For any set of incompatibilities, the minimal conflict
|
|
## should be a subset of the original set.
|
|
##
|
|
## **Feature: nip-dependency-resolution, Property 6: Conflict Minimality**
|
|
## **Validates: Requirements 7.5**
|
|
|
|
# Generate random incompatibilities
|
|
var incompatibilities: seq[Incompatibility] = @[]
|
|
|
|
for i in 0 ..< 10:
|
|
incompatibilities.add(Incompatibility(
|
|
terms: @[],
|
|
cause: if i mod 3 == 0: Root elif i mod 3 == 1: Dependency else: IncompatibilityCause.VariantConflict,
|
|
externalContext: "Incomp " & $i,
|
|
fromPackage: some("pkg" & $i),
|
|
fromVersion: none(SemanticVersion)
|
|
))
|
|
|
|
let minimal = extractMinimalConflict(incompatibilities)
|
|
|
|
check minimal.isSome
|
|
|
|
# The minimal set should be a subset of the original
|
|
let minimalSet = minimal.get()
|
|
check minimalSet.len <= incompatibilities.len
|
|
|
|
# Every incompatibility in minimal should be in original
|
|
for minIncomp in minimalSet:
|
|
let found = incompatibilities.anyIt(
|
|
it.externalContext == minIncomp.externalContext and
|
|
it.cause == minIncomp.cause
|
|
)
|
|
check found
|
|
|
|
test "Property: Minimal conflict preserves root incompatibilities":
|
|
## Root incompatibilities (user requirements) should always
|
|
## be preserved in the minimal conflict set.
|
|
##
|
|
## **Feature: nip-dependency-resolution, Property 6: Conflict Minimality**
|
|
## **Validates: Requirements 7.5**
|
|
|
|
# Create a mix of incompatibilities with at least one root
|
|
let rootIncomp = Incompatibility(
|
|
terms: @[],
|
|
cause: Root,
|
|
externalContext: "User requirement",
|
|
fromPackage: some("nginx"),
|
|
fromVersion: none(SemanticVersion)
|
|
)
|
|
|
|
var incompatibilities = @[rootIncomp]
|
|
|
|
for i in 0 ..< 5:
|
|
incompatibilities.add(Incompatibility(
|
|
terms: @[],
|
|
cause: Dependency,
|
|
externalContext: "Dependency " & $i,
|
|
fromPackage: some("pkg" & $i),
|
|
fromVersion: none(SemanticVersion)
|
|
))
|
|
|
|
let minimal = extractMinimalConflict(incompatibilities)
|
|
|
|
check minimal.isSome
|
|
|
|
# Root incompatibilities should be preserved
|
|
let hasRoot = minimal.get().anyIt(it.cause == Root)
|
|
check hasRoot
|
|
|
|
test "Property: Minimal conflict is deterministic":
|
|
## Extracting minimal conflict from the same set should
|
|
## always produce the same result.
|
|
##
|
|
## **Feature: nip-dependency-resolution, Property 6: Conflict Minimality**
|
|
## **Validates: Requirements 7.5**
|
|
|
|
let incompatibilities = @[
|
|
Incompatibility(
|
|
terms: @[],
|
|
cause: Root,
|
|
externalContext: "Root",
|
|
fromPackage: some("pkg1"),
|
|
fromVersion: none(SemanticVersion)
|
|
),
|
|
Incompatibility(
|
|
terms: @[],
|
|
cause: Dependency,
|
|
externalContext: "Dep1",
|
|
fromPackage: some("pkg2"),
|
|
fromVersion: none(SemanticVersion)
|
|
),
|
|
Incompatibility(
|
|
terms: @[],
|
|
cause: Dependency,
|
|
externalContext: "Dep2",
|
|
fromPackage: some("pkg3"),
|
|
fromVersion: none(SemanticVersion)
|
|
)
|
|
]
|
|
|
|
# Extract minimal conflict multiple times
|
|
let minimal1 = extractMinimalConflict(incompatibilities)
|
|
let minimal2 = extractMinimalConflict(incompatibilities)
|
|
let minimal3 = extractMinimalConflict(incompatibilities)
|
|
|
|
# All results should be the same
|
|
check minimal1.isSome
|
|
check minimal2.isSome
|
|
check minimal3.isSome
|
|
|
|
check minimal1.get().len == minimal2.get().len
|
|
check minimal2.get().len == minimal3.get().len
|
|
|
|
# The contexts should match
|
|
let contexts1 = minimal1.get().mapIt(it.externalContext).sorted()
|
|
let contexts2 = minimal2.get().mapIt(it.externalContext).sorted()
|
|
let contexts3 = minimal3.get().mapIt(it.externalContext).sorted()
|
|
|
|
check contexts1 == contexts2
|
|
check contexts2 == contexts3
|
|
|
|
test "Property: Minimal conflict handles empty input":
|
|
## Extracting minimal conflict from empty set should return None.
|
|
##
|
|
## **Feature: nip-dependency-resolution, Property 6: Conflict Minimality**
|
|
## **Validates: Requirements 7.5**
|
|
|
|
let minimal = extractMinimalConflict(@[])
|
|
|
|
check minimal.isNone
|
|
|
|
test "Property: Minimal conflict handles single incompatibility":
|
|
## Extracting minimal conflict from single incompatibility
|
|
## should return that incompatibility.
|
|
##
|
|
## **Feature: nip-dependency-resolution, Property 6: Conflict Minimality**
|
|
## **Validates: Requirements 7.5**
|
|
|
|
let incomp = Incompatibility(
|
|
terms: @[],
|
|
cause: Root,
|
|
externalContext: "Single",
|
|
fromPackage: some("pkg"),
|
|
fromVersion: none(SemanticVersion)
|
|
)
|
|
|
|
let minimal = extractMinimalConflict(@[incomp])
|
|
|
|
check minimal.isSome
|
|
check minimal.get().len == 1
|
|
check minimal.get()[0].externalContext == "Single"
|
|
|
|
test "Property: Minimal conflict reduces redundancy":
|
|
## The minimal conflict should have fewer or equal incompatibilities
|
|
## than the original set (it should not add incompatibilities).
|
|
##
|
|
## **Feature: nip-dependency-resolution, Property 6: Conflict Minimality**
|
|
## **Validates: Requirements 7.5**
|
|
|
|
# Create a large set of incompatibilities
|
|
var incompatibilities: seq[Incompatibility] = @[]
|
|
|
|
for i in 0 ..< 20:
|
|
incompatibilities.add(Incompatibility(
|
|
terms: @[],
|
|
cause: if i == 0: Root else: Dependency,
|
|
externalContext: "Incomp " & $i,
|
|
fromPackage: some("pkg" & $(i mod 5)),
|
|
fromVersion: none(SemanticVersion)
|
|
))
|
|
|
|
let minimal = extractMinimalConflict(incompatibilities)
|
|
|
|
check minimal.isSome
|
|
|
|
# Minimal should not have more incompatibilities than original
|
|
check minimal.get().len <= incompatibilities.len
|
|
|
|
# Minimal should have at least 1 incompatibility (if original had any)
|
|
check minimal.get().len >= 1
|
|
|
|
test "Property: Minimal conflict preserves conflict causes":
|
|
## The minimal conflict should preserve the causes of conflicts
|
|
## (Root, Dependency, VariantConflict, etc.)
|
|
##
|
|
## **Feature: nip-dependency-resolution, Property 6: Conflict Minimality**
|
|
## **Validates: Requirements 7.5**
|
|
|
|
let incompatibilities = @[
|
|
Incompatibility(
|
|
terms: @[],
|
|
cause: Root,
|
|
externalContext: "Root",
|
|
fromPackage: some("pkg1"),
|
|
fromVersion: none(SemanticVersion)
|
|
),
|
|
Incompatibility(
|
|
terms: @[],
|
|
cause: Dependency,
|
|
externalContext: "Dep",
|
|
fromPackage: some("pkg2"),
|
|
fromVersion: none(SemanticVersion)
|
|
),
|
|
Incompatibility(
|
|
terms: @[],
|
|
cause: IncompatibilityCause.VariantConflict,
|
|
externalContext: "Variant",
|
|
fromPackage: some("pkg3"),
|
|
fromVersion: none(SemanticVersion)
|
|
)
|
|
]
|
|
|
|
let minimal = extractMinimalConflict(incompatibilities)
|
|
|
|
check minimal.isSome
|
|
|
|
# The minimal set should contain at least one of each cause type
|
|
# (or at least preserve the causes that are present)
|
|
let causes = minimal.get().mapIt(it.cause)
|
|
|
|
# Should have at least one incompatibility
|
|
check causes.len >= 1
|
|
|
|
# All causes in minimal should be in original
|
|
for cause in causes:
|
|
let found = incompatibilities.anyIt(it.cause == cause)
|
|
check found
|
|
|