`lookupKeyValue` in `Development.IDE.Graph.Internal.Key` sometimes errors

[MangoIV]

while trouble shooting something else, I encountered HLS erroring with the following message:

(GhcSessionDeps,NormalizedUri (-1539086352248807771) "inmemory://model/1")IntMap.!: key 15 is not

This comes from lookupKeyValue in Development.IDE.Graph.Internal.Key. The IntMap in that module's type GlobalKeyValueMap which is where the missing key was tried be looked up from, stores the keys to the values in another HashMap, i.e. the type looks as follows:

newtype Key = UnsafeMkKey Int

pattern Key :: () => (Typeable a, Hashable a, Show a) => a -> Key
pattern Key a <- (lookupKeyValue -> KeyValue a _)
{-# COMPLETE Key #-}

data KeyValue = forall a . (Typeable a, Hashable a, Show a) => KeyValue a Text

instance Eq KeyValue where
    KeyValue a _ == KeyValue b _ = Just a == cast b
instance Hashable KeyValue where
    hashWithSalt i (KeyValue x _) = hashWithSalt i (typeOf x, x)
instance Show KeyValue where
    show (KeyValue _ t) = T.unpack t

data GlobalKeyValueMap = GlobalKeyValueMap !(Map.HashMap KeyValue Key) !(IntMap KeyValue) {-# UNPACK #-} !Int

keyMap :: IORef GlobalKeyValueMap
keyMap = unsafePerformIO $ newIORef (GlobalKeyValueMap Map.empty IM.empty 0)

{-# NOINLINE keyMap #-}

The Int and the IntMap are related in the sense that the Int is supposed to indicate the next KeyValue to use.

The only way to update the IntMap is by the use of newKey which returns an opaque wrapper around the Int. To my knowledge it is also the only way of obtaining such a Key, since its constructor is not exported:

newKey :: (Typeable a, Hashable a, Show a) => a -> Key
newKey k = unsafePerformIO $ do
  traceM $ "inserting new key: " <> show k
  let !newKey = KeyValue k (T.pack (show k)) -- FIXME: this is a spaceleak in its purest form (no use for the thing, purely space leak)
  atomicModifyIORef' keyMap $ \km@(GlobalKeyValueMap hm im n) ->
    let new_key = Map.lookup newKey hm
    in case new_key of
          Just v  -> (km, v)
          Nothing ->
            let !new_index = UnsafeMkKey n
            in (GlobalKeyValueMap (Map.insert newKey new_index hm) (IM.insert n newKey im) (n+1), new_index)
{-# NOINLINE newKey #-}

lookupKeyValue :: Key -> KeyValue
lookupKeyValue (UnsafeMkKey x) = unsafePerformIO $ do
  GlobalKeyValueMap _ im _ <- readIORef keyMap
  pure $! im IM.! x

I therefore conclude, that, if newKey wasn't buggy, there'd be no way to ever get the error we've gotten.

Unforunately we do get it though - as to why that is, I don't have a precise explanation. I imagine that the atomicModifyIORef' is not actually executed, my hunches were

• new_index is somehow floated out (I think this is impossible, since n comes from within the atomicModifyIORef') or something has aborted the atomicModifyIORef'
• atomicModifyIORef' returns the value but does not actually execute the transaction in the cell (I think this should also be impossible)

[MangoIV]

Something that I don't know is how the atomicity of the atomicModifyIORef' interacts with the unsafePerformIO. E.g. could

-- start atomic block
read ref
write ref
-- end atomic block
read ref 

be reordered to

read ref 
read ref 
write ref 

because in that case, we might already have returned the value to the second read and then the value might be missing. but that would mean that the atomicModifyIORef wasn't really atomic anymore... :P

[MangoIV]

Also for context, the trace from -prof:

(GhcSessionDeps,NormalizedUri (-1539086352248807771) "inmemory://model/1")IntMap.!: key 15 is not
  an element of the map
  CallStack (from HasCallStack):
  error, called at libraries/containers/containers/src/Data/IntMap/Internal.hs:601:17 in
  containers-0.7-c3e2:Data.IntMap.Internal
  CallStack (from -prof):
  Development.IDE.Graph.Internal.Key.renderKey (src/Development/IDE/Graph/Internal/Key.hs:107:1-46)
  Development.IDE.Core.Tracing.withTrace (src/Development/IDE/Core/Tracing.hs:(39,1)-(44,37))
...

[MangoIV]

some additional info

• compiled with ghc 9.10
• no optimizations
• profiling on, no additional profiling flags
• deps obtained via nix
• my branch has a bunch of additional stuff - if i don't get anyway, I will push and post a link to it

[MangoIV]

core looks sensible, btw.

[fendor]

I can reproduce the issue with GHC 9.6.7, no optimisations, and compiling all dependencies with profiling.

[fendor]

Closed by #4654

Perhaps we want to redesign the API to avoid some unsafePerformIOs in the future?

[MangoIV]

As I see it the main reason for this is interning. Are there any good libraries for interning that go beyond strings?

[fendor]

Perhaps a good opportunity to give https://hackage.haskell.org/package/symbolize a try?

[MangoIV]

Well that's exactly what I meant with "only strings". This is for string interning only.