• Tyler Smith's avatar
    op-supervisor: Cross safe updates cycle detection + tests (#12530) · 2cf297da
    Tyler Smith authored
    * op-supervisor: experimental cross-safety, with hazard detection
    
    * tweak: Add some errors/error returns in backend/cross.
    
    * wip: Chain index <> ID mapping.
    
    * fix: Check parent instead of re-checking hazardBlock.
    
    * Remove Hazard Work
    
    * Write missing DB Bindings OpenBlock, LocallyDerivedFrom, CrossDerivedFrom
    
    * Configurable WorkFn for Workers
    
    * op-supervisor: move chain-index <> chain ID translation into dependency set, fix some interfaces
    
    * op-supervisor: update cross-safety worker routine
    
    * op-supervisor: update more error handling
    
    * op-supervisor: move errors to types package
    
    * op-supervisor: check CanExecuteAt and CanInitiateAt
    
    * op-supervisor: determine cross-safe candidate and L1 scope, and more fixes
    
    * todo L1 scope increment
    
    * op-supervisor: cross-safe L1 scope bump
    
    * op-supervisor: dependency set getter
    
    * op-supervisor: L1 scope increment fix
    
    * op-supervisor: fix cross-safe updates typing
    
    * op-node: signal L1 traversal of derivation to supervisor
    
    * op-supervisor: fromda fixes and tests
    
    * op-supervisor: fix OpenBlock, fix/add missing interface methods, hook up cross-safe worker routines
    
    * OpenBlock to return map[uint32]ExecutingMessage
    
    * Add Frontier Unit Tests
    
    * fix WithParent panic
    
    * op-node: register L1 traversal with op-supervisor
    
    * op-node,op-supervisor: add logging, temp work around for interop local-safe updates
    
    * Add safe_start_test, unsafe_start_test
    
    * Add safe_update_test and unsafe_update_test
    
    * add worker_test
    
    * op-supervisor: fix cross-safe L1 scope bumping
    
    * op-supervisor: fix logs DB test
    
    * Add cycle.go and initial unit tests.
    
    * fix: Use new execMsg log index info to complete graph.
    
    * debug: Add helper to write out Mermaid of our graph.
    
    * tests: Add more cycle tests.
    
    * tests: Organize cycle tests.
    
    * tests: Add NoCycle test.
    
    * fix: Add edges between basic logs.
    
    * tests: More comprehensive NoCycle tests.
    
    * tests: Make tests not use index-0 exec msgs for now.
    
    * fix: Disallow self-referencing messages.
    
    * fix: Safely handle unknown chains.
    
    * tests,fix: Remove unintended self-reference.
    
    * tests,fix: Remove unintended self-reference.
    
    * tests: Add test for the first log being exec.
    
    * refactor: Create ErrFailedToOpenBlock for error.
    
    * tests,refactor: Use table-driven tests to make it easier to iterate test vectors.
    
    * cleanup: Change some comments and make Mermaid debugging easier to disable.
    
    * tests: Add permuations of 2-cycles involving adjacency and first logs.
    
    * fix: When adding edges for execMsgs, remove node from inDegree0.
    
    * refactor: Split graph build from checks; abstract adding edges.
    
    This allows us to more easily test specifics of our cycle checking.
    
    Errors can be in either part, and only being able to test the entirety
    makes things a little difficult.
    
    Abstracting edge creation helps eliminate bugs like 118aeb6b8.
    
    * tests: Test execMsg to base log which is right after an execMsg to the first execMsg.
    
    * tests: Cycle across timestamps should not return an error.
    
    * fix: Don't consider cycles that depend on out-of-timestamp nodes.
    
    We do this by first collecting every execMsg from all chains, filtering
    out the out-of-timestamp nodes, and putting into a lookup map.
    
    When creating edges, we check to see if the target node is
    uninteresting.
    
    * fix: Remove debug mermaid logging.
    
    * cleanup: Remove stray text in comment.
    
    * tweak: Make presence check more idiomatic; remove possible nil map access.
    
    * docs: Improve comments in cycle detection code.
    
    * cleanup: Reorganize cycle detection code.
    
    * cleanup: Move public types to top.
    
    * cleanup: Change some names for consistency.
    
    * cleanup: Better comment in cycle detection.
    
    * docs: Explain graph representation.
    
    * tests: Re-organize HazardCycleChecks tests.
    
    * docs: Better naming and docs in cycle.go.
    
    * tests: Add large graph cycle detection tests.
    
    * tests: Add nil hazard map test.
    
    * refactor: Slightly tweak graph sort code to nest less; add comments.
    
    * tweak: Make self referencial messages fail with an ErrConflict.
    
    * tests: Add tests for both older/younger timestamps, and document that younger init msgs shouldn't occur.
    
    * tests: Add tests for 2-cycle with 3 chains.
    
    * tweak: Check that an exec msg's init msg exists.
    
    * tests: tweak test to use index 0 instead of 1.
    
    * cleanup: Remove unused function.
    
    * op-e2e: fix interop mock backend action test
    
    CI try 2
    
    ---------
    Co-authored-by: default avatarprotolambda <proto@protolambda.com>
    Co-authored-by: default avataraxelKingsley <axel.kingsley@gmail.com>
    2cf297da
cycle_test.go 14.5 KB