mirror of
https://github.com/apple/swift-collections
synced 2026-11-22 04:20:40 +00:00
- withEveryDeque/withEveryFullDeque now visit capacity 0. - checkEquatable reports transitivity violations instead of trapping when pairs arrive out of order (non-transitive oracles, maxSamples). - Minimal range-replaceable collections no longer trap in removeLast() and popLast(). - LifetimeTracked's "Double deinit" precondition can now fire. - withEvery, withEveryRange and withSomeArrayLayouts include the failing value in their "Throwing trace". - CustomCountedProducer drops its unused chunkSize parameter, and the two loops that reran identical cases over it are removed. Adds regression tests for the first three. Fixes #810
148 lines
4.8 KiB
Swift
148 lines
4.8 KiB
Swift
//===----------------------------------------------------------------------===//
|
|
//
|
|
// This source file is part of the Swift Collections open source project
|
|
//
|
|
// Copyright (c) 2014 - 2026 Apple Inc. and the Swift project authors
|
|
// Licensed under Apache License v2.0 with Runtime Library Exception
|
|
//
|
|
// See https://swift.org/LICENSE.txt for license information
|
|
//
|
|
// SPDX-License-Identifier: Apache-2.0 WITH Swift-exception
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
// Loosely adapted from https://github.com/apple/swift/tree/main/stdlib/private/StdlibUnittest
|
|
|
|
public func checkEquatable<Instance: Equatable>(
|
|
equivalenceClasses: [[Instance]],
|
|
maxSamples: Int? = nil,
|
|
file: StaticString = #filePath,
|
|
line: UInt = #line
|
|
) {
|
|
let instances = equivalenceClasses.flatMap { $0 }
|
|
let oracle = equivalenceClasses.indices.flatMap { i in repeatElement(i, count: equivalenceClasses[i].count) }
|
|
checkEquatable(instances, oracle: { oracle[$0] == oracle[$1] }, file: file, line: line)
|
|
}
|
|
|
|
public func checkEquatable<C: Collection>(
|
|
_ instances: C,
|
|
oracle: (C.Index, C.Index) -> Bool,
|
|
maxSamples: Int? = nil,
|
|
file: StaticString = #filePath,
|
|
line: UInt = #line
|
|
) where C.Element: Equatable {
|
|
let indices = Array(instances.indices)
|
|
checkEquatable(
|
|
Array(instances),
|
|
oracle: { oracle(indices[$0], indices[$1]) },
|
|
file: file, line: line)
|
|
}
|
|
|
|
public func checkEquatable<T : Equatable>(
|
|
expectedEqual: Bool, _ lhs: T, _ rhs: T,
|
|
file: StaticString = #filePath, line: UInt = #line
|
|
) {
|
|
checkEquatable(
|
|
[lhs, rhs],
|
|
oracle: { expectedEqual || $0 == $1 },
|
|
file: file, line: line)
|
|
}
|
|
|
|
public func checkEquatable<Instance: Equatable>(
|
|
_ instances: [Instance],
|
|
oracle: (Int, Int) -> Bool,
|
|
maxSamples: Int? = nil,
|
|
file: StaticString = #filePath,
|
|
line: UInt = #line
|
|
) {
|
|
let entry = TestContext.current.push("checkEquatable", file: file, line: line)
|
|
defer { TestContext.current.pop(entry) }
|
|
// For each index (which corresponds to an instance being tested) track the
|
|
// set of equal instances.
|
|
var transitivityScoreboard: [ClassBox<Set<Int>>] = instances.map { _ in
|
|
ClassBox([])
|
|
}
|
|
|
|
withSomeRanges(
|
|
"range", in: 0 ..< instances.count - 1, maxSamples: maxSamples
|
|
) { range in
|
|
let i = range.lowerBound
|
|
let j = range.upperBound
|
|
|
|
if i == j {
|
|
expectTrue(oracle(i, i),
|
|
"bad oracle: broken reflexivity at index \(i)")
|
|
}
|
|
let x = instances[i]
|
|
let y = instances[j]
|
|
|
|
let expectedXY = oracle(i, j)
|
|
expectEqual(oracle(j, i), expectedXY,
|
|
"bad oracle: broken symmetry between indices \(i), \(j)")
|
|
|
|
let actualXY = (x == y)
|
|
let actualYX = (y == x)
|
|
expectEqual(
|
|
actualXY, expectedXY,
|
|
"""
|
|
Elements \((expectedXY
|
|
? "expected equal, found not equal"
|
|
: "expected not equal, found equal")):
|
|
lhs (at index \(i)): \(String(reflecting: x))
|
|
rhs (at index \(j)): \(String(reflecting: y))
|
|
""")
|
|
|
|
expectEqual(
|
|
actualYX, actualXY,
|
|
"""
|
|
Reflexivity violation:
|
|
\(actualXY
|
|
? "lhs == rhs but !(rhs == lhs)"
|
|
: "!(lhs == rhs) but rhs == lhs")
|
|
lhs (at index \(i)): \(String(reflecting: x))
|
|
rhs (at index \(j)): \(String(reflecting: y))
|
|
""")
|
|
|
|
// Not-equal must be the inverse of equal.
|
|
expectNotEqual(
|
|
x != y, actualXY,
|
|
"""
|
|
`!=` returns the same result as `==`:
|
|
lhs (at index \(i)): \(String(reflecting: x))
|
|
rhs (at index \(j)): \(String(reflecting: y))
|
|
""")
|
|
|
|
// Check transitivity of the predicate represented by the oracle.
|
|
// If we are adding the instance `j` into an equivalence set, check that
|
|
// it is equal to every other instance in the set.
|
|
if expectedXY && i < j && transitivityScoreboard[i].value.insert(j).inserted {
|
|
if transitivityScoreboard[i].value.count == 1 {
|
|
transitivityScoreboard[i].value.insert(i)
|
|
}
|
|
for k in transitivityScoreboard[i].value {
|
|
expectTrue(
|
|
oracle(j, k),
|
|
"""
|
|
bad oracle: transitivity violation
|
|
x (at index \(i)): \(String(reflecting: x))
|
|
y (at index \(j)): \(String(reflecting: y))
|
|
z (at index \(k)): \(String(reflecting: instances[k]))
|
|
""")
|
|
// No need to check equality between actual values, we will check
|
|
// them with the checks above.
|
|
}
|
|
for k in transitivityScoreboard[j].value {
|
|
expectTrue(
|
|
oracle(i, k),
|
|
"""
|
|
bad oracle: transitivity violation
|
|
x (at index \(i)): \(String(reflecting: x))
|
|
y (at index \(j)): \(String(reflecting: y))
|
|
z (at index \(k)): \(String(reflecting: instances[k]))
|
|
""")
|
|
}
|
|
transitivityScoreboard[j] = transitivityScoreboard[i]
|
|
}
|
|
}
|
|
}
|