Improve code coverage of the main library

[jeltsch]

This issue calls for improving code coverage of the main library.

A code coverage report was created by executing cabal test --enable-coverage lsm-tree:lsm-tree-test on the jeltsch/unsliced-keys-in-ordinary-indexes branch as of 28 March 2025, that is, on commit dd6b71c.

The individual coverage deficits of all modules in the main library where examined. All non-trivial cases of missing coverage are listed below. Each case is described by either of the following:

• A situation that never occurred, which led to code not being executed
• A value that was never used (in which case the description contains the phrase “never used”)

Coverage deficits of the following kinds were considered trivial and are therefore not mentioned here:

• Derived class instantiations
• Instantiations of NFData
• Field selectors
• Error message strings or parts thereof
• Deliberately unused values¹ (where it was clear that they are deliberately unused)
• Explicit ()

Data.Arena

• scrambleArena
  • Non-empty free list
• newBlockWithFree
  • Non-empty free list

Data.Map.Range

• rangeLookup
  • Unbounded in at least one direction
• evalLowerBound
  • Exclusive lower bound

Database.LSMTree

• Bifunctor LookupResult
  • Never used
• Bifunctor (QueryResult k)
  • Never used
• rangeLookup
  • Resolver never used
• withCursor
  • Never used
• withCursorAtOffset
  • Never used
• readCursor
  • Resolver never used
• retrieveBlobs
  • Invalid blob reference
• unions
  • Table type mismatch

Database.LSMTree.Common

Nothing

Database.LSMTree.Internal

• All trace messages never used
• withOpenSession
  • Session is closed
• openSession
  • Unexected error when acquiring session file lock
  • Session directory locked with tryLockFile returning Nothing
  • Registry never used for restoring session
  • Active directory never used when removing it in session creation
  • Snapshots directory never used when removing it in session creation
  • Corrupted snapshots directory when restoring session
  • Non-empty active directory when restoring session
  • Session already closed when closing session
  • Rollback for cursor list acquisition when closing session
  • Non-empty list of cursors when closing session
  • Rollback for table list acquisition when closing session
• newEmptyTableContent
  • Registry never used for creating levels cache
• rangeLookup
  • Resolver never used
  • Multiple chunks
• readCursor
  • Resolver never used
• readCursorWhile
  • Resolver never used
• createSnapshot
  • Named snapshot directory never used when rolling back snapshot directory creation
• openSnapshot
  • Wrong table type
  • Resolver never used when opening write buffer
• wrapFileCorruptedErrorAsSnapshotCorruptedError
  • Ordinary action registry abort (ExitCaseAbort)
  • Commit action registry error
  • Unmentioned exception
• doesSnapshotExist
  • Never used
• listSnapshots
  • Alleged snapshot directory not being a directory
• unions
  • Table session mismatch
  • Session closed
  • Unmodified session state after creation of unions table never used
• writeBufferToNewRun
  • Level number 1 never used
• matchSessions
  • Session root mismatch
• supplyUnionCredits
  • Union level denotation never used

Database.LSMTree.Internal.Assertions

• fromIntegralChecked
  • Conversion error found

Database.LSMTree.Internal.BitMath

• mod2
  • Never used
• ceilDiv2
  • Never used
• mod4
  • Never used
• div16
  • Never used
• mod16
  • Never used
• mul16
  • Never used
• divPageSize
  • Never used
• modPageSize
  • Never used

Database.LSMTree.Internal.BlobFile

• openBlobFile
  • Error when opening the file

Database.LSMTree.Internal.BlobRef

• deRefWeakBlobRef
  • Invalid reference

Database.LSMTree.Internal.BloomFilter

• bloomFilterFromSBS
  • Wrong endianness
  • Bloom filter too large
  • Byte array too large for components

Database.LSMTree.Internal.BloomFilterQuery1

• Show RunIxKeyIx
  • Never used

Database.LSMTree.Internal.BloomFilterQuery2

• All assertion properties never used
• alignmentOfType# @CandidateProbe
  • Never used
• indexOffAddr# @CandidateProbe
  • Never used
• Show CandidateProbe
  • Never used

Database.LSMTree.Internal.ByteString

• tryCheapToShort
  • Never used
• tryGetByteArray
  • Non-zero offset into byte array
  • Contents referenced by a MallocPtr
  • Contents referenced by a PlainForeignPtr
  • Contents referenced by a FinalPtr
