packages feed

cek-polytropos-0.1.0.2: src/Cek/Polytropos/Dissect.hs

{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE StrictData #-}

-- |
-- Module      : Cek.Polytropos.Dissect
-- Description : Universal O(1) array cursor dissection over Polytropos.Core.Rep.
--
-- Replaces O(N) nested 'GHC.Generics' sum/product continuation frames with a
-- single flat cursor over 'Polytropos.Core.Rep'.
--
-- === The Problem of Generic Dissection Overhead
--
-- Standard polynomial functor dissection via GHC's 'Generic1' introduces deeply
-- nested tree structures of binary sums (':+:') and binary products (':*:').
-- For a constructor with \(k\) arguments, the generic representation requires
-- \(k\) nested 'Prod2' frame allocations. Each frame allocation costs multiple
-- heap words and pointer traversals.
--
-- === Flat Representation Dissection
--
-- In 'Polytropos.Core', every algebraic data type or record constructor is represented
-- as a single contiguous array ('Rep'):
--
-- @
-- data Rep (f :: Type -> Type) a = Rep {-# UNPACK #-} !Word !(SmallArray Any)
-- @
--
-- 'PolyDissect' exploits this contiguous representation by turning functor dissection
-- into a single integer cursor ('pdCursor') sliding across a 'SmallArray':
--
--   * Slots @[0 .. pdCursor - 1]@: Contain evaluated Clowns (@c@).
--   * Slot @pdCursor@: The active evaluation hole currently being reduced.
--   * Slots @[pdCursor + 1 .. n - 1]@: Contain unevaluated Jokers (@j@).
--
-- This reduces frame allocation to an unboxed cursor increment, achieving $O(1)$
-- stepping with optimal cache locality and zero tree-pointer chasing.
module Cek.Polytropos.Dissect
  ( -- * Flat Dissection Representation
    PolyDissect(..)

    -- * Dissection Stepping Operations
  , polyStepIn
  , polyStepNext
  ) where

import Data.Bifunctor (Bifunctor(..))
import Data.Primitive.SmallArray
  ( SmallArray
  , indexSmallArray
  , runSmallArray
  , sizeofSmallArray
  , thawSmallArray
  , writeSmallArray
  )
import GHC.Exts (Any, unsafeCoerce#)
import Polytropos.Core (Rep(..))

-- | Universal dissection state for any 'Polytropos.Core.Rep' syntax node.
--
-- Invariant: in 'pdSlots', indices @[0 .. pdCursor - 1]@ hold evaluated
-- Clowns @c@, index 'pdCursor' is the active hole, and indices
-- @[pdCursor + 1 .. n - 1]@ hold unevaluated Jokers @j@.
data PolyDissect c j = PolyDissect
  { pdTag    :: {-# UNPACK #-} !Word
    -- ^ The constructor tag index within the source sum/data type.
  , pdCursor :: {-# UNPACK #-} !Int
    -- ^ Zero-based offset of the currently active evaluation hole.
  , pdSlots  :: !(SmallArray Any)
    -- ^ Array of slots partitioned by 'pdCursor' into Clowns and Jokers.
  }

-- | Functor mapping over the unevaluated Jokers to the right of 'pdCursor'.
instance Functor (PolyDissect c) where
  fmap g (PolyDissect tag cur arr) =
    let !n = sizeofSmallArray arr
        !arr' = runSmallArray $ do
          m <- thawSmallArray arr 0 n
          let loop !i
                | i >= n = pure m
                | i <= cur = loop (i + 1)
                | otherwise = do
                    let !j = unsafeCoerce# (indexSmallArray arr i)
                    writeSmallArray m i (unsafeCoerce# (g j))
                    loop (i + 1)
          loop 0
    in PolyDissect tag cur arr'

-- | Bifunctor mapping over both evaluated Clowns and unevaluated Jokers.
instance Bifunctor PolyDissect where
  bimap f g (PolyDissect tag cur arr) =
    let !n = sizeofSmallArray arr
        !arr' = runSmallArray $ do
          m <- thawSmallArray arr 0 n
          let loop !i
                | i >= n = pure m
                | i < cur = do
                    let !c = unsafeCoerce# (indexSmallArray arr i)
                    writeSmallArray m i (unsafeCoerce# (f c))
                    loop (i + 1)
                | i == cur = loop (i + 1)
                | otherwise = do
                    let !j = unsafeCoerce# (indexSmallArray arr i)
                    writeSmallArray m i (unsafeCoerce# (g j))
                    loop (i + 1)
          loop 0
    in PolyDissect tag cur arr'

-- | Step into slot 0 of a 'Polytropos.Core.Rep' syntax node in strictly O(1) time.
--
-- If the constructor has zero payload slots (e.g. nullary constructor or empty record),
-- returns 'Left' immediately with zero heap allocations. Otherwise, initializes
-- 'pdCursor' at 0 and returns 'Right' with the first child term paired with 'PolyDissect'.
{-# INLINE polyStepIn #-}
polyStepIn
  :: Rep f j
  -> Either (Rep g c) (f j, PolyDissect (g c) (f j))
polyStepIn (Rep !tag !arr)
  | sizeofSmallArray arr == 0 =
      Left (Rep tag (unsafeCoerce# arr))
  | otherwise =
      let !firstJoker = unsafeCoerce# (indexSmallArray arr 0)
      in Right (firstJoker, PolyDissect tag 0 (unsafeCoerce# arr))

-- | Plug an evaluated Clown @g c@ into 'pdCursor' and advance to @pdCursor + 1@.
--
-- When @pdCursor + 1 == sizeofSmallArray pdSlots@, all child terms have been evaluated
-- and the complete reconstructed 'Rep' is returned in 'Left'.
-- Otherwise, returns 'Right' with the next Joker subterm and updated 'PolyDissect'.
{-# INLINE polyStepNext #-}
polyStepNext
  :: g c
  -> PolyDissect (g c) (f j)
  -> Either (Rep g c) (f j, PolyDissect (g c) (f j))
polyStepNext !clownVal (PolyDissect !tag !cursor !arr) =
  let !n     = sizeofSmallArray arr
      !nextC = cursor + 1
      !arr'  = runSmallArray $ do
                 m <- thawSmallArray arr 0 n
                 writeSmallArray m cursor (unsafeCoerce# clownVal)
                 pure m
  in if nextC >= n
       then Left (Rep tag (unsafeCoerce# arr'))
       else let !nextJoker = unsafeCoerce# (indexSmallArray arr nextC)
            in Right (nextJoker, PolyDissect tag nextC arr')