mirror of
https://github.com/QuilibriumNetwork/ceremonyclient.git
synced 2026-02-21 18:37:26 +08:00
dbd95bd9e9
* v2.1.0 [omit consensus and adjacent] - this commit will be amended with the full release after the file copy is complete * 2.1.0 main node rollup
583 lines
16 KiB
Go
583 lines
16 KiB
Go
package compute
|
|
|
|
import (
|
|
"testing"
|
|
|
|
"github.com/stretchr/testify/assert"
|
|
"github.com/stretchr/testify/mock"
|
|
"github.com/stretchr/testify/require"
|
|
"source.quilibrium.com/quilibrium/monorepo/types/mocks"
|
|
)
|
|
|
|
func TestExecutionDAG_BasicConstruction(t *testing.T) {
|
|
// Test basic DAG construction with no dependencies
|
|
t.Run("NoDependencies", func(t *testing.T) {
|
|
codeExecute := &CodeExecute{
|
|
Domain: [32]byte{1, 2, 3},
|
|
Rendezvous: [32]byte{4, 5, 6},
|
|
ExecuteOperations: []*ExecuteOperation{
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app1"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("op1"),
|
|
Dependencies: [][]byte{},
|
|
},
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app2"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("op2"),
|
|
Dependencies: [][]byte{},
|
|
},
|
|
},
|
|
}
|
|
|
|
// Set up mock dependencies
|
|
mockHypergraph := &mocks.MockHypergraph{}
|
|
mockHypergraph.On("GetVertexData", mock.Anything).Return(nil, nil)
|
|
codeExecute.hypergraph = mockHypergraph
|
|
|
|
dag, err := codeExecute.buildExecutionDAG()
|
|
require.NoError(t, err)
|
|
require.NotNil(t, dag)
|
|
|
|
// Both operations should be in stage 0
|
|
assert.Len(t, dag.Stages, 1)
|
|
assert.Len(t, dag.Stages[0], 2)
|
|
assert.Contains(t, dag.Stages[0], "op1")
|
|
assert.Contains(t, dag.Stages[0], "op2")
|
|
})
|
|
|
|
// Test linear dependency chain
|
|
t.Run("LinearDependencies", func(t *testing.T) {
|
|
codeExecute := &CodeExecute{
|
|
Domain: [32]byte{1, 2, 3},
|
|
Rendezvous: [32]byte{4, 5, 6},
|
|
ExecuteOperations: []*ExecuteOperation{
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app1"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("op1"),
|
|
Dependencies: [][]byte{},
|
|
},
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app2"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("op2"),
|
|
Dependencies: [][]byte{[]byte("op1")},
|
|
},
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app3"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("op3"),
|
|
Dependencies: [][]byte{[]byte("op2")},
|
|
},
|
|
},
|
|
}
|
|
|
|
mockHypergraph := &mocks.MockHypergraph{}
|
|
mockHypergraph.On("GetVertexData", mock.Anything).Return(nil, nil)
|
|
codeExecute.hypergraph = mockHypergraph
|
|
|
|
dag, err := codeExecute.buildExecutionDAG()
|
|
require.NoError(t, err)
|
|
require.NotNil(t, dag)
|
|
|
|
// Should have 3 stages
|
|
assert.Len(t, dag.Stages, 3)
|
|
assert.Equal(t, []string{"op1"}, dag.Stages[0])
|
|
assert.Equal(t, []string{"op2"}, dag.Stages[1])
|
|
assert.Equal(t, []string{"op3"}, dag.Stages[2])
|
|
})
|
|
|
|
// Test diamond dependency pattern
|
|
t.Run("DiamondDependencies", func(t *testing.T) {
|
|
codeExecute := &CodeExecute{
|
|
Domain: [32]byte{1, 2, 3},
|
|
Rendezvous: [32]byte{4, 5, 6},
|
|
ExecuteOperations: []*ExecuteOperation{
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app1"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("op1"),
|
|
Dependencies: [][]byte{},
|
|
},
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app2"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("op2"),
|
|
Dependencies: [][]byte{[]byte("op1")},
|
|
},
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app3"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("op3"),
|
|
Dependencies: [][]byte{[]byte("op1")},
|
|
},
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app4"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("op4"),
|
|
Dependencies: [][]byte{[]byte("op2"), []byte("op3")},
|
|
},
|
|
},
|
|
}
|
|
|
|
mockHypergraph := &mocks.MockHypergraph{}
|
|
mockHypergraph.On("GetVertexData", mock.Anything).Return(nil, nil)
|
|
codeExecute.hypergraph = mockHypergraph
|
|
|
|
dag, err := codeExecute.buildExecutionDAG()
|
|
require.NoError(t, err)
|
|
require.NotNil(t, dag)
|
|
|
|
// Should have 3 stages
|
|
assert.Len(t, dag.Stages, 3)
|
|
assert.Equal(t, []string{"op1"}, dag.Stages[0])
|
|
// op2 and op3 can execute in parallel
|
|
assert.Len(t, dag.Stages[1], 2)
|
|
assert.Contains(t, dag.Stages[1], "op2")
|
|
assert.Contains(t, dag.Stages[1], "op3")
|
|
assert.Equal(t, []string{"op4"}, dag.Stages[2])
|
|
})
|
|
}
|
|
|
|
func TestExecutionDAG_CycleDetection(t *testing.T) {
|
|
// Test direct cycle
|
|
t.Run("DirectCycle", func(t *testing.T) {
|
|
codeExecute := &CodeExecute{
|
|
Domain: [32]byte{1, 2, 3},
|
|
Rendezvous: [32]byte{4, 5, 6},
|
|
ExecuteOperations: []*ExecuteOperation{
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app1"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("op1"),
|
|
Dependencies: [][]byte{[]byte("op2")},
|
|
},
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app2"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("op2"),
|
|
Dependencies: [][]byte{[]byte("op1")},
|
|
},
|
|
},
|
|
}
|
|
|
|
mockHypergraph := &mocks.MockHypergraph{}
|
|
codeExecute.hypergraph = mockHypergraph
|
|
|
|
dag, err := codeExecute.buildExecutionDAG()
|
|
assert.Error(t, err)
|
|
assert.Contains(t, err.Error(), "cycle detected")
|
|
assert.Nil(t, dag)
|
|
})
|
|
|
|
// Test indirect cycle
|
|
t.Run("IndirectCycle", func(t *testing.T) {
|
|
codeExecute := &CodeExecute{
|
|
Domain: [32]byte{1, 2, 3},
|
|
Rendezvous: [32]byte{4, 5, 6},
|
|
ExecuteOperations: []*ExecuteOperation{
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app1"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("op1"),
|
|
Dependencies: [][]byte{[]byte("op3")},
|
|
},
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app2"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("op2"),
|
|
Dependencies: [][]byte{[]byte("op1")},
|
|
},
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app3"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("op3"),
|
|
Dependencies: [][]byte{[]byte("op2")},
|
|
},
|
|
},
|
|
}
|
|
|
|
mockHypergraph := &mocks.MockHypergraph{}
|
|
codeExecute.hypergraph = mockHypergraph
|
|
|
|
dag, err := codeExecute.buildExecutionDAG()
|
|
assert.Error(t, err)
|
|
assert.Contains(t, err.Error(), "cycle detected")
|
|
assert.Nil(t, dag)
|
|
})
|
|
}
|
|
|
|
func TestExecutionDAG_DisconnectedGraph(t *testing.T) {
|
|
// Test disconnected graph - this is the case that causes the error in the failing test
|
|
t.Run("DisconnectedComponents", func(t *testing.T) {
|
|
codeExecute := &CodeExecute{
|
|
Domain: [32]byte{1, 2, 3},
|
|
Rendezvous: [32]byte{4, 5, 6},
|
|
ExecuteOperations: []*ExecuteOperation{
|
|
// First component
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app1"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("op1"),
|
|
Dependencies: [][]byte{},
|
|
},
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app2"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("op2"),
|
|
Dependencies: [][]byte{[]byte("op1")},
|
|
},
|
|
// Second component - disconnected
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app3"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("op3"),
|
|
Dependencies: [][]byte{[]byte("op4")},
|
|
},
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app4"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("op4"),
|
|
Dependencies: [][]byte{[]byte("op5")},
|
|
},
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app5"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("op5"),
|
|
Dependencies: [][]byte{},
|
|
},
|
|
},
|
|
}
|
|
|
|
mockHypergraph := &mocks.MockHypergraph{}
|
|
mockHypergraph.On("GetVertexData", mock.Anything).Return(nil, nil)
|
|
codeExecute.hypergraph = mockHypergraph
|
|
|
|
// This should actually succeed - disconnected components are valid
|
|
// They just need to be scheduled properly
|
|
dag, err := codeExecute.buildExecutionDAG()
|
|
require.NoError(t, err)
|
|
require.NotNil(t, dag)
|
|
|
|
// Should have proper stages for both components
|
|
assert.Len(t, dag.Operations, 5)
|
|
|
|
// Verify both components are scheduled
|
|
processedOps := make(map[string]bool)
|
|
for _, stage := range dag.Stages {
|
|
for _, opID := range stage {
|
|
processedOps[opID] = true
|
|
}
|
|
}
|
|
assert.Len(t, processedOps, 5)
|
|
})
|
|
}
|
|
|
|
func TestExecutionDAG_ErrorCases(t *testing.T) {
|
|
// Test duplicate operation identifiers
|
|
t.Run("DuplicateIdentifiers", func(t *testing.T) {
|
|
codeExecute := &CodeExecute{
|
|
Domain: [32]byte{1, 2, 3},
|
|
Rendezvous: [32]byte{4, 5, 6},
|
|
ExecuteOperations: []*ExecuteOperation{
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app1"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("op1"),
|
|
Dependencies: [][]byte{},
|
|
},
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app2"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("op1"), // Duplicate!
|
|
Dependencies: [][]byte{},
|
|
},
|
|
},
|
|
}
|
|
|
|
mockHypergraph := &mocks.MockHypergraph{}
|
|
codeExecute.hypergraph = mockHypergraph
|
|
|
|
dag, err := codeExecute.buildExecutionDAG()
|
|
assert.Error(t, err)
|
|
assert.Contains(t, err.Error(), "duplicate operation identifier")
|
|
assert.Nil(t, dag)
|
|
})
|
|
|
|
// Test dependency on non-existent operation
|
|
t.Run("NonExistentDependency", func(t *testing.T) {
|
|
codeExecute := &CodeExecute{
|
|
Domain: [32]byte{1, 2, 3},
|
|
Rendezvous: [32]byte{4, 5, 6},
|
|
ExecuteOperations: []*ExecuteOperation{
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app1"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("op1"),
|
|
Dependencies: [][]byte{[]byte("op_nonexistent")},
|
|
},
|
|
},
|
|
}
|
|
|
|
mockHypergraph := &mocks.MockHypergraph{}
|
|
codeExecute.hypergraph = mockHypergraph
|
|
|
|
dag, err := codeExecute.buildExecutionDAG()
|
|
assert.Error(t, err)
|
|
assert.Contains(t, err.Error(), "dependency")
|
|
assert.Contains(t, err.Error(), "not found")
|
|
assert.Nil(t, dag)
|
|
})
|
|
}
|
|
|
|
func TestExecutionDAG_ConflictDetection(t *testing.T) {
|
|
// Test read-write conflict detection
|
|
t.Run("ReadWriteConflict", func(t *testing.T) {
|
|
t.Skip("With multiphasic locking, implement this test")
|
|
})
|
|
|
|
// Test operations on different addresses can run in parallel
|
|
t.Run("NoConflictParallel", func(t *testing.T) {
|
|
codeExecute := &CodeExecute{
|
|
Domain: [32]byte{1, 2, 3},
|
|
Rendezvous: [32]byte{4, 5, 6},
|
|
ExecuteOperations: []*ExecuteOperation{
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app1"),
|
|
ExecutionContext: ExecutionContextIntrinsic,
|
|
},
|
|
Identifier: []byte("op1"),
|
|
Dependencies: [][]byte{},
|
|
},
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app2"), // Different address - no conflict
|
|
ExecutionContext: ExecutionContextIntrinsic,
|
|
},
|
|
Identifier: []byte("op2"),
|
|
Dependencies: [][]byte{},
|
|
},
|
|
},
|
|
}
|
|
|
|
mockHypergraph := &mocks.MockHypergraph{}
|
|
mockHypergraph.On("GetVertexData", mock.Anything).Return(nil, nil)
|
|
codeExecute.hypergraph = mockHypergraph
|
|
|
|
dag, err := codeExecute.buildExecutionDAG()
|
|
require.NoError(t, err)
|
|
require.NotNil(t, dag)
|
|
|
|
// Operations without conflicts can run in parallel
|
|
assert.Len(t, dag.Stages, 1)
|
|
assert.Len(t, dag.Stages[0], 2)
|
|
})
|
|
}
|
|
|
|
func TestExecutionDAG_ComplexScenarios(t *testing.T) {
|
|
// Test multiple independent chains that should run in parallel
|
|
t.Run("MultipleIndependentChains", func(t *testing.T) {
|
|
codeExecute := &CodeExecute{
|
|
Domain: [32]byte{1, 2, 3},
|
|
Rendezvous: [32]byte{4, 5, 6},
|
|
ExecuteOperations: []*ExecuteOperation{
|
|
// Chain 1
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app1"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("chain1_op1"),
|
|
Dependencies: [][]byte{},
|
|
},
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app1"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("chain1_op2"),
|
|
Dependencies: [][]byte{[]byte("chain1_op1")},
|
|
},
|
|
// Chain 2
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app2"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("chain2_op1"),
|
|
Dependencies: [][]byte{},
|
|
},
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app2"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("chain2_op2"),
|
|
Dependencies: [][]byte{[]byte("chain2_op1")},
|
|
},
|
|
// Merge point
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app3"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("merge_op"),
|
|
Dependencies: [][]byte{[]byte("chain1_op2"), []byte("chain2_op2")},
|
|
},
|
|
},
|
|
}
|
|
|
|
mockHypergraph := &mocks.MockHypergraph{}
|
|
mockHypergraph.On("GetVertexData", mock.Anything).Return(nil, nil)
|
|
codeExecute.hypergraph = mockHypergraph
|
|
|
|
dag, err := codeExecute.buildExecutionDAG()
|
|
require.NoError(t, err)
|
|
require.NotNil(t, dag)
|
|
|
|
// Should have 3 stages
|
|
assert.Len(t, dag.Stages, 3)
|
|
// First stage: both chain starts
|
|
assert.Len(t, dag.Stages[0], 2)
|
|
// Second stage: both chain continuations
|
|
assert.Len(t, dag.Stages[1], 2)
|
|
// Third stage: merge
|
|
assert.Len(t, dag.Stages[2], 1)
|
|
})
|
|
}
|
|
|
|
// Test to reproduce the issue from compute_execution_engine_test.go
|
|
func TestExecutionDAG_SequentialDependenciesIssue(t *testing.T) {
|
|
// This test reproduces the "not all operations were processed - possible disconnected graph" error
|
|
t.Run("AllOperationsHaveDependencies", func(t *testing.T) {
|
|
// When all operations have dependencies and none have zero dependencies,
|
|
// the current algorithm fails to process any operations
|
|
codeExecute := &CodeExecute{
|
|
Domain: [32]byte{1, 2, 3},
|
|
Rendezvous: [32]byte{4, 5, 6},
|
|
ExecuteOperations: []*ExecuteOperation{
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app1"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("op1"),
|
|
Dependencies: [][]byte{[]byte("external_op")}, // Depends on something not in the list
|
|
},
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app2"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("op2"),
|
|
Dependencies: [][]byte{[]byte("op1")},
|
|
},
|
|
},
|
|
}
|
|
|
|
mockHypergraph := &mocks.MockHypergraph{}
|
|
codeExecute.hypergraph = mockHypergraph
|
|
|
|
dag, err := codeExecute.buildExecutionDAG()
|
|
assert.Error(t, err)
|
|
assert.Contains(t, err.Error(), "dependency") // Should fail with dependency not found
|
|
assert.Nil(t, dag)
|
|
})
|
|
|
|
// Test the fix: operations should be able to depend on external operations
|
|
// that were executed in a previous transaction
|
|
t.Run("ExternalDependenciesHandled", func(t *testing.T) {
|
|
// The algorithm should handle operations that depend on external operations
|
|
// by treating them as having their dependencies already satisfied
|
|
codeExecute := &CodeExecute{
|
|
Domain: [32]byte{1, 2, 3},
|
|
Rendezvous: [32]byte{4, 5, 6},
|
|
ExecuteOperations: []*ExecuteOperation{
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app1"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("op1"),
|
|
Dependencies: [][]byte{}, // No dependencies within this batch
|
|
},
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app2"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("op2"),
|
|
Dependencies: [][]byte{[]byte("op1")},
|
|
},
|
|
{
|
|
Application: Application{
|
|
Address: []byte("app3"),
|
|
ExecutionContext: ExecutionContextExtrinsic,
|
|
},
|
|
Identifier: []byte("op3"),
|
|
Dependencies: [][]byte{[]byte("op2")},
|
|
},
|
|
},
|
|
}
|
|
|
|
mockHypergraph := &mocks.MockHypergraph{}
|
|
mockHypergraph.On("GetVertexData", mock.Anything).Return(nil, nil)
|
|
codeExecute.hypergraph = mockHypergraph
|
|
|
|
dag, err := codeExecute.buildExecutionDAG()
|
|
require.NoError(t, err)
|
|
require.NotNil(t, dag)
|
|
|
|
// All operations should be scheduled
|
|
assert.Len(t, dag.Operations, 3)
|
|
assert.Len(t, dag.Stages, 3)
|
|
})
|
|
}
|