packages feed

pykinos-core-0.1.0.2: src/Pykinos/Schema/HiddenClass.hs

{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE DerivingStrategies #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE RecordWildCards #-}
{-# LANGUAGE StrictData #-}

-- |
-- Module      : Pykinos.Schema.HiddenClass
-- Description : Order-preserving symbol lexicon and 3-way dynamic record MergeMorphs.
--
-- Eliminates dynamic @Map Text Expr@ trees by interning field names into
-- rank-ordered 'FieldId's and representing record shapes as interned 'SchemaId's
-- with precomputed 3-way 'MergeMorph3' gather plans.
--
-- === Architectural Rationale
--
-- Traditional AST record representations in interpreters (such as Dhall and 1ML)
-- use unbalanced search trees or associative maps. When performing record operations
-- (such as record merge @//@, deep meet @/\\@, or signature projection @:>@), every
-- operation traverses pointer-heavy tree structures, resulting in significant GC
-- pressure and branch mispredictions.
--
-- By decoupling the field names into a frozen, rank-ordered 'Lexicon' and mapping
-- field sets into contiguous sorted 'PrimArray's of 'Word32's ('SchemaId'), record
-- merge operations become pure array-to-array linear scans synthesized in $O(N_1 + N_2)$
-- time into unboxed 64-bit gather codes ('MergeMorph3').
--
-- === 3-Way Gather Code Representation
--
-- Each gather code in 'MergeMorph3' is an unboxed 'Int64':
--
--   1. Positive values (@code >= 0@): The field is copied directly from slot
--      @code@ of the left record.
--   2. Negative values with bit 62 clear (@code < 0@, @bit 62 == 0@): The field
--      is copied directly from slot @complement code@ of the right record.
--   3. Negative values with bit 62 set (@code < 0@, @bit 62 == 1@): Both records
--      contain the field. A collision has occurred that must be resolved via
--      recursive normalization (for 'OpCombineDeep'). The two source slot indices
--      @(idx1, idx2)@ are packed into bits 0..59.
module Pykinos.Schema.HiddenClass
  ( -- * Field and Schema Identifiers
    FieldId(..)
  , SchemaId(..)

    -- * Dynamic Record Operations
  , RecordOp(..)
  , MergeMorph3(..)

    -- * Symbol Lexicon
  , Lexicon(..)
  , buildLexicon
  , lookupFieldId
  , lookupFieldText

    -- * Slot Search and Gather Code Encoding
  , findFieldSlot
  , collisionBit3
  , encodeRightSlot3
  , encodeCollision3
  , decodeMergeCode3

    -- * Linear Merge Synthesis
  , synthesizeMergeMorph3
  ) where

import Data.Bits (complement, shiftL, shiftR, unsafeShiftR, (.&.), (.|.))
import Data.Int (Int64)
import qualified Data.Map.Strict as Map
import Data.Primitive.PrimArray
  ( PrimArray
  , indexPrimArray
  , primArrayFromList
  , sizeofPrimArray
  )
import Data.Primitive.SmallArray
  ( SmallArray
  , indexSmallArray
  , smallArrayFromList
  )
import qualified Data.Set as Set
import Data.Text (Text)
import Data.Word (Word32)

-- | Rank-ordered 32-bit field identifier.
--
-- Invariant: For all field identifiers @fid1@ and @fid2@,
-- @fid1 < fid2@ holds if and only if @text(fid1) < text(fid2)@ in standard
-- lexicographical UTF-8 byte order. This invariant guarantees that sorting by
-- 'FieldId' is completely isomorphic to sorting by record label 'Text'.
newtype FieldId = FieldId { unFieldId :: Word32 }
  deriving newtype (Eq, Ord, Show)

-- | Interned 32-bit identifier for a sorted 'PrimArray' of 'FieldId's.
--
-- A 'SchemaId' represents the immutable structural type of a record. Two records
-- share the same 'SchemaId' if and only if they possess identical field sets in
-- identical order.
newtype SchemaId = SchemaId { unSchemaId :: Word32 }
  deriving newtype (Eq, Ord, Show)

-- | Dynamic record algebra operations supported by 'MergeMorph3'.
--
-- These correspond to the fundamental record combinators in languages with
-- first-class records and modules:
data RecordOp
  = OpPreferR
    -- ^ Right-biased override union. When a label appears in both records,
    -- the value from the right-hand record overwrites the left-hand record.
    -- Corresponds to Dhall's @//@ and 1ML structure @include@.
  | OpCombineDeep
    -- ^ Recursive deep meet. When a label appears in both records,
    -- the two values collide and must be recursively merged.
    -- Corresponds to Dhall's @/\\@ and 1ML signature sharing.
  | OpRestrict
    -- ^ Domain restriction / projection. Restricts the fields of the left
    -- record to the schema defined by the right record.
    -- Corresponds to 1ML existential sealing (@Mod :> Sig@).
  deriving (Eq, Ord, Show)

-- | 3-way gather plan encoded in an unboxed 'PrimArray' of 'Int64' codes.
--
-- The array length matches the number of fields in the resulting merged record.
-- Each slot contains an instruction specifying how the target value is obtained:
--
--   * @code >= 0@              : copy slot @code@ from left record
--   * @code < 0, bit 62 == 0@  : copy slot @complement code@ from right record
--   * @code < 0, bit 62 == 1@  : lazy deep-meet collision on @(idx1, idx2)@
newtype MergeMorph3 = MergeMorph3 { unMergeMorph3 :: PrimArray Int64 }
  deriving (Eq, Show)

-- | Frozen rank-ordered lexicon mapping 'Text' labels to 'FieldId's.
--
-- Provides bidirectional O(log L) lookup from 'Text' to 'FieldId' and
-- O(1) indexed recovery from 'FieldId' back to 'Text'.
data Lexicon = Lexicon
  { lexToId   :: !(Map.Map Text FieldId)
    -- ^ Forward index mapping unique text labels to rank-ordered field IDs.
  , lexToText :: !(SmallArray Text)
    -- ^ Reverse index enabling O(1) term reconstruction during pretty-printing.
  }
  deriving (Show)

-- | Construct a rank-ordered 'Lexicon' from all field labels appearing in an AST.
--
-- Collects all unique labels, sorts them into strictly ascending order, and assigns
-- zero-based sequential 'Word32' identifiers.
buildLexicon :: [Text] -> Lexicon
buildLexicon rawLabels =
  let sortedUnique = Set.toAscList (Set.fromList rawLabels)
      pairs        = zip sortedUnique [FieldId i | i <- [0 ..]]
  in Lexicon
       { lexToId   = Map.fromDistinctAscList pairs
       , lexToText = smallArrayFromList sortedUnique
       }

-- | Resolve a 'Text' label to its rank-ordered 'FieldId' in O(log L) time.
{-# INLINE lookupFieldId #-}
lookupFieldId :: Lexicon -> Text -> Maybe FieldId
lookupFieldId Lexicon{..} !txt = Map.lookup txt lexToId

-- | Recover the original 'Text' label from a 'FieldId' in strictly O(1) time.
{-# INLINE lookupFieldText #-}
lookupFieldText :: Lexicon -> FieldId -> Text
lookupFieldText Lexicon{..} (FieldId !w) =
  indexSmallArray lexToText (fromIntegral w)

-- | Bit 62 distinguishes a right-record slot from a two-record deep collision.
-- Bit 63 is the sign bit (1 for negative numbers). Bit 62 serves as the discriminator flag.
collisionBit3 :: Int64
collisionBit3 = 1 `shiftL` 62

-- | Encode a right-record slot index @idx2@ as a negative 'Int64' with bit 62 clear.
--
-- Uses bitwise complement ('Data.Bits.complement') so that @idx2 = 0@ maps to @-1@,
-- @idx2 = 1@ maps to @-2@, etc., ensuring strict negativity while keeping bit 62 zero.
{-# INLINE encodeRightSlot3 #-}
encodeRightSlot3 :: Int -> Int64
encodeRightSlot3 !idx2 =
  complement (fromIntegral idx2) .&. complement collisionBit3

-- | Encode a colliding pair of slot indices @(idx1, idx2)@ for 'OpCombineDeep'.
--
-- Packs @idx1@ into bits 30..59 and @idx2@ into bits 0..29, sets bit 62, and negates.
{-# INLINE encodeCollision3 #-}
encodeCollision3 :: Int -> Int -> Int64
encodeCollision3 !idx1 !idx2 =
  let !payload = (fromIntegral idx1 `shiftL` 30) .|. fromIntegral idx2
  in complement payload .|. collisionBit3

-- | Decode a 'MergeMorph3' gather code into its constituent source slots:
--
--   * @Left (Left idx1)@   : Unambiguous value from slot @idx1@ of the left record.
--   * @Left (Right idx2)@  : Unambiguous value from slot @idx2@ of the right record.
--   * @Right (idx1, idx2)@ : Recursive collision between @idx1@ and @idx2@.
{-# INLINE decodeMergeCode3 #-}
decodeMergeCode3 :: Int64 -> Either (Either Int Int) (Int, Int)
decodeMergeCode3 !code
  | code >= 0 = Left (Left (fromIntegral code))
  | (code .&. collisionBit3) == 0 =
      Left (Right (fromIntegral (complement code)))
  | otherwise =
      let !raw  = complement (code .&. complement collisionBit3)
          !idx1 = fromIntegral (raw `shiftR` 30)
          !idx2 = fromIntegral (raw .&. 0x3FFFFFFF)
      in Right (idx1, idx2)

-- | Branch-minimized binary search over a sorted 'PrimArray' of 'Word32' field IDs.
--
-- Returns the slot index of the target 'FieldId' if present, or 'Nothing'.
-- Operates in $O(\log N)$ time with zero heap allocations.
{-# INLINE findFieldSlot #-}
findFieldSlot :: PrimArray Word32 -> FieldId -> Maybe Int
findFieldSlot !fields (FieldId !target) =
  go 0 (sizeofPrimArray fields - 1)
  where
    go !lo !hi
      | lo > hi   = Nothing
      | otherwise =
          let !mid = (lo + hi) `unsafeShiftR` 1
              !v   = indexPrimArray fields mid
          in case compare v target of
               LT -> go (mid + 1) hi
               GT -> go lo (mid - 1)
               EQ -> Just mid

-- | Two-finger linear synthesis of a 3-way 'MergeMorph3' over two sorted schemas.
--
-- Traverses the two sorted 'PrimArray's in parallel in $O(N_1 + N_2)$ time, emitting:
--
--   1. The merged schema's sorted 'PrimArray' of field IDs.
--   2. The compiled 'MergeMorph3' gather codes for instantiating the merged record values.
synthesizeMergeMorph3
  :: RecordOp
  -> PrimArray Word32
  -> PrimArray Word32
  -> (PrimArray Word32, MergeMorph3)
synthesizeMergeMorph3 !op !f1 !f2 =
  let !n1 = sizeofPrimArray f1
      !n2 = sizeofPrimArray f2
      -- Linear merge worker with accumulators for output fields and gather codes:
      go !i !j accFields accCodes
        | i >= n1 && j >= n2 =
            -- Both inputs exhausted; finish and freeze output arrays:
            ( primArrayFromList (reverse accFields)
            , MergeMorph3 (primArrayFromList (reverse accCodes))
            )
        | i >= n1 =
            -- Left input exhausted; process remaining right-hand fields:
            case op of
              OpRestrict ->
                -- OpRestrict only retains fields present in the left record:
                ( primArrayFromList (reverse accFields)
                , MergeMorph3 (primArrayFromList (reverse accCodes))
                )
              _ ->
                let !k2 = indexPrimArray f2 j
                in go i (j + 1) (k2 : accFields) (encodeRightSlot3 j : accCodes)
        | j >= n2 =
            -- Right input exhausted; process remaining left-hand fields:
            case op of
              OpRestrict ->
                -- OpRestrict only retains fields present in both records:
                ( primArrayFromList (reverse accFields)
                , MergeMorph3 (primArrayFromList (reverse accCodes))
                )
              _ ->
                let !k1 = indexPrimArray f1 i
                in go (i + 1) j (k1 : accFields) (fromIntegral i : accCodes)
        | otherwise =
            -- Both streams have remaining elements; compare field IDs:
            let !k1 = indexPrimArray f1 i
                !k2 = indexPrimArray f2 j
            in case compare k1 k2 of
                 LT -> case op of
                   OpRestrict -> go (i + 1) j accFields accCodes
                   _          -> go (i + 1) j (k1 : accFields) (fromIntegral i : accCodes)
                 GT -> case op of
                   OpRestrict -> go i (j + 1) accFields accCodes
                   _          -> go i (j + 1) (k2 : accFields) (encodeRightSlot3 j : accCodes)
                 EQ ->
                   -- Field appears in both records; determine resolution by operation:
                   let !code = case op of
                         OpPreferR     -> encodeRightSlot3 j
                         OpCombineDeep -> encodeCollision3 i j
                         OpRestrict    -> fromIntegral i
                   in go (i + 1) (j + 1) (k1 : accFields) (code : accCodes)
  in go 0 0 [] []