cardano-coin-selection
cardano-coin-selection copied to clipboard
Published
20 hours ago •
IntersectMBO
IntersectMBO
Tests fail with ghc 9.6 on stackage nightly
Add to expected test failures for now.
Test suite failure for package cardano-coin-selection-1.0.1
unit: exited with: ExitFailure 1
Full log available at /var/stackage/work/unpack-dir/.stack-work/logs/cardano-coin-selection-1.0.1-test.log
Cardano.CoinSelection
CoinMap properties
CoinMap coverage is adequate [✔]
+++ OK, passed 200 tests:
39.0% coin map has multiple entries
39.0% coin map has several unique values
34.0% coin map has one entry
34.0% coin map has one unique value
27.0% coin map is empty
CoinMapEntry coverage is adequate [✔]
+++ OK, passed 3200 tests:
86.72% coin map entry list has multiple entries
86.34% coin map entry list has multiple unique keys
40.16% coin map entry list has multiple duplicate keys
27.56% coin map entry list has no duplicate keys
15.69% coin map entry list has one duplicate key
11.34% coin map entry list has two duplicate keys
5.25% coin map entry list is empty
4.53% coin map entry list has one unique key
4.38% coin map entry list has one entry
3.88% coin map entry list has two unique keys
3.66% coin map entry list has two entries
coinMapFromList preserves total value for each unique key [✔]
+++ OK, passed 100 tests.
coinMapFromList preserves total value [✔]
+++ OK, passed 100 tests.
coinMapToList preserves total value [✔]
+++ OK, passed 100 tests.
coinMapFromList . coinMapToList = id [✔]
+++ OK, passed 100 tests.
coinMapToList . coinMapFromList = id (when no keys duplicated) [✔]
+++ OK, passed 100 tests.
coinMapToList order deterministic [✔]
+++ OK, passed 100 tests (43% shuffled).
CoinSelection properties
monoidal append preserves keys [✔]
+++ OK, passed 100 tests.
monoidal append preserves value [✔]
+++ OK, passed 100 tests.
CoinSelectionData properties
CoinSelectionData coverage is adequate [✔]
+++ OK, passed 200 tests (98.5% amountAvailable ≥ amountRequested).
Cardano.CoinSelection.Algorithm.LargestFirst
Coin selection: largest-first algorithm: unit tests
Expect success: case #1:
max=100, UTxO=[10,10,17], Output=[17] --> Right [17] [✔]
Expect success: case #2:
max=100, UTxO=[12,10,17], Output=[1] --> Right [17] [✔]
Expect success: case #3:
max=100, UTxO=[12,10,17], Output=[18] --> Right [12,17] [✔]
Expect success: case #4:
max=100, UTxO=[12,10,17], Output=[30] --> Right [10,12,17] [✔]
Expect success: case #5:
max=3, UTxO=[1,2,10,6,5], Output=[11,1] --> Right [6,10] [✔]
Expect success: case #6:
max=100, UTxO=[12,20,17], Output=[40,1,1,1] --> Right [12,17,20] [✔]
Expect success: case #7:
max=100, UTxO=[12,20,17], Output=[40,1] --> Right [12,17,20] [✔]
Expect success: case #8:
max=100, UTxO=[20,20,10,5], Output=[41,6] --> Right [10,20,20] [✔]
Expect success: case #9:
max=2, UTxO=[1,2,10,6,5], Output=[11,1] --> Right [6,10] [✔]
Expect success: fewer inputs than outputs: case #1:
max=1000, UTxO=[100,100], Output=[1,2,3,4] --> Right [100] [✔]
Expect success: fewer inputs than outputs: case #2:
max=1000, UTxO=[100,10], Output=[1,2,3,4] --> Right [100] [✔]
Expect success: fewer inputs than outputs: case #3:
max=1000, UTxO=[10,10], Output=[1,2,3,4] --> Right [10] [✔]
Expect success: fewer inputs than outputs: case #4:
max=1, UTxO=[100], Output=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] --> Right [100] [✔]
UTxO balance not sufficient: case #1:
max=100, UTxO=[12,10,17], Output=[40] --> Left (InputValueInsufficient (InputValueInsufficientError {inputValueAvailable = Coin 39, inputValueRequired = Coin 40})) [✔]
UTxO balance not sufficient: case #2:
max=100, UTxO=[12,10,17], Output=[40,1,1,1] --> Left (InputValueInsufficient (InputValueInsufficientError {inputValueAvailable = Coin 39, inputValueRequired = Coin 43})) [✔]
UTxO balance sufficient, but maximum input count exceeded:
max=9, UTxO=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1], Output=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] --> Left (InputLimitExceeded (InputLimitExceededError {calculatedInputLimit = 9})) [✔]
Coin selection: largest-first algorithm: properties
forall (UTxO, NonEmpty TxOut), for all selected input, there's no bigger input in the UTxO that is not already in the selected inputs [✔]
+++ OK, passed 100 tests; 1 discarded.
The algorithm selects just enough inputs and no more. [✔]
+++ OK, passed 10000 tests; 81 discarded.
The algorithm produces the correct set of change. [✘]
Cardano.CoinSelection.Algorithm.Migration
idealBatchSize
Eventually converge for decreasing functions [✔]
+++ OK, passed 100 tests:
47% BatchSize 42
27% BatchSize 32768
26% BatchSize 21845
accuracy of selectCoins
dust=1% [✔]
+++ OK, passed 1000 tests:
89.9% MEDIOCRE (<= 99%)
9.8% PERFECT (== 100%)
0.3% OKAY (> 99%)
dust=5% [✔]
+++ OK, passed 1000 tests:
72.5% PERFECT (== 100%)
23.1% MEDIOCRE (<= 99%)
4.4% OKAY (> 99%)
dust=10% [✔]
+++ OK, passed 1000 tests:
89.5% PERFECT (== 100%)
6.6% MEDIOCRE (<= 99%)
3.9% OKAY (> 99%)
dust=25% [✔]
+++ OK, passed 1000 tests:
96.6% PERFECT (== 100%)
2.2% OKAY (> 99%)
1.2% MEDIOCRE (<= 99%)
dust=50% [✔]
+++ OK, passed 1000 tests:
98.6% PERFECT (== 100%)
1.1% OKAY (> 99%)
0.3% MEDIOCRE (<= 99%)
selectCoins properties
No coin selection has outputs [✔]
+++ OK, passed 10000 tests.
Every coin in the selection change > dust threshold [✔]
+++ OK, passed 10000 tests.
Total input UTxO value >= sum of selection change coins [✔]
+++ OK, passed 10000 tests.
Every selection input is unique [✔]
+++ OK, passed 10000 tests.
Every selection input is a member of the UTxO [✔]
+++ OK, passed 10000 tests.
Every coin selection is well-balanced [✔]
+++ OK, passed 10000 tests.
selectCoins regressions
regression #1 [✔]
+++ OK, passed 1 test.
Cardano.CoinSelection.Algorithm.RandomImprove
Coin selection : random algorithm unit tests
Cardano.CoinSelectionSpec[355:5] [✔]
Cardano.CoinSelectionSpec[355:5] [✔]
Cardano.CoinSelectionSpec[355:5] [✔]
Cardano.CoinSelectionSpec[355:5] [✔]
Cardano.CoinSelectionSpec[355:5] [✔]
Cardano.CoinSelectionSpec[355:5] [✔]
cannot cover aim, but only min:
max=4, UTxO=[1,1,1,1,1,1], Output=[3] --> Right [1,1,1,1] [✔]
REG CO-450: no fallback:
max=4, UTxO=[1000000,1000000,1000000,1000000], Output=[2000000,500000] --> Right [1000000,1000000,1000000,1000000] [✔]
enough funds, proper fragmentation, inputs depleted:
max=100, UTxO=[10,10,10,10], Output=[38,1] --> Left (InputsExhausted InputsExhaustedError) [✔]
Cardano.CoinSelectionSpec[355:5] [✔]
each output needs <maxNumOfInputs:
max=9, UTxO=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1], Output=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] --> Left (InputLimitExceeded (InputLimitExceededError {calculatedInputLimit = 9})) [✔]
each output needs >maxNumInputs:
max=9, UTxO=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1], Output=[10,10,10,10,10,10,10,10,10,10] --> Left (InputLimitExceeded (InputLimitExceededError {calculatedInputLimit = 9})) [✔]
Cardano.CoinSelectionSpec[355:5] [✔]
Cardano.CoinSelectionSpec[355:5] [✔]
Cardano.CoinSelectionSpec[355:5] [✔]
Coin selection properties : random algorithm
forall (UTxO, NonEmpty TxOut), running algorithm gives not less UTxO fragmentation than LargestFirst algorithm [✔]
+++ OK, passed 100 tests; 2 discarded.
forall (UTxO, NonEmpty TxOut), running algorithm gives the same errors as LargestFirst algorithm [✔]
+++ OK, passed 100 tests.
Cardano.CoinSelection.Fee
Fee calculation : unit tests
CoinSelection (inps=[20]outs=[17]chngs=[3]), UTxO=[]), fee=3 --> Right (FeeOutput {csInps = [20], csOuts = [17], csChngs = []}) [✔]
CoinSelection (inps=[20,20]outs=[16,18]chngs=[4,2]), UTxO=[]), fee=6 --> Right (FeeOutput {csInps = [20,20], csOuts = [16,18], csChngs = []}) [✔]
CoinSelection (inps=[20,20]outs=[18,18]chngs=[2,2]), UTxO=[]), fee=2 --> Right (FeeOutput {csInps = [20,20], csOuts = [18,18], csChngs = [1,1]}) [✔]
CoinSelection (inps=[20,20]outs=[17,18]chngs=[3,2]), UTxO=[]), fee=2 --> Right (FeeOutput {csInps = [20,20], csOuts = [17,18], csChngs = [2,1]}) [✔]
CoinSelection (inps=[20,20,20]outs=[14,18,19]chngs=[6,2,1]), UTxO=[]), fee=3 --> Right (FeeOutput {csInps = [20,20,20], csOuts = [14,18,19], csChngs = [4,1,1]}) [✔]
CoinSelection (inps=[20,20,20]outs=[14,18,19]chngs=[6,2,1]), UTxO=[]), fee=3 --> Right (FeeOutput {csInps = [20,20,20], csOuts = [14,18,19], csChngs = [6]}) [✔]
CoinSelection (inps=[20]outs=[17]chngs=[3]), UTxO=[]), fee=4 --> Left (CannotCoverFee (Fee (Coin 1))) [✔]
CoinSelection (inps=[10]outs=[7]chngs=[3]), UTxO=[1]), fee=5 --> Left (CannotCoverFee (Fee (Coin 1))) [✔]
CoinSelection (inps=[10]outs=[7]chngs=[3]), UTxO=[1,1]), fee=5 --> Right (FeeOutput {csInps = [10,1,1], csOuts = [7], csChngs = []}) [✔]
CoinSelection (inps=[10]outs=[7]chngs=[3]), UTxO=[3]), fee=5 --> Right (FeeOutput {csInps = [10,3], csOuts = [7], csChngs = [1]}) [✔]
CoinSelection (inps=[10,10]outs=[7,7]chngs=[3,3]), UTxO=[2,2]), fee=10 --> Right (FeeOutput {csInps = [10,10,2,2], csOuts = [7,7], csChngs = []}) [✔]
CoinSelection (inps=[10,10]outs=[7,7]chngs=[3,3]), UTxO=[3,3]), fee=10 --> Right (FeeOutput {csInps = [10,10,3,3], csOuts = [7,7], csChngs = [1,1]}) [✔]
CoinSelection (inps=[20,20]outs=[16,18]chngs=[4,2]), UTxO=[]), fee=6 --> Right (FeeOutput {csInps = [20,20], csOuts = [16,18], csChngs = []}) [✔]
CoinSelection (inps=[1]outs=[1]chngs=[]), UTxO=[2]), fee=1 --> Right (FeeOutput {csInps = [1,2], csOuts = [1], csChngs = [1]}) [✔]
CoinSelection (inps=[]outs=[]chngs=[]), UTxO=[3]), fee=3 --> Right (FeeOutput {csInps = [3], csOuts = [], csChngs = []}) [✔]
CoinSelection (inps=[]outs=[]chngs=[]), UTxO=[2,2]), fee=3 --> Right (FeeOutput {csInps = [2,2], csOuts = [], csChngs = [1]}) [✔]
CoinSelection (inps=[]outs=[]chngs=[]), UTxO=[2,2]), fee=3 --> Right (FeeOutput {csInps = [2,2], csOuts = [], csChngs = [1]}) [✔]
Fee Calculation: Generators
Arbitrary CoinSelection [✔]
+++ OK, passed 100 tests.
Fee Adjustment properties
Fee adjustment is deterministic when there's no extra inputs [✔]
+++ OK, passed 100 tests.
Adjusting for fee (/= 0) reduces the change outputs or increase inputs [✔]
+++ OK, passed 100 tests; 10 discarded.
distributeFee
fee portions are all within unity of ideal unrounded portions [✔]
+++ OK, passed 100 tests.
fee portions are allocated optimally [✔]
+++ OK, passed 100 tests.
Σ fst (distributeFee fee outs) == fee [✔]
+++ OK, passed 3200 tests.
properties (6400 in total):
50.00% fee > 0
40.55% nOuts=2+
4.88% nOuts=1
4.58% nOuts=2
snd (distributeFee fee outs) == outs [✔]
+++ OK, passed 3200 tests.
properties (6400 in total):
50.00% fee > 0
40.55% nOuts=2+
4.88% nOuts=1
4.58% nOuts=2
expectFailure: not (any null (fst <$> distributeFee fee outs)) [✔]
+++ OK, failed as expected. Falsified (after 1264 tests and 49 shrinks):
(Fee (Coin 1),Coin 1 :| [Coin 1])
coalesceDust
sum coins = sum (coalesceDust threshold coins) [✔]
+++ OK, passed 12800 tests:
91.016% sum coins ≠ 0
8.984% sum coins = 0
all (/= Coin 0) (coalesceDust threshold coins) [✔]
+++ OK, passed 12800 tests:
91.141% ∃ coin ∈ coins . coin = 0
8.984% ∀ coin ∈ coins . coin = 0
8.859% ∀ coin ∈ coins . coin > 0
leaves at most one dust coin [✔]
+++ OK, passed 12800 tests:
52.805% length result ≥ 2
38.211% length result = 1
26.687% ∀ coin ∈ coins . coin ≠ threshold
13.891% have mixture of coin values in relation to threshold
8.984% length result = 0
8.906% ∀ coin ∈ coins . coin = threshold
7.953% ∀ coin ∈ coins . coin < threshold
3.180% ∀ coin ∈ coins . coin > threshold
length coins >= (coalesceDust threshold coins) [✔]
+++ OK, passed 100 tests.
reduceChangeOutputs
data coverage is adequate [✔]
+++ OK, passed 400 tests:
100.0% fee >= 0
51.5% several non-empty coins
30.8% fee = 0
23.5% 0 < fee < sum coins
21.8% fee > sum coins
21.2% fee = sum coins
21.2% two non-empty coins
15.5% one non-empty coin
the fee balancing algorithm converges for any coin selection [✔]
+++ OK, passed 100000 tests.
splitCoin
data coverage is adequate [✔]
+++ OK, passed 200 tests:
73.0% coin to split is non-zero
54.0% list of coins has at least one non-zero coin
42.5% list of coins has at least one zero coin
37.0% list of coins has multiple entries
33.5% coin to split is smaller than number of coins to increase
33.5% list of coins is empty
29.5% list of coins is singleton
27.0% coin to split is zero
preserves the total sum [✔]
+++ OK, passed 100 tests.
results are all within unity of ideal unrounded results [✔]
+++ OK, passed 100 tests.
Cardano.CoinSelection.Types
Lemma 2.1 - Properties of UTxO operations
2.1.1) ins⊲ u ⊆ u [✔]
+++ OK, passed 100 tests (78% dom u ⋂ ins ≠ ∅).
2.1.2) ins⋪ u ⊆ u [✔]
+++ OK, passed 100 tests (78% dom u ⋂ ins ≠ ∅).
2.1.3) u ⊳ outs ⊆ u [✔]
+++ OK, passed 100 tests (81% u ⋂ outs ≠ ∅).
2.1.4) ins⊲ (u ⋃ v) = (ins⊲ u) ⋃ (ins⊲ v) [✔]
+++ OK, passed 100 tests (92% (dom u ⋃ dom v) ⋂ ins ≠ ∅).
2.1.5) ins⋪ (u ⋃ v) = (ins⋪ u) ⋃ (ins⋪ v) [✔]
+++ OK, passed 100 tests (92% (dom u ⋃ dom v) ⋂ ins ≠ ∅).
2.1.6) (dom u ⋂ ins) ⊲ u = ins⊲ u [✔]
+++ OK, passed 100 tests (78% dom u ⋂ ins ≠ ∅).
2.1.7) (dom u ⋂ ins) ⋪ u = ins⋪ u [✔]
+++ OK, passed 100 tests (78% dom u ⋂ ins ≠ ∅).
2.1.8) (dom u ⋃ ins) ⋪ (u ⋃ v) = (ins ⋃ dom u) ⋪ v [✔]
+++ OK, passed 100 tests (78% dom u ⋂ ins ≠ ∅).
2.1.9) ins⋪ u = (dom u \ ins)⊲ u [✔]
+++ OK, passed 100 tests (78% dom u ⋂ ins ≠ ∅).
Lemma 2.6 - Properties of balance
2.6.1) dom u ⋂ dom v ==> balance (u ⋃ v) = balance u + balance v [✔]
+++ OK, passed 200 tests (67.0% u ≠ ∅ , v ≠ ∅).
2.6.2) balance (ins⋪ u) = balance u - balance (ins⊲ u) [✔]
+++ OK, passed 100 tests (78% dom u ⋂ ins ≠ ∅).
Internal.Coin
Coin properties
Only construction of non-negative values is possible. [✔]
+++ OK, passed 3200 tests:
50.03% input is negative
46.53% input is positive
3.44% input is zero
Coverage of generated values is acceptable. [✔]
+++ OK, passed 100 tests:
45% value is more than one
28% value is zero
27% value is one
Addition [✔]
+++ OK, passed 100 tests.
Multiplication [✔]
+++ OK, passed 6400 tests:
48.64% scaling factor is positive
48.20% scaling factor is negative
3.16% scaling factor is zero
Subtraction [✔]
+++ OK, passed 100 tests:
50% x > y
29% x < y
21% values are equal
Division [✔]
+++ OK, passed 6400 tests:
48.64% denominator is positive
48.20% denominator is negative
3.16% denominator is zero
Modulus [✔]
+++ OK, passed 6400 tests:
48.64% denominator is positive
48.20% denominator is negative
3.16% denominator is zero
Distance [✔]
+++ OK, passed 100 tests:
50% x > y
29% x < y
21% values are equal
Test.Vector.Shuffle
shuffle
every list can be shuffled, ultimately [✔]
+++ OK, passed 100 tests (91% shuffled).
shuffle is non-deterministic [✔]
+++ OK, passed 100 tests (95% not deterministic).
sort (shuffle xs) == sort xs [✔]
+++ OK, passed 100 tests (98% non-empty).
shuffleNonEmpty
every non-empty list can be shuffled, ultimately [✔]
+++ OK, passed 100 tests (91% shuffled).
shuffleNonEmpty is non-deterministic [✔]
+++ OK, passed 100 tests (92% not deterministic).
sort (shuffleNonEmpty xs) == sort xs [✔]
+++ OK, passed 100 tests (100% non-empty).
shuffleWith / mkSeed
shuffling with the same seed is deterministic [✔]
+++ OK, passed 100 tests (98% non singleton).
different seed means different shuffles [✔]
+++ OK, passed 200 tests; 23 discarded:
89.5% different
66.0% big list
29.0% small list
5.0% singleton
Failures:
src/test/Cardano/CoinSelection/Algorithm/LargestFirstSpec.hs:274:9:
1) Cardano.CoinSelection.Algorithm.LargestFirst, Coin selection: largest-first algorithm: properties, The algorithm produces the correct set of change.
*** Gave up! Passed only 51199 tests; 416 discarded tests:
98.742% amountSelected > amountRequired
1.258% amountSelected = amountRequired
To rerun use: --match "/Cardano.CoinSelection.Algorithm.LargestFirst/Coin selection: largest-first algorithm: properties/The algorithm produces the correct set of change./"
Randomized with seed 624635623
Finished in 43.6456 seconds
121 examples, 1 failure
