Semantics and implementation of move for SoA vectors

[Shimuuar]

It turn out move is not implemented correctly for unboxed vector which use structure of arrays (SoA) representation. Here is move's specification:

If the vectors do not overlap, then this is equivalent to copy. Otherwise, the copying is performed as if the source vector were copied to a temporary vector and then the temporary vector was copied to the target vector.

For tuples move is implemented as pairwise move each underlying array. However it's possible for arrays corresponding to different to alias thus breaking move implementation. As an example:

{-# LANGUAGE ImportQualifiedPost #-}
{-# LANGUAGE TypeFamilies #-}
module MV where

import Control.Monad.Primitive
import Data.Vector.Unboxed qualified as VU
import Data.Vector.Unboxed.Mutable qualified as MVU
import Data.Vector.Generic.Mutable qualified as MVG

-- Reference implementation for move:
moveSpec :: (MVG.MVector v a, PrimMonad m, PrimState m ~ s) => v s a -> v s a -> m ()
moveSpec tgt src = do
 tmp <- MVG.clone src
 MVG.copy tgt tmp

problemSoA :: IO ()
problemSoA = do
 putStrLn "Reference impl"
 testMove moveSpec
 putStrLn "\nmove"
 testMove MVU.move
 where
 testMove fun = do
 va <- MVU.generate 4 id
 vb <- MVU.generate 4 (+100)
 let src = MVU.zip va vb
 dst = MVU.zip vb va
 print . ("src = "++) . show =<< VU.freeze src
 print . ("dst = "++) . show =<< VU.freeze dst
 fun dst src
 print . ("dst = "++) . show =<< VU.freeze dst

produces

Reference impl
"src = [(0,100),(1,101),(2,102),(3,103)]"
"dst = [(100,0),(101,1),(102,2),(103,3)]"
"dst = [(0,100),(1,101),(2,102),(3,103)]"

move
"src = [(0,100),(1,101),(2,102),(3,103)]"
"dst = [(100,0),(101,1),(102,2),(103,3)]"
"dst = [(0,0),(1,1),(2,2),(3,3)]"

Which is obviously breaks specification. However I don't see any easy fix. We'll need to check all underlying arrays for overlap and we don't have machinery for that