• unsafePinnedByteArrayToByteString
  • Byte array not pinned
  • Contents pointer never used

Database.LSMTree.Internal.CRC32C

• hGetExactlyCRC32C_SBS
  • Contents pointer never used
• hGetAllCRC32C'
  • Non-positive chunk size
  • Contents pointer of internally used byte string never used

Database.LSMTree.Internal.ChecksumHandle

Nothing

Database.LSMTree.Internal.Chunk

Nothing

Database.LSMTree.Internal.Config

• runParamsForLevel
  • Level number never used
• Semigroup TableConfigOverride
  • Never used
• Monoid TableConfigOverride
  • Never used
• configOverrideDiskCachePolicy
  • Never used
• bloomFilterAllocForLevel
  • FPR request
• diskCachePolicyForLevel
  • Caching from a given level downwards

Database.LSMTree.Internal.Cursor

• readEntriesWhile
  • Mupsert with a key that has other entries

Database.LSMTree.Internal.Entry

• hasBlob
  • Never used
• onBlobRef
  • Never used
• bifoldMap @Entry
  • Blob reference not used when inserting with blob
• combineMaybe
  • Never used

Database.LSMTree.Internal.IncomingRun

• nominalDebtAsCredits
  • Never used
• supplyCreditsIncomingRun
  • Level number never used when computing threshold
• depositNominalCredits
  • Previous nominal credits never used
• immediatelyCompleteIncomingRun
  • Level number never used when supplying credits

Database.LSMTree.Internal.Index

Nothing

Database.LSMTree.Internal.Index.Compact

• search
  • Empty index
  • Sequence of large-entry pages and pages with clashes without preceding pages found
  • Search key belongs to the second or later page in a series of clashing pages²
• hasClashes
  • Never used
• toLBS
  • Never used
• putBitVec
  • Bit vector not byte-aligned
• fromSBS
  • Wrong endianness
  • Number of pages not representable as Int value
  • Number of entries not representable as Int value
  • Byte array too large for components
• checkedPrimVec
  • Negative offset
• checkedBitVec
  • Negative offset
• bitIndexFromToRev
  • No upper bound
• vectorLowerBound
  • No lower bound
• vectorUpperBound
  • Exclusive upper bound

Database.LSMTree.Internal.Index.CompactAcc

Nothing

Database.LSMTree.Internal.Index.Ordinary

• fromSBS
  • Wrong endianness
  • Number of entries not representable as Int value

Database.LSMTree.Internal.Index.OrdinaryAcc

Nothing

Database.LSMTree.Internal.Lookup

• intraPageLookupsOn
  • Combining of entries never used (two occurrences)
  • Byte count discrepancy

Database.LSMTree.Internal.Merge

• abort
  • Implicitly closed merge
  • Explicitly closed merge
• complete
  • Ongoing merge
  • Implicitly closed merge
  • Explicitly closed merge
• stepsToCompletion
  • Never used
• steps
  • Completed merge
  • Implicitly closed merge
  • Explicitly closed merge
• doStepsLevel
  • Readers drained when handling mupdate
  • Readers drained when dropping remaining entries of the same key

Database.LSMTree.Internal.MergeSchedule

• All trace messages never used
• mkLevelsCache
  • Reference release operation never used in rollback for duplicating runs
• iforLevelM_
  • Level number never used by consumer
• flushWriteBuffer
  • Empty table write buffer
  • Level number 1 never used
• addRunToLevels
  • Level number never used when immediately completing incoming run
• mergingRunParamsForLevel
  • Regular level specification never used
• maxRunSize
  • Negative level number
• mergeTypeForLevel
  • Last-level denotation never used
• supplyCredits
  • Level numbers never used

Database.LSMTree.Internal.MergingRun

• new
  • Empty new merge
• newCompleted
  • Error handler never used
• unsafeNew
  • Table too large
• atomicModifyInt
  • CAS looping
• supplyCreditsAbsolute
  • Information on supplied credits never used (two values)
• performMergeSteps
  • Merge completed
• completeMerge
  • Merge completed
• expectCompleted
  • Merge maybe completed
  • Merge ongoing

Database.LSMTree.Internal.MergingTree

• expectCompleted
  • Ongoing tree merge
  • Pending tree merge

Database.LSMTree.Internal.MergingTree.Lookup

• mkLookupNode
  • One lookup tree
• mergeLookupAcc
  • Resolver never used when merging levels
• buildLookupTree
  • Reference release operation never used in rollback for duplicating runs (two occurrences)
  • Pending level merge with no merging runs but a union merge

