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