Test for async traversal of dependency graph
Includes some refactorings driven by this test intended to make interrogating
the graph a bit easier, but this could use further improvements, seems like
there are missing abstractions.
MODIFY
WalletWasabi.Tests/UnitTests/WabiSabi/Client/CredentialDependencyTests.cs
WalletWasabi.Tests/UnitTests/WabiSabi/Client/CredentialDependencyTests.cs
using System;
using System.Collections.Generic;
+using System.Collections.Immutable;
using System.Linq;
+using System.Threading;
+using System.Threading.Tasks;
using WalletWasabi.WabiSabi.Client.CredentialDependencies;
using Xunit;
@@ -8,6 +11,115 @@ namespace WalletWasabi.Tests.UnitTests.WabiSabi.Client
{
public class CredentialDependencyTests
{
+ [Fact]
+ public async void AsyncDependencyGraphTraversal()
+ {
+ var g = DependencyGraph.ResolveCredentialDependencies(
+ inputValues: new[] { new ulong[] { 10000, 1930 }, new ulong[] { 1000, 1930 } },
+ outputValues: new[] { new ulong[] { 5000, 31 }, new ulong[] { 3500, 31 }, new ulong[] { 2500, 31 } });
+
+ await SimulateAsyncRequests(g);
+ }
+
+ // Demonstrate how to use the dependency grap. Also checks it can be
+ // executed with no deadlocks.
+ private async Task SimulateAsyncRequests(DependencyGraph g)
+ {
+ // Keep track of the partial sets credentials to present. Requests
+ // that are keys in this dictionary are still waiting to be sent.
+ var pendingCredentialsToPresent = g.Vertices.ToDictionary(v => v, _ => DependencyGraph.CredentialTypes.ToDictionary(t => t, _ => new List<ulong>()));
+
+ // A waiting request is blocked if either set of credentials that
+ // need to be presented is incomplete. Since input registrations and
+ // connection confirmation are modeled as a single node with in
+ // degree 0, they are never blocked.
+ ImmutableArray<RequestNode> unblockedRequests() => pendingCredentialsToPresent.Keys.Where(node => DependencyGraph.CredentialTypes.All(t => g.InDegree(node, t) == pendingCredentialsToPresent[node][t].Count)).ToImmutableArray();
+
+ // Also keep track of the in-flight requests
+ var inFlightRequests = new List<(Task<ImmutableSortedDictionary<CredentialType, IEnumerable<ulong>>> Task, ImmutableSortedDictionary<CredentialType, IEnumerable<CredentialDependency>> Dependencies)>();
+
+ // And all sent requests, for testing purposes.
+ var sent = new HashSet<RequestNode>();
+
+ var rng = new Random();
+
+ // Simulate sending a request. Instead of actual Credential objects,
+ // credentials are just represented as ulongs.
+ async Task<ImmutableSortedDictionary<CredentialType, IEnumerable<ulong>>> SimulateRequest(
+ RequestNode node,
+ ImmutableSortedDictionary<CredentialType, IEnumerable<ulong>> presented,
+ ImmutableSortedDictionary<CredentialType, IEnumerable<ulong>> requested)
+ {
+ foreach (var credentialType in presented.Keys)
+ {
+ Assert.Equal(g.InEdges(node, credentialType).Select(e => e.Value).OrderBy(x => x), presented[credentialType].OrderBy(x => x));
+ Assert.Equal(g.OutEdges(node, credentialType).Select(e => e.Value).OrderBy(x => x), requested[credentialType].OrderBy(x => x));
+ }
+
+ Assert.DoesNotContain(node, sent);
+ sent.Add(node);
+
+ await Task.Delay(1 + rng.Next(10));
+
+ return requested;
+ }
+
+ var ct = new CancellationTokenSource(40_000);
+
+ for (var remainingSteps = 2 * pendingCredentialsToPresent.Count; remainingSteps > 0 && pendingCredentialsToPresent.Count + inFlightRequests.Count > 0; remainingSteps--)
+ {
+ // Clear unblocked but waiting requests. Not very efficient
+ // (quadratic complexity), but good enough for demonstration
+ // purposes.
+ foreach (var node in unblockedRequests())
+ {
+ // FIXME this is a little ugly, how should it look in the real code? seems like we're missing an abstraction
+ var edgesByType = DependencyGraph.CredentialTypes.ToImmutableSortedDictionary(t => t, t => g.OutEdges(node, t));
+ var credentialsToRequest = edgesByType.ToImmutableSortedDictionary(kvp => kvp.Key, kvp => kvp.Value.Select(e => e.Value));
+ var credentialsToPresent = pendingCredentialsToPresent[node].ToImmutableSortedDictionary(kvp => kvp.Key, kvp => kvp.Value.AsEnumerable());
+
+ Assert.NotEmpty(edgesByType);
+
+ var task = SimulateRequest(node, credentialsToPresent, credentialsToRequest);
+
+ inFlightRequests.Add((Task: task, Dependencies: edgesByType));
+ Assert.True(pendingCredentialsToPresent.Remove(node));
+ }
+
+ // At this point at least one task must be in progress.
+ Assert.True(inFlightRequests.Count > 0);
+
+ // Wait for a response to arrive
+ var i = Task.WaitAny(inFlightRequests.Select(x => x.Task).ToArray(), ct.Token);
+ Assert.InRange(i, 0, inFlightRequests.Count);
+ var entry = inFlightRequests[i];
+ inFlightRequests.RemoveAt(i);
+
+ var issuedCredentials = await entry.Task;
+
+ // Unblock the requests that depend on the issued credentials from this response
+ foreach ((var credentialType, var edges) in entry.Dependencies)
+ {
+ Assert.Equal(edges.Count(), issuedCredentials[credentialType].Count());
+ foreach ((var credential, var edge) in issuedCredentials[credentialType].Zip(edges))
+ {
+ // Ignore the fact that credential is the same as
+ // edge.Value, it's meant to represent the real thing
+ // since it's returned from the task.
+ Assert.Equal(edge.Value, credential);
+ pendingCredentialsToPresent[edge.To][credentialType].Add(credential);
+ }
+ }
+ }
+
+ Assert.Empty(inFlightRequests);
+ Assert.Empty(pendingCredentialsToPresent);
+
+ Assert.True(g.Vertices.All(v => sent.Contains(v)));
+
+ ct.Dispose();
+ }
+
[Fact]
public void ResolveCredentialDependenciesBasic()
{
@@ -30,9 +142,9 @@ namespace WalletWasabi.Tests.UnitTests.WabiSabi.Client
Assert.Empty(g.OutEdges(small.To, CredentialType.Amount));
Assert.Equal(2, g.InEdges(small.To, CredentialType.Amount).Count());
Assert.Equal(1, g.InEdges(small.To, CredentialType.Amount).Select(e => e.From).Distinct().Count());
- Assert.Empty(g.OutEdges(small.To, CredentialType.VirtualBytes));
- Assert.Equal(2, g.InEdges(small.To, CredentialType.VirtualBytes).Count());
- Assert.Equal(g.Vertices[0], g.InEdges(small.To, CredentialType.VirtualBytes).Select(e => e.From).Distinct().Single());
+ Assert.Empty(g.OutEdges(small.To, CredentialType.Vsize));
+ Assert.Equal(2, g.InEdges(small.To, CredentialType.Vsize).Count());
+ Assert.Equal(g.Vertices[0], g.InEdges(small.To, CredentialType.Vsize).Select(e => e.From).Distinct().Single());
var large = edges.OrderByDescending(e => e.Value).First();
Assert.Equal(2UL, large.Value);
@@ -66,10 +178,10 @@ namespace WalletWasabi.Tests.UnitTests.WabiSabi.Client
Assert.Empty(g.OutEdges(nonZeroEdge.To, CredentialType.Amount));
Assert.Equal(2, g.InEdges(nonZeroEdge.To, CredentialType.Amount).Count());
Assert.Equal(1, g.InEdges(nonZeroEdge.To, CredentialType.Amount).Select(e => e.From).Distinct().Count());
- Assert.Empty(g.OutEdges(nonZeroEdge.To, CredentialType.VirtualBytes));
- Assert.Equal(2, g.InEdges(nonZeroEdge.To, CredentialType.VirtualBytes).Count());
- Assert.Equal(2, g.InEdges(nonZeroEdge.To, CredentialType.VirtualBytes).Select(e => e.Value == 0).Count());
- Assert.Equal(g.Vertices[0], g.InEdges(nonZeroEdge.To, CredentialType.VirtualBytes).Select(e => e.From).Distinct().Single());
+ Assert.Empty(g.OutEdges(nonZeroEdge.To, CredentialType.Vsize));
+ Assert.Equal(2, g.InEdges(nonZeroEdge.To, CredentialType.Vsize).Count());
+ Assert.Equal(2, g.InEdges(nonZeroEdge.To, CredentialType.Vsize).Select(e => e.Value == 0).Count());
+ Assert.Equal(g.Vertices[0], g.InEdges(nonZeroEdge.To, CredentialType.Vsize).Select(e => e.From).Distinct().Single());
AssertResolvedGraphInvariants(g, inputValues, outputValues);
}
@@ -140,7 +252,7 @@ namespace WalletWasabi.Tests.UnitTests.WabiSabi.Client
[InlineData("21,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1", "11,5 10,5 10,5 10,6", 42)]
[InlineData("21,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1", "10,5 10,5 10,5 10,6", 43)]
[InlineData("21,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1 1,1", "10,5 10,5 10,5 10,5", 42)]
- public void ResolveCredentialDependencies(string inputs, string outputs, int finalVertexCount)
+ public async void ResolveCredentialDependencies(string inputs, string outputs, int finalVertexCount)
{
// blackbox tests (apart from finalVertexCount, which leaks
// information about implementation) covering valid range
@@ -159,11 +271,13 @@ namespace WalletWasabi.Tests.UnitTests.WabiSabi.Client
Assert.Equal(finalVertexCount, g.Vertices.Count);
// TODO when sum is even, reverse
+
+ await SimulateAsyncRequests(g);
}
private void AssertResolvedGraphInvariants(DependencyGraph graph, IEnumerable<IEnumerable<ulong>> inputValues, IEnumerable<IEnumerable<ulong>> outputValues)
{
- for (CredentialType credentialType = 0; credentialType < CredentialType.NumTypes; credentialType++)
+ foreach (var credentialType in DependencyGraph.CredentialTypes)
{
// Input nodes
foreach (var node in graph.Vertices.Take(inputValues.Count()))

MODIFY
WalletWasabi/WabiSabi/Client/CredentialDependencies/CredentialType.cs
WalletWasabi/WabiSabi/Client/CredentialDependencies/CredentialType.cs
@@ -3,7 +3,6 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
public enum CredentialType
{
Amount,
- VirtualBytes,
- NumTypes
+ Vsize
}
}

MODIFY
WalletWasabi/WabiSabi/Client/CredentialDependencies/DependencyGraph.cs
WalletWasabi/WabiSabi/Client/CredentialDependencies/DependencyGraph.cs
@@ -9,6 +9,8 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
{
public const int K = ProtocolConstants.CredentialNumber;
+ public static ImmutableArray<CredentialType> CredentialTypes { get; } = ImmutableArray.Create<CredentialType>(CredentialType.Amount, CredentialType.Vsize);
+
public ImmutableList<RequestNode> Vertices { get; private set; } = ImmutableList<RequestNode>.Empty;
public ImmutableList<RequestNode> Inputs { get; private set; } = ImmutableList<RequestNode>.Empty;
@@ -20,7 +22,7 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
// Internal properties used to keep track of effective values and edges
public ImmutableSortedDictionary<CredentialType, CredentialEdgeSet> edgeSets { get; init; } = ImmutableSortedDictionary<CredentialType, CredentialEdgeSet>.Empty
.Add(CredentialType.Amount, new() { CredentialType = CredentialType.Amount })
- .Add(CredentialType.VirtualBytes, new() { CredentialType = CredentialType.VirtualBytes });
+ .Add(CredentialType.Vsize, new() { CredentialType = CredentialType.Vsize });
public long Balance(RequestNode node, CredentialType credentialType) => edgeSets[credentialType].Balance(node);
@@ -46,12 +48,12 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
public static DependencyGraph FromValues(IEnumerable<IEnumerable<ulong>> inputValues, IEnumerable<IEnumerable<ulong>> outputValues)
{
- if (Enumerable.Concat(inputValues, outputValues).Any(x => x.Count() != (int)CredentialType.NumTypes))
+ if (Enumerable.Concat(inputValues, outputValues).Any(x => x.Count() != CredentialTypes.Length))
{
- throw new ArgumentException($"Number of credential values must be {CredentialType.NumTypes}");
+ throw new ArgumentException($"Number of credential values must be {CredentialTypes.Length}");
}
- for (CredentialType credentialType = 0; credentialType < CredentialType.NumTypes; credentialType++)
+ foreach (var credentialType in CredentialTypes)
{
// no Sum(Func<ulong, ulong>)) variant
long credentialValue(IEnumerable<ulong> x) => (long)x.Skip((int)credentialType).First();
@@ -177,8 +179,8 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
/// with non-maximized in-degrees, it can only increase the available
/// out degree for nodes which are not fully consumed.</para></remarks>
private DependencyGraph ResolveCredentials()
- => edgeSets.Keys.Aggregate(
- edgeSets.Keys.Aggregate(this, (g, credentialType) => g.ResolveNegativeBalanceNodes(credentialType)),
+ => CredentialTypes.Aggregate(
+ CredentialTypes.Aggregate(this, (g, credentialType) => g.ResolveNegativeBalanceNodes(credentialType)),
(g, credentialType) => g.ResolveZeroCredentials(credentialType));
private DependencyGraph ResolveNegativeBalanceNodes(CredentialType credentialType)
@@ -189,7 +191,7 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
var negative = g.Vertices.Where(v => edgeSet.Balance(v) < 0);
- if (negative.Count() == 0)
+ if (!negative.Any())
{
return g;
}
@@ -244,7 +246,7 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
IEnumerable<RequestNode> negative = Vertices.Where(v => edgeSet.Balance(v) < 0).OrderBy(v => edgeSet.Balance(v));
- if (negative.Count() == 0)
+ if (!negative.Any())
{
return this;
}
@@ -358,7 +360,7 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
// dependencies between different requests, weight credentials
// should often be easily satisfiable with parallel edges to the
// amount credential edges.
- if (credentialType + 1 < CredentialType.NumTypes)
+ if (CredentialTypes.Contains(credentialType + 1))
{
// TODO Limit up to a certain height in the graph, no more than
// the initial value, this can sometimes create a deeper graph
@@ -394,7 +396,7 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
var edgeSet = edgeSets[credentialType];
var unresolvedNodes = Vertices.Where(v => edgeSet.RemainingInDegree(v) > 0 && edgeSet.AvailableZeroOutDegree(v) > 0).OrderByDescending(v => edgeSet.AvailableZeroOutDegree(v));
- if (unresolvedNodes.Count() == 0)
+ if (!unresolvedNodes.Any())
{
return ResolveZeroCredentialsForTerminalNodes(credentialType); ;
}
@@ -425,7 +427,7 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
var edgeSet = edgeSets[credentialType];
var unresolvedNodes = Vertices.Where(v => edgeSet.RemainingInDegree(v) > 0).OrderByDescending(v => edgeSet.AvailableZeroOutDegree(v));
- if (unresolvedNodes.Count() == 0)
+ if (!unresolvedNodes.Any())
{
return this;
}
@@ -459,19 +461,19 @@ namespace WalletWasabi.WabiSabi.Client.CredentialDependencies
foreach (var v in Vertices)
{
- if (v.InitialBalance(CredentialType.Amount) == 0 && v.InitialBalance(CredentialType.VirtualBytes) == 0)
+ if (v.InitialBalance(CredentialType.Amount) == 0 && v.InitialBalance(CredentialType.Vsize) == 0)
{
output += $" {id(v)} [label=\"\"];\n";
}
else
{
- output += $" {id(v)} [label=\"{v.InitialBalance(CredentialType.Amount)}s {v.InitialBalance(CredentialType.VirtualBytes)}b\"];\n";
+ output += $" {id(v)} [label=\"{v.InitialBalance(CredentialType.Amount)}s {v.InitialBalance(CredentialType.Vsize)}b\"];\n";
}
}
- for (CredentialType credentialType = 0; credentialType < CredentialType.NumTypes; credentialType++)
+ foreach (var credentialType in CredentialTypes)
{
var color = credentialType == 0 ? "blue" : "red";
var unit = credentialType == 0 ? "s" : "b";

Test for async traversal of dependency graph

Includes some refactorings driven by this test intended to make interrogating
the graph a bit easier, but this could use further improvements, seems like
there are missing abstractions.