Reduce the scope and complexity of the code that uses unsafe.
Make the utility functions public so they can be reused by other matrix-like representations.
Reducing scope of unsafe
The internals of AdjMatrix use unsafe code for two reasons:
The possibility to "detach" edge presence information from the edge data, so that implementation of Neighbors does not cause "E does not live long enough" error.
A space reduction, where Vec<Option<E>> would need extra byte(s) for every item in a lot of practical cases (where a memory layout optimization would not help). Although the real performance effect was not benchmarked!
To be more confident in the correctness as well as reduce stress while making changes in the future, the scope and complexity of the code using unsafe should be reduced.
There should be a new Vec-like type encapsulating the BitVec, Vec<MaybeUninit<T>> pair. The API surface should be as minimal as possible while still supporting the needs of the AdjMatrix implementation. And it should still be possible to get reference to the underlying BitVec which does not have any generics. Since the implementation will not need to care about anything matrix-related, the implementation should be more straightforward and much easier to reason about. Anyway, miri should be used to ensure correctness.
Exposing utility functions
There are some useful functions that help with storing matrix-like data in a linear vector, namely:
size_of -- calculating needed size of the vector given number of vertices and graph being directed or undirected
resize -- Resizing the vector to a new size, correctly moving existing edge data. Although this function needs to be made edge container agnostic.
index & coords -- Functions that can convert edge coordinates (source vertex and destination vertex) to the vector index and vice versa.
These should be publicly available so they can be used by external implementations.
The main two goals of the refactoring are:
unsafe.Reducing scope of unsafe
The internals of
AdjMatrixuse unsafe code for two reasons:Neighborsdoes not cause "Edoes not live long enough" error.Vec<Option<E>>would need extra byte(s) for every item in a lot of practical cases (where a memory layout optimization would not help). Although the real performance effect was not benchmarked!To be more confident in the correctness as well as reduce stress while making changes in the future, the scope and complexity of the code using unsafe should be reduced.
There should be a new
Vec-like type encapsulating theBitVec,Vec<MaybeUninit<T>>pair. The API surface should be as minimal as possible while still supporting the needs of theAdjMatriximplementation. And it should still be possible to get reference to the underlyingBitVecwhich does not have any generics. Since the implementation will not need to care about anything matrix-related, the implementation should be more straightforward and much easier to reason about. Anyway, miri should be used to ensure correctness.Exposing utility functions
There are some useful functions that help with storing matrix-like data in a linear vector, namely:
size_of-- calculating needed size of the vector given number of vertices and graph being directed or undirectedresize-- Resizing the vector to a new size, correctly moving existing edge data. Although this function needs to be made edge container agnostic.index&coords-- Functions that can convert edge coordinates (source vertex and destination vertex) to the vector index and vice versa.These should be publicly available so they can be used by external implementations.