Database.LSMTree.Internal.Page

Nothing

Database.LSMTree.Internal.PageAcc

Nothing

Database.LSMTree.Internal.PageAcc1

• singletonPage
  • Deletion

Database.LSMTree.Internal.Paths

• isValidSnapshotName
  • String contains a character that is neither a lowercase Latin letter nor a digit
• toSnapshotName
  • String is not a valid snapshot name
• pure @ForRunFiles
  • Never used

Database.LSMTree.Internal.Primitive

Nothing

Database.LSMTree.Internal.Range

Nothing

Database.LSMTree.Internal.RawBytes

• IsList RawBytes
  • Never used
• unpack
  • Never used
• unsafeFromByteString
  • Byte array fetching unsuccessful

Database.LSMTree.Internal.RawOverflowPage

Nothing

Database.LSMTree.Internal.RawPage

• getRawPageIndexKey
  • No index

Database.LSMTree.Internal.Run

• Show (Run m h)
  • Never used
• runFsPathsNumber
  • Never used
• mkRawBlobRef
  • Never used
• openFromDisk
  • Invalid file (three occurrences)
  • Unexpected checksum

Database.LSMTree.Internal.RunAcc

• addKeyOp
  • Chunks emmitted by small key/op addition with page emission never used

Database.LSMTree.Internal.RunBuilder

Nothing

Database.LSMTree.Internal.RunNumber

Nothing

Database.LSMTree.Internal.RunReader

Nothing

Database.LSMTree.Internal.RunReaders

• Eq (ReadCtx m h)
  • Never used
• nextReadCtx
  • Reinstantiated empty key/op buffer never used

Database.LSMTree.Internal.Serialise

• sizeofKey64
  • Never used
• sizeofValue16
  • Never used
• sizeofValue64
  • Never used
• serialisedValue
  • Never used
• SerialisedBlob
  • Never used (at least not in expressions)
• serialisedBlob
  • Never used

Database.LSMTree.Internal.Serialise.Class

• serialiseKeyMinimalSize
  • Never used
• requireBytesExactly
  • Unexpected number of bytes
• deserialiseKey @Word64
  • Unexpected number of bytes
• deserialiseValue @Word64
  • Unexpected number of bytes
• serialiseValue @Void
  • Never used
• deserialiseValue @Void
  • Never used

Database.LSMTree.Internal.Snapshot

• fromSnapMergingTree
  • Completed tree merge
  • Pending level merge
• snapshotWriteBuffer
  • Rollback for write buffer writing
• openWriteBuffer
  • Resolver never used
• fromSnapLevels
  • Level number never used
• fromSnapMergingRun
  • Error handler never used

Database.LSMTree.Internal.Snapshot.Codec

• prettySnapshotVersion
  • Never used
• readFileSnapshotMetaData
  • Invalid file
• decodeSnapshotMetaData
  • Exception
• decode @(Versioned a)
  • Incompatible snapshot format version
• decode @SnapshotVersion
  • Unknown snapshot format version
• decodeVersioned @SnapshotTableType
  • Unexpected tag
• decodeVersioned @SnapshotRun
  • Unexpected combination of list length and tag
• decodeVersioned @MergePolicy
  • Unexpected tag
• decodeVersioned @SizeRation
  • Not 4
• decodeVersioned @WriteBufferAlloc
  • Unexpected tag
• decodeVersioned @RunParams
  • Unexpected combination of list length and tag
• decodedVersion @RunDataCaching
  • Unexpected tag
• decodedVersion @IndexType
  • Unexpected tag
• decodedVersion @RunBloomFilterAlloc
  • Unexpected combination of list length and tag
• decodedVersion @BloomFilterAlloc
  • Unexpected combination of list length and tag
• decodedVersion @FencePointerIndex
  • Unexpected tag
• decodedVersion @DiskCachePolicy
  • Unexpected combination of list length and tag
• decodedVersion @MergeSchedule
  • Unexpected tag
• decodedVersion @SnapIncomingRun
  • Unexpected combination of list length and tag
• decodedVersion @MergePolicyForLevel
  • Unexpected tag
• decodedVersion @SnapMergingRun
  • Unexpected combination of list length and tag
• decodedVersion @LevelMergeType
  • Unexpected tag
• decodedVersion @TreeMergeType
  • Unexpected tag
• decodedVersion @SnapMergingTreeState
  • Unexpected combination of list length and tag
