package cross import ( "errors" "fmt" "strconv" "testing" "github.com/stretchr/testify/require" "github.com/ethereum-optimism/optimism/op-service/eth" "github.com/ethereum-optimism/optimism/op-supervisor/supervisor/types" ) type mockCycleCheckDeps struct { openBlockFn func(chainID types.ChainID, blockNum uint64) (eth.BlockRef, uint32, map[uint32]*types.ExecutingMessage, error) } func (m *mockCycleCheckDeps) OpenBlock(chainID types.ChainID, blockNum uint64) (eth.BlockRef, uint32, map[uint32]*types.ExecutingMessage, error) { return m.openBlockFn(chainID, blockNum) } type chainBlockDef struct { logCount uint32 messages map[uint32]*types.ExecutingMessage error error } type hazardCycleChecksTestCase struct { name string chainBlocks map[string]chainBlockDef expectErr error msg string // Optional overrides hazards map[types.ChainIndex]types.BlockSeal openBlockFn func(chainID types.ChainID, blockNum uint64) (eth.BlockRef, uint32, map[uint32]*types.ExecutingMessage, error) } func runHazardCycleChecksTestCaseGroup(t *testing.T, group string, tests []hazardCycleChecksTestCase) { for _, tc := range tests { t.Run(group+"/"+tc.name, func(t *testing.T) { runHazardCycleChecksTestCase(t, tc) }) } } func runHazardCycleChecksTestCase(t *testing.T, tc hazardCycleChecksTestCase) { // Create mocked dependencies deps := &mockCycleCheckDeps{ openBlockFn: func(chainID types.ChainID, blockNum uint64) (eth.BlockRef, uint32, map[uint32]*types.ExecutingMessage, error) { // Use override if provided if tc.openBlockFn != nil { return tc.openBlockFn(chainID, blockNum) } // Default behavior chainStr := chainID.String() def, ok := tc.chainBlocks[chainStr] if !ok { return eth.BlockRef{}, 0, nil, errors.New("unexpected chain") } if def.error != nil { return eth.BlockRef{}, 0, nil, def.error } return eth.BlockRef{Number: blockNum}, def.logCount, def.messages, nil }, } // Generate hazards map automatically if not explicitly provided var hazards map[types.ChainIndex]types.BlockSeal if tc.hazards != nil { hazards = tc.hazards } else { hazards = make(map[types.ChainIndex]types.BlockSeal) for chainStr := range tc.chainBlocks { hazards[chainIndex(chainStr)] = types.BlockSeal{Number: 1} } } // Run the test err := HazardCycleChecks(deps, 100, hazards) // No error expected if tc.expectErr == nil { require.NoError(t, err, tc.msg) return } // Error expected, make sure it's the right one require.Error(t, err, tc.msg) if errors.Is(err, tc.expectErr) { require.ErrorIs(t, err, tc.expectErr, tc.msg) } else { require.Contains(t, err.Error(), tc.expectErr.Error(), tc.msg) } } func chainIndex(s string) types.ChainIndex { id, err := strconv.ParseUint(s, 10, 32) if err != nil { panic(fmt.Sprintf("invalid chain index in test: %v", err)) } return types.ChainIndex(id) } func execMsg(chain string, logIdx uint32) *types.ExecutingMessage { return execMsgWithTimestamp(chain, logIdx, 100) } func execMsgWithTimestamp(chain string, logIdx uint32, timestamp uint64) *types.ExecutingMessage { return &types.ExecutingMessage{ Chain: chainIndex(chain), LogIdx: logIdx, Timestamp: timestamp, } } var emptyChainBlocks = map[string]chainBlockDef{ "1": { logCount: 0, messages: map[uint32]*types.ExecutingMessage{}, }, } func TestHazardCycleChecksFailures(t *testing.T) { testOpenBlockErr := errors.New("test OpenBlock error") tests := []hazardCycleChecksTestCase{ { name: "empty hazards", chainBlocks: emptyChainBlocks, hazards: make(map[types.ChainIndex]types.BlockSeal), expectErr: nil, msg: "expected no error when there are no hazards", }, { name: "nil hazards", chainBlocks: emptyChainBlocks, hazards: nil, expectErr: nil, msg: "expected no error when there are nil hazards", }, { name: "nil blocks", chainBlocks: nil, hazards: nil, expectErr: nil, msg: "expected no error when there are nil blocks and hazards", }, { name: "failed to open block error", chainBlocks: emptyChainBlocks, openBlockFn: func(chainID types.ChainID, blockNum uint64) (eth.BlockRef, uint32, map[uint32]*types.ExecutingMessage, error) { return eth.BlockRef{}, 0, nil, testOpenBlockErr }, expectErr: errors.New("failed to open block"), msg: "expected error when OpenBlock fails", }, { name: "block mismatch error", chainBlocks: emptyChainBlocks, // openBlockFn returns a block number that doesn't match the expected block number. openBlockFn: func(chainID types.ChainID, blockNum uint64) (eth.BlockRef, uint32, map[uint32]*types.ExecutingMessage, error) { return eth.BlockRef{Number: blockNum + 1}, 0, make(map[uint32]*types.ExecutingMessage), nil }, expectErr: errors.New("tried to open block"), msg: "expected error due to block mismatch", }, { name: "invalid log index error", chainBlocks: map[string]chainBlockDef{ "1": { logCount: 3, messages: map[uint32]*types.ExecutingMessage{ 5: execMsg("1", 0), // Invalid index >= logCount. }, }, }, expectErr: ErrExecMsgHasInvalidIndex, msg: "expected invalid log index error", }, { name: "self reference detected error", chainBlocks: map[string]chainBlockDef{ "1": { logCount: 1, messages: map[uint32]*types.ExecutingMessage{ 0: execMsg("1", 0), // Points at itself. }, }, }, expectErr: types.ErrConflict, msg: "expected self reference detection error", }, { name: "unknown chain", chainBlocks: map[string]chainBlockDef{ "1": { logCount: 2, messages: map[uint32]*types.ExecutingMessage{ 1: execMsg("2", 0), // References chain 2 which isn't in hazards. }, }, }, hazards: map[types.ChainIndex]types.BlockSeal{ 1: {Number: 1}, // Only include chain 1. }, expectErr: ErrExecMsgUnknownChain, msg: "expected unknown chain error", }, } runHazardCycleChecksTestCaseGroup(t, "Failure", tests) } func TestHazardCycleChecksNoCycle(t *testing.T) { tests := []hazardCycleChecksTestCase{ { name: "no logs", chainBlocks: emptyChainBlocks, expectErr: nil, msg: "expected no cycle found for block with no logs", }, { name: "one basic log", chainBlocks: map[string]chainBlockDef{ "1": { logCount: 1, messages: map[uint32]*types.ExecutingMessage{}, }, }, msg: "expected no cycle found for single basic log", }, { name: "one exec log", chainBlocks: map[string]chainBlockDef{ "1": { logCount: 2, messages: map[uint32]*types.ExecutingMessage{ 1: execMsg("1", 0), }, }, }, msg: "expected no cycle found for single exec log", }, { name: "two basic logs", chainBlocks: map[string]chainBlockDef{ "1": { logCount: 2, messages: map[uint32]*types.ExecutingMessage{}, }, }, msg: "expected no cycle found for two basic logs", }, { name: "two exec logs to same target", chainBlocks: map[string]chainBlockDef{ "1": { logCount: 3, messages: map[uint32]*types.ExecutingMessage{ 1: execMsg("1", 0), 2: execMsg("1", 0), }, }, }, msg: "expected no cycle found for two exec logs pointing at the same log", }, { name: "two exec logs to different targets", chainBlocks: map[string]chainBlockDef{ "1": { logCount: 3, messages: map[uint32]*types.ExecutingMessage{ 1: execMsg("1", 0), 2: execMsg("1", 1), }, }, }, msg: "expected no cycle found for two exec logs pointing at the different logs", }, { name: "one basic log one exec log", chainBlocks: map[string]chainBlockDef{ "1": { logCount: 2, messages: map[uint32]*types.ExecutingMessage{ 1: execMsg("1", 0), }, }, }, msg: "expected no cycle found for one basic and one exec log", }, { name: "first log is exec", chainBlocks: map[string]chainBlockDef{ "1": { logCount: 1, messages: map[uint32]*types.ExecutingMessage{ 0: execMsg("2", 0), }, }, "2": { logCount: 1, messages: nil, }, }, msg: "expected no cycle found first log is exec", }, { name: "cycle through older timestamp", chainBlocks: map[string]chainBlockDef{ "1": { logCount: 2, messages: map[uint32]*types.ExecutingMessage{ 0: execMsg("2", 0), 1: execMsgWithTimestamp("2", 1, 101), }, }, "2": { logCount: 2, messages: map[uint32]*types.ExecutingMessage{ 0: execMsg("1", 1), }, }, }, msg: "expected no cycle detection error for cycle through messages with different timestamps", }, // This should be caught by earlier validations, but included for completeness. { name: "cycle through younger timestamp", chainBlocks: map[string]chainBlockDef{ "1": { logCount: 2, messages: map[uint32]*types.ExecutingMessage{ 0: execMsg("2", 0), 1: execMsgWithTimestamp("2", 1, 99), }, }, "2": { logCount: 2, messages: map[uint32]*types.ExecutingMessage{ 0: execMsg("1", 1), }, }, }, msg: "expected no cycle detection error for cycle through messages with different timestamps", }, } runHazardCycleChecksTestCaseGroup(t, "NoCycle", tests) } func TestHazardCycleChecksCycle(t *testing.T) { tests := []hazardCycleChecksTestCase{ { name: "2-cycle in single chain with first log", chainBlocks: map[string]chainBlockDef{ "1": { logCount: 3, messages: map[uint32]*types.ExecutingMessage{ 0: execMsg("1", 2), 2: execMsg("1", 0), }, }, }, expectErr: ErrCycle, msg: "expected cycle detection error", }, { name: "2-cycle in single chain with first log, adjacent", chainBlocks: map[string]chainBlockDef{ "1": { logCount: 2, messages: map[uint32]*types.ExecutingMessage{ 0: execMsg("1", 1), 1: execMsg("1", 0), }, }, }, expectErr: ErrCycle, msg: "expected cycle detection error", }, { name: "2-cycle in single chain, not first, adjacent", chainBlocks: map[string]chainBlockDef{ "1": { logCount: 3, messages: map[uint32]*types.ExecutingMessage{ 1: execMsg("1", 2), 2: execMsg("1", 1), }, }, }, expectErr: ErrCycle, msg: "expected cycle detection error", }, { name: "2-cycle in single chain, not first, not adjacent", chainBlocks: map[string]chainBlockDef{ "1": { logCount: 4, messages: map[uint32]*types.ExecutingMessage{ 1: execMsg("1", 3), 3: execMsg("1", 1), }, }, }, expectErr: ErrCycle, msg: "expected cycle detection error", }, { name: "2-cycle across chains", chainBlocks: map[string]chainBlockDef{ "1": { logCount: 2, messages: map[uint32]*types.ExecutingMessage{ 1: execMsg("2", 0), }, }, "2": { logCount: 2, messages: map[uint32]*types.ExecutingMessage{ 0: execMsg("1", 1), }, }, }, expectErr: ErrCycle, msg: "expected cycle detection error for cycle through executing messages", }, { name: "3-cycle in single chain", chainBlocks: map[string]chainBlockDef{ "1": { logCount: 4, messages: map[uint32]*types.ExecutingMessage{ 1: execMsg("1", 2), // Points to log 2 2: execMsg("1", 3), // Points to log 3 3: execMsg("1", 1), // Points back to log 1 }, }, }, expectErr: ErrCycle, msg: "expected cycle detection error for 3-node cycle", }, { name: "cycle through adjacency dependency", chainBlocks: map[string]chainBlockDef{ "1": { logCount: 10, messages: map[uint32]*types.ExecutingMessage{ 1: execMsg("1", 5), // Points to log 5 5: execMsg("1", 2), // Points back to log 2 which is adjacent to log 1 }, }, }, expectErr: ErrCycle, msg: "expected cycle detection error for when cycle goes through adjacency dependency", }, { name: "2-cycle across chains with 3 hazard chains", chainBlocks: map[string]chainBlockDef{ "1": { logCount: 2, messages: map[uint32]*types.ExecutingMessage{ 1: execMsg("2", 1), }, }, "2": { logCount: 2, messages: map[uint32]*types.ExecutingMessage{ 1: execMsg("1", 1), }, }, "3": {}, }, expectErr: ErrCycle, hazards: map[types.ChainIndex]types.BlockSeal{ 1: {Number: 1}, 2: {Number: 1}, 3: {Number: 1}, }, msg: "expected cycle detection error for cycle through executing messages", }, } runHazardCycleChecksTestCaseGroup(t, "Cycle", tests) } const ( largeGraphChains = 10 largeGraphLogsPerChain = 10000 ) func TestHazardCycleChecksLargeGraphNoCycle(t *testing.T) { // Create a large but acyclic graph chainBlocks := make(map[string]chainBlockDef) for i := 1; i <= largeGraphChains; i++ { msgs := make(map[uint32]*types.ExecutingMessage) // Create a chain of dependencies across chains if i > 1 { for j := uint32(0); j < largeGraphLogsPerChain; j++ { // Point to previous chain, same log index msgs[j] = execMsg(strconv.Itoa(i-1), j) } } chainBlocks[strconv.Itoa(i)] = chainBlockDef{ logCount: largeGraphLogsPerChain, messages: msgs, } } tc := hazardCycleChecksTestCase{ name: "Large graph without cycles", chainBlocks: chainBlocks, expectErr: nil, msg: "expected no cycle in large acyclic graph", } runHazardCycleChecksTestCase(t, tc) } func TestHazardCycleChecksLargeGraphCycle(t *testing.T) { // Create a large graph with a cycle hidden in it const cycleChain = 3 const cycleLogIndex = 5678 chainBlocks := make(map[string]chainBlockDef) for i := 1; i <= largeGraphChains; i++ { msgs := make(map[uint32]*types.ExecutingMessage) // Create a chain of dependencies across chains if i > 1 { for j := uint32(0); j < largeGraphLogsPerChain; j++ { if i == cycleChain && j == cycleLogIndex { // Create a cycle by pointing back to chain 1 msgs[j] = execMsg("1", cycleLogIndex+1) } else { // Normal case: point to previous chain, same log index msgs[j] = execMsg(strconv.Itoa(i-1), j) } } } else { // In chain 1, create the other side of the cycle msgs[cycleLogIndex+1] = execMsg(strconv.Itoa(cycleChain), cycleLogIndex) } chainBlocks[strconv.Itoa(i)] = chainBlockDef{ logCount: largeGraphLogsPerChain, messages: msgs, } } tc := hazardCycleChecksTestCase{ name: "Large graph with cycle", chainBlocks: chainBlocks, expectErr: ErrCycle, msg: "expected to detect cycle in large cyclic graph", } runHazardCycleChecksTestCase(t, tc) }