hub.darcs.net :: dolio -> vector-algorithms -> issue

#8Tim.sort is unsafe

coopercm

compiling vector with unsafechecks: true results in the following out of bounds exception

Prelude> import qualified Data.Vector.Unboxed as U
Prelude U> xs :: [(Double, Int)] <- read <$> readFile "bust_sort.txt"
Prelude U> import qualified Data.Vector.Algorithms.Tim as Tim
Prelude U Tim> U.modify Tim.sort (U.fromList xs)
*** Exception: ./Data/Vector/Generic/Mutable.hs:721 (unsafeRead): index out of bounds (-1,313)
CallStack (from HasCallStack):
  error, called at ./Data/Vector/Internal/Check.hs:87:5 in vector-0.11.0.0-870I7k04VpECBZVwLXe120:Data.Vector.Internal.Check

• coopercmFri Nov 11 03:00:20 UTC 2016

  bust_sort.txt: http://pastebin.com/K3HfMj1Z

• coopercmWed Nov 16 04:13:22 UTC 2016

  some hints acquired by turning off all inline pragmas and recompiling with -O0 and call stacks:

    Data.Vector.Algorithms.Tim.mergeHi.iter (src/Data/Vector/Algorithms/Tim.hs:(295,2)-(322,70))
    Data.Vector.Algorithms.Tim.mergeHi (src/Data/Vector/Algorithms/Tim.hs:(285,1)-(322,70))
    Data.Vector.Algorithms.Tim.merge (src/Data/Vector/Algorithms/Tim.hs:(338,1)-(351,24))
    Data.Vector.Algorithms.Tim.sortBy.performMerges (src/Data/Vector/Algorithms/Tim.hs:(134,2)-(143,46))
    Data.Vector.Algorithms.Tim.sortBy.iter (src/Data/Vector/Algorithms/Tim.hs:(124,2)-(132,42))
    Data.Vector.Algorithms.Tim.sortBy (src/Data/Vector/Algorithms/Tim.hs:(118,1)-(146,39))
    Main.main (foo.hs:(5,1)-(7,43))

• coopercmWed Nov 16 04:22:46 UTC 2016

  this is wrong: http://hub.darcs.net/dolio/vector-algorithms/browse/src/Data/Vector/Algorithms/Tim.hs#318 since the invariant is i >= 0 not i >= 1

• coopercmWed Nov 16 04:27:09 UTC 2016

  possible fix:

  @@ -292,13 +292,14 @@
    gt  a b = cmp a b == GT
    gte a b = cmp a b /= LT
    tmpBufLen = u - m
  - iter _ _ j _ _ _ _ _ | j < 0 = return ()
  - iter tmpBuf i j _ _ _ _ _ | i < l = do
  + iter _ _ j _ _ _ _ _ | j <= 0 = return ()
  + iter tmpBuf i j _ _ _ _ _ | i <= l = do