• decodedVersion @SnapPendingMerge
  • Unexpected combination of list length and tag
• decodedVersion @SnapPreExistingRun
  • Unexpected combination of list length and tag

Database.LSMTree.Internal.StrictArray

Nothing

Database.LSMTree.Internal.UniqCounter

Nothing

Database.LSMTree.Internal.Unsliced

• unsafeMakeUnsliced
  • Never used
• unsafeMakeUnslicedKey
  • Never used
• Show (Unsliced SerialisedKey)
  • Never used

Database.LSMTree.Internal.Vector

• mapMStrict
  • Never used
• imapMStrict
  • Never used
• zipWithStrict
  • Never used

Database.LSMTree.Internal.Vector.Growing

• new
  • Non-positive buffer size
• append
  • Length overflow
  • Only one possible new buffer size
  • No possible new buffer size

Database.LSMTree.Internal.WriteBuffer

• fromList
  • Never used
• lookups
  • Never used
• rangeLookups
  • Never used
• convertRange
  • Never used

Database.LSMTree.Internal.WriteBufferBlobs

Nothing

Database.LSMTree.Internal.WriteBufferReader

• readWriteBuffer
  • Resolver never used
• new
  • Error handler never used (two occurrences)

Database.LSMTree.Internal.WriteBufferWriter

• unsafeFinalise
  • Result never used

Database.LSMTree.Monoidal

• withTable
  • Never used
• new
  • Never used
• close
  • Never used
• lookups
  • Never used
• rangeLookup
  • Never used
• withCursor
  • Never used
• withCursorAtOffset
  • Never used
• newCursor
  • Never used
• newCursorAtOffset
  • Never used
• closeCursor
  • Never used
• readCursor
  • Never used
• updates
  • Never used
• inserts
  • Never used
• deletes
  • Never used
• mupserts
  • Never used
• createSnapshot
  • Never used
• openSnapshot
  • Never used
• duplicate
  • Never used
• union
  • Never used
• unions
  • Never used
• remainingUnionDebt
  • Never used
• supplyUnionCredits
  • Never used
• resolve
  • Never used

Database.LSMTree.Normal

• withTable
  • Never used
• new
  • Never used
• close
  • Never used
• Bifunctor LookupResult
  • Never used
• lookups
  • Never used
• Bifunctor (QueryResult k)
  • Never used
• rangeLookup
  • Never used
• withCursor
  • Never used
• withCursorAtOffset
  • Never used
• newCursor
  • Never used
• newCursorAtOffset
  • Never used
• closeCursor
  • Never used
• readCursor
  • Never used
• toNormalQueryResult
  • Never used
• updates
  • Never used
• inserts
  • Never used
• deletes
  • Never used
• retrieveBlobs
  • Never used
• createSnapshot
  • Never used
• openSnapshot
  • Never used
• duplicate
  • Never used
• union
  • Never used
• unions
  • Never used
• remainingUnionDebt
  • Never used
• supplyUnionCredits
  • Never used

Footnotes

1. An example is the index argument in the second alternative of Database.LSMTree.Internal.Index.finalLBS, which is not used by the underlying function Database.LSMTree.Internal.Index.Ordinary.finalLBS. ↩

2. The existence of this case in connection with the previous one suggests that there might be no clashes at all. ↩

[jeltsch]

For further details see the machine-generated report.

[jeltsch]

As we agreed outside of GitHub, checking the coverage of the merge scheduling code should be given priority at this point. Concretely, the following modules should be inspected:

• Database.LSMTree.Internal.IncomingRun
• Database.LSMTree.Internal.Lookup
• Database.LSMTree.Internal.MergeSchedule
• Database.LSMTree.Internal.MergingRun
• Database.LSMTree.Internal.MergingTree
• Database.LSMTree.Internal.MergingTree.Lookup

@jorisdral said that he found no concerning coverage issues in these modules but some in Database.LSMTree.Internal.Snapshot, namely the ones in fromSnapMergingTree.

I reran the test suite now with more test cases for the QuickCheck tests in the following modules:

• Test.Database.LSMTree.Generators
• Test.Database.LSMTree.Internal.Lookup
• Test.Database.LSMTree.Internal.MergingRun
• Test.Database.LSMTree.Internal.MergingTree
• Test.Database.LSMTree.Internal.Snapshot.Codec

When increasing the number of test cases per test from 100 to 1,000, the “completed tree merge” case in fromSnapMergingTree became covered. When increasing that number further to 10,000, then additionally the “pending level merge” case became partly covered.

