fromList causes segfault if list doesn't contain rows*columns elements

[ttesmer]

Segmentation Fault

fromList rows cols list

The above causes a segfault and crashes the program if rows*cols > (1+length list). This is bad because the compiler does not catch the exception and so the program crashes while running and leaves no trace of where or why the error occured. I understand that the documentation says that fromList has to have a list with rows*cols amount of elements but there should still be an error message to determine where this error occured and why. This should preferrably happen at compile time, not while the program is running.

Reproduce

In ghci:

λ> import Data.Matrix
λ> fromList 2 2 [1,2,3] -- this works
┌     ┐
│ 1 2 │
│ 3   │
└     ┘
λ> fromList 2 2 [1,2] -- this doesn't
┌     ┐
│ 1 2 │
│   [1]    54 segmentation fault  ghci

Like I said, this becomes a huge problem once you define multiple matrices in your program and perhaps even change their shape etc. In ghci you can easily see where the problem occured but in a normal, compiled .hs file, you'll need tons of print statements just to see which matrix caused the error.

[Daniel-Diaz]

Hi! Thanks for reporting this issue, and sorry for my late reply.

I was a bit confused as to why the segfault was happening, but when I tried some stuff in GHCi I was left even more confused:

Prelude> import Data.Matrix

Prelude Data.Matrix> getElem 1 1 $ fromList 2 2 [1,2,3]
1

Prelude Data.Matrix> getElem 2 2 $ fromList 2 2 [1,2,3]
*** Exception: Data.Vector.Mutable: uninitialised element
CallStack (from HasCallStack):
  error, called at ./Data/Vector/Mutable.hs:188:17 in vector-0.12.0.2-H1Eu1OCXL0L9y980iV8EwU:Data.Vector.Mutable

Prelude Data.Matrix> getElem 2 2 $ fmap show $ fromList 2 2 [1,2,3]
""

Prelude Data.Matrix> getElem 1 1 $ fromList 2 2 [1,2]
1

Prelude Data.Matrix> getElem 2 2 $ fromList 2 2 [1,2]
*** Exception: Data.Vector.Mutable: uninitialised element
CallStack (from HasCallStack):
  error, called at ./Data/Vector/Mutable.hs:188:17 in vector-0.12.0.2-H1Eu1OCXL0L9y980iV8EwU:Data.Vector.Mutable

Prelude Data.Matrix> getElem 2 2 $ fmap show $ fromList 2 2 [1,2]
"Segmentation fault (core dumped)

Wat? Where does that empty string even come from? And why does the segfault occur only after show is applied?

[ttesmer]

Hi @Daniel-Diaz, thank you for answering!

I was a bit confused as to why the segfault was happening, but when I tried some stuff in GHCi I was left even more confused:

First off, I found out where the segfault is coming from. Relevant here is that getElem calls safeGet. However, safeGet is actually unsafe if the size of the matrix is inconsistent with the actual length of the vector. This is because safeGet only checks these conditions:

 -- | Variant of 'getElem' that returns Maybe instead of an error.
 safeGet :: Int -> Int -> Matrix a -> Maybe a
 safeGet i j a@(M n m _ _ _ _)
   | i > n || j > m || i < 1 || j < 1 = Nothing
   | otherwise = Just $ unsafeGet i j a

So the function only considers whether the index is too large or too little for the matrix. But with fromList, n and m can be inconsistent with the size of the content in the matrix. If that is the case, then safeGet calls unsafeGet, which in turn calls V.unsafeIndex with a too small vector, which won't work:

λ> import Data.Vector as V
λ> let vec = V.fromListN (2*2) [1,2] 
λ> V.unsafeIndex vec 3
[1]    6703 segmentation fault

(The above doesn't actually work for me in GHCi, but in a compiled file it does.)
This is the unsafeIndex implementation as of vector-0.12.3.1 (from here):

-- | /O(1)/ Unsafe indexing without bounds checking
unsafeIndex :: Vector v a => v a -> Int -> a
{-# INLINE_FUSED unsafeIndex #-}
unsafeIndex v i = UNSAFE_CHECK(checkIndex) "unsafeIndex" i (length v)
                $ unId (basicUnsafeIndexM v i)

So this UNSAFE_CHECK C++ header is causing the segfault. I looked into it and they removed this header from their file in a recent commit and changed the unsafeIndex function accordingly as well.

However, as of vector-0.12.3.1, these changes are not yet in the Cabal package.

Wat? Where does that empty string even come from?

I don't really know, but the same thing can be expressed using only Data.Vector:

λ> import Data.Vector as V
λ> let vec = V.map show $ V.fromListN (2*2) [1,2,3]
λ> V.unsafeIndex vec 3 
""

So as to where it's coming from: it's gotta be the mixture of V.map and V.unsafeIndex. Also odd that V.maping any other function causes a segfault (e.g. V.map id). Only show seems to be able to work on the "fourth" (non-existent) element.

And why does the segfault occur only after show is applied?

Not sure but the fromList of Data.Matrix uses V.fromListN, not V.fromList. If you call it with V.fromList instead, there's no *** Exception: Data.Vector.Mutable: uninitialised element error, but a segfault:

λ> V.unsafeIndex (V.fromListN (2*2) [1,2]) 3
*** Exception: Data.Vector.Mutable: uninitialised element. If you are trying to compact a vector, use the 'Data.Vector.force' function to remove uninitialised elements from the underlying array.
λ> V.unsafeIndex (V.fromList [1,2]) 3
4294967298
λ> V.unsafeIndex (V.fromList [1,2]) 3
[1]    5267 segmentation fault  ghci

I have no idea why it's spitting out that number first and only segfaults the second time. I've gotten a ton of weird results while testing this, but if I do the same thing in a compiled Haskell file I get the segfault everytime.

So it might have something to do with the implementation of V.fromListN.

Other Solutions

Instead of just adding an error function to fromList, there could be a condition in safeGet to check if n*m > V.length v (v would have to be made explicit in the matrix argument). However, then the error output would be something like

λ> getElem 2 2 $ fromList 2 2 [1,2,3]
*** Exception: getElem: Trying to get the (2,2) element from a 2x2 matrix.
CallStack (from HasCallStack):
  error, called at ./Data/Matrix.hs:451:6 in matrix-0.3.6.2-691jJV8ZQdVAa99Wk2ZSCf:Data.Matrix

which not only makes no sense when reading it, but also does not help in understanding that in fact the matrix is not 2x2.

Another solution could be to just not use unsafeIndex until the changes in the vector repo make it to the Cabal package. So safeGet would actually be safe if it returned

  | otherwise = v V.! (encode w (i+ro,j+co))

(Or maybe use V.!?, which returns a Maybe, like safeGet does anyways?). I'm not sure why the unsafe indexing was used; I might be missing something.

(BTW, this is my first GitHub contribution so please bear with me (and/or tell me) if any of this is unncessary or something.)