pykinos-penelope-0.1.0.2: src/Pykinos/Effect/Penelope.hs
{-# LANGUAGE BangPatterns, DataKinds, GADTs, PolyKinds, RankNTypes, ScopedTypeVariables, PatternSynonyms #-}
{-# OPTIONS_GHC -Wno-pattern-namespace-specifier #-}
{- |
Module : Pykinos.Effect.Penelope
Description : Penelope Higher-Order Scoped Batching, Transient Epochs, & MVCC Pushouts
Copyright : (c) Nadia Yvette Chambers, 2026
License : EUPL-1.2
Maintainer : Nadia Chambers <nadia.yvette.chambers@ik.me>
Stability : experimental
Portability : non-portable (GHC extensions, row types)
Provides Penelope effect algebra integration for transient-epoch batching, lockless
Multi-Version Concurrency Control (MVCC) snapshots, and categorical pushout merges.
= Architectural Mechanics
1. **Transient Epoch Scoping ('withTransientEpoch'):**
In transactional workloads, serial copy-on-write allocations per individual write
generate excessive garbage and node copies. A transient epoch amortizes allocation
by tagging all node insertions during an active batch with a freshly minted 'EpochId'.
Nodes created within the same epoch can be reused without defensive cloning.
2. **Lockless MVCC Snapshots ('MVCCSnapshot'):**
Captures an \(O(1)\) reference to the root 'BPlusMap' at a given 'EpochId',
optionally pre-materializing a contiguous 'FASTMap' read-accelerator ('msFastAcc')
for branch-minimized query routing.
3. **Categorical Pushout Commutation ('commitEpochPushout'):**
When two concurrent tasks fork from a common base snapshot \(V_0\) into divergent
branches \(V_1\) and \(V_2\), their concurrent modifications form a categorical pushout span:
\[
\begin{array}{ccc}
V_0 & \longrightarrow & V_1 \\
\downarrow & & \downarrow \\
V_2 & \longrightarrow & V_1 \amalg_{V_0} V_2
\end{array}
\]
* If the disjoint deltas commute or represent idempotent updates to identical values,
the pushout merges cleanly into a unified 'MVCCSnapshot'.
* If concurrent writes to the same key diverge, 'commitEpochPushout' isolates the
cellular sheaf \(H^1\) obstruction as a list of 'PushoutConflict' records.
-}
module Pykinos.Effect.Penelope
( -- * Higher-Order Penelope Effect
PykinosBatchH(..)
, PukinosBatchH
, pattern RunPukinosBatch
-- * MVCC Snapshots & Obstructions
, MVCCSnapshot(..)
, PushoutConflict(..)
-- * Epoch Execution & Merging
, withTransientEpoch
, mvccSnapshot
, commitEpochPushout
) where
import Data.Kind (Type)
import Pykinos.Tree.BPlus
( EpochId
, BPlusMap(..)
, lookupBPlus
, insertBPlusEpoch
, toAscListBPlus
)
import Pykinos.Tree.FAST (FASTMap, freezeFAST)
-- | Higher-Order Scoped Penelope Effect for transient epoch-stamped mutations over a 'BPlusMap'.
--
-- Regions track input and output effect rows during scoped batch mutation.
data PykinosBatchH k v (regions :: [([Type], [Type])]) (ins :: [Type]) (outs :: [Type]) where
-- | Opens a transient mutation scope with a freshly minted 'EpochId',
-- avoiding wide-node write amplification before freezing on region exit.
RunPykinosBatch
:: !(BPlusMap k v)
-> (EpochId -> BPlusMap k v -> BPlusMap k v)
-> PykinosBatchH k v '[ '(ins, outs) ] ins outs
-- | Backward-compatible type alias for legacy PukinosBatchH.
type PukinosBatchH = PykinosBatchH
-- | Backward-compatible pattern synonym for 'RunPykinosBatch'.
pattern RunPukinosBatch
:: forall k v (ins :: [Type]) (outs :: [Type]).
BPlusMap k v
-> (EpochId -> BPlusMap k v -> BPlusMap k v)
-> PykinosBatchH k v '[ '(ins, outs) ] ins outs
pattern RunPukinosBatch m f = RunPykinosBatch m f
-- | Lockless \(O(1)\) Multi-Version Concurrency Control (MVCC) snapshot handle.
--
-- Pairs an immutable 'EpochId' watermark with the root 'BPlusMap' and an optional
-- pre-materialized 'FASTMap' read accelerator.
data MVCCSnapshot k v = MVCCSnapshot
{ msEpoch :: {-# UNPACK #-} !EpochId
-- ^ Epoch watermark associated with this snapshot.
, msTree :: !(BPlusMap k v)
-- ^ Root persistent B+ tree node hierarchy.
, msFastAcc :: !(Maybe (FASTMap k v))
-- ^ Optional cache-line blocked Eytzinger read accelerator.
} deriving (Eq, Show)
-- | Cohomological \(H^1\) merge obstruction on key 'k'.
--
-- Materialized when two concurrent branches modify the same key to conflicting,
-- non-equal values relative to base snapshot \(V_0\).
data PushoutConflict k v = PushoutConflict
{ pcKey :: !k
-- ^ Key where concurrent conflicting writes occurred.
, pcBaseVal :: !(Maybe v)
-- ^ Original value in common ancestor snapshot \(V_0\) (if present).
, pcLeftVal :: !v
-- ^ Mutated value in worker branch \(V_1\).
, pcRightVal :: !v
-- ^ Divergent mutated value in worker branch \(V_2\).
} deriving (Eq, Show)
-- | Execute a batch of modifications under a freshly incremented transient 'EpochId'.
--
-- Running time: \(O(k \log_M n)\) for \(k\) inserted entries.
{-# INLINE withTransientEpoch #-}
withTransientEpoch
:: Ord k
=> EpochId
-- ^ Previous epoch watermark.
-> BPlusMap k v
-- ^ Base B+ tree before batch modification.
-> (EpochId -> (k -> v -> BPlusMap k v -> BPlusMap k v) -> BPlusMap k v -> BPlusMap k v)
-- ^ Scoped mutation lambda receiving new 'EpochId' and insertion closure.
-> (EpochId, BPlusMap k v)
withTransientEpoch !prevEpoch !baseTree batchFn =
let !nextEpoch = prevEpoch + 1
!resTree = batchFn nextEpoch (insertBPlusEpoch nextEpoch) baseTree
in (nextEpoch, resTree)
-- | Capture an \(O(1)\) lockless MVCC snapshot of a 'BPlusMap' (optionally freezing a 'FASTMap').
--
-- Running time: \(O(1)\) when @buildFast = False@; \(O(n)\) when building FAST accelerator.
{-# INLINE mvccSnapshot #-}
mvccSnapshot :: EpochId -> Bool -> BPlusMap k v -> MVCCSnapshot k v
mvccSnapshot !ep !buildFast !tree =
MVCCSnapshot
{ msEpoch = ep
, msTree = tree
, msFastAcc = if buildFast then Just (freezeFAST tree) else Nothing
}
-- | Compute the Categorical Pushout (\(V_1 \amalg_{V_0} V_2\)) of two concurrent 'BPlusMap'
-- branches forked from a common ancestor snapshot \(V_0\).
--
-- * If all modifications commute or resolve idempotently, returns 'Right' with the merged snapshot.
-- * If overlapping keys diverge, returns 'Left' containing the list of 'PushoutConflict' records.
--
-- Running time: \(O(|\Delta_1| \log n + |\Delta_2| \log n)\).
commitEpochPushout
:: (Ord k, Eq v)
=> MVCCSnapshot k v
-- ^ Base snapshot \(V_0\)
-> BPlusMap k v
-- ^ Worker 1 branch \(V_1\)
-> BPlusMap k v
-- ^ Worker 2 branch \(V_2\)
-> Either [PushoutConflict k v] (MVCCSnapshot k v)
commitEpochPushout (MVCCSnapshot !baseEp !v0 _) !v1 !v2 =
let !newEp = baseEp + 1
!deltas1 = diffAgainstBase v0 v1
!deltas2 = diffAgainstBase v0 v2
(!conflicts, !merged) =
foldl'
(\(!errs, !accTree) (k, val2) ->
case lookup k deltas1 of
Nothing ->
(errs, insertBPlusEpoch newEp k val2 accTree)
Just val1
| val1 == val2 ->
(errs, insertBPlusEpoch newEp k val1 accTree)
| otherwise ->
let !c = PushoutConflict k (lookupBPlus k v0) val1 val2
in (c : errs, accTree))
([], applyDeltas newEp v0 deltas1)
deltas2
in case conflicts of
[] -> Right (mvccSnapshot newEp False merged)
cs -> Left (reverse cs)
-- | Extract all entries in 'vBranch' that differ from base map 'v0'.
diffAgainstBase :: (Ord k, Eq v) => BPlusMap k v -> BPlusMap k v -> [(k, v)]
diffAgainstBase !v0 !vBranch =
[ (k, v)
| (k, v) <- toAscListBPlus vBranch
, lookupBPlus k v0 /= Just v
]
-- | Sequentially apply a list of key-value deltas stamped with epoch 'ep'.
applyDeltas :: Ord k => EpochId -> BPlusMap k v -> [(k, v)] -> BPlusMap k v
applyDeltas !ep = foldl' (\acc (k, v) -> insertBPlusEpoch ep k v acc)