@jorisdral, @mheinzel, could you please take a look at the concrete coverage of fromSnapMergingTree in the coverage report for 10,000 test cases per test and tell me whether you consider the remaining deficits problematic?

[jeltsch]

As we agreed outside of GitHub, checking the coverage of the merge scheduling code should be given priority at this point. Concretely, the following modules should be inspected:

• Database.LSMTree.Internal.IncomingRun
• Database.LSMTree.Internal.Lookup
• Database.LSMTree.Internal.MergeSchedule
• Database.LSMTree.Internal.MergingRun
• Database.LSMTree.Internal.MergingTree
• Database.LSMTree.Internal.MergingTree.Lookup

@jorisdral said that he found no concerning coverage issues in these modules […].

I’ve marked the respective items in the issue description as resolved now.

[jeltsch]

Since the modules that I had previously marked as resolved contain coverage deficits that not all of us consider surely harmless and @recursion-ninja is going to have a fresh look at test coverage, I removed all the check marks in the issue description above.

[recursion-ninja]

I looked through the all sites in all the functions listed by @jeltsch regarding the code overage of the lsm-tree:lsm-tree-test test suite. I think most of the execution paths of the code-base which were not covered by the test suite were either obviously safe or of dubious value to add test coverage for. However there were a few that I thought were worth adding coverage for.

They fall into these broad categories:

1. Ensure non-trivial data-types satisfy type-class laws.
2. Cover all major execution paths of functions exposed through library's the public API
3. Cover all execution paths related to core database functionality

For brevity, I have included below the subset of reported code coverage sites that I think we should add coverage for in the lsm-tree:lsm-tree-test` .

Data.Map.Range

• rangeLookup
  • Unbounded in at least one direction
• evalLowerBound
  • Exclusive lower bound

Database.LSMTree

• Bifunctor LookupResult
  • Never used
• Bifunctor (QueryResult k)
  • Never used
• rangeLookup
  • Resolver never used
• withCursor
  • Never used
• withCursorAtOffset
  • Never used
• readCursor
  • Resolver never used

Database.LSMTree.Common

Nothing

Database.LSMTree.Internal

• rangeLookup
  • Resolver never used
  • Multiple chunks

Database.LSMTree.Internal.Config

• Semigroup TableConfigOverride
  • Never used
• Monoid TableConfigOverride
  • Never used

Database.LSMTree.Internal.Index.Compact

• toLBS
  • Never used

Database.LSMTree.Internal.Merge

• doStepsLevel
  • Readers drained when handling mupdate

Database.LSMTree.Internal.MergingRun

• expectCompleted
  • Merge maybe completed
  • Merge ongoing

Database.LSMTree.Internal.Paths

• pure @ForRunFiles
  • Never used

Database.LSMTree.Internal.Snapshot

• fromSnapMergingTree
  • Completed tree merge
  • Pending level merge

Database.LSMTree.Monoidal

• withTable
  • Never used
• new
  • Never used
• close
  • Never used
• lookups
  • Never used
• rangeLookup
  • Never used
• withCursor
  • Never used
• withCursorAtOffset
  • Never used
• newCursor
  • Never used
• newCursorAtOffset
  • Never used
• closeCursor
  • Never used
• readCursor
  • Never used
• updates
  • Never used
• inserts
  • Never used
• deletes
  • Never used
• mupserts
  • Never used

Database.LSMTree.Normal

• withTable
  • Never used
• new
  • Never used
• close
  • Never used
• Bifunctor LookupResult
  • Never used
• lookups
  • Never used
• Bifunctor (QueryResult k)
  • Never used
• rangeLookup
  • Never used
• withCursor
  • Never used
• withCursorAtOffset
  • Never used
• newCursor
  • Never used
• newCursorAtOffset
  • Never used
• closeCursor
  • Never used
• readCursor
  • Never used
• updates
  • Never used
• inserts
  • Never used
• deletes
  • Never used

[jorisdral]

I should point out that the public API has changed quite a bit since this coverage report was generated. For example, the normal and monoidal modules do not exist anymore. So it's probably useful to rerun the tests with coverage output enabled on latest main

[recursion-ninja]

@joris, definitely agreed and already initiated. I was using the prior list generated by @jeltsch as an an initial guide to get myself familiar with the coverage situation and I think that it was helpful in identifying the categories worthy of adding coverage to.