integer overflow in replace

[rwbarton]

It's obvious that a lot of care went into properly handling integer overflow in this library. In the spirit of completeness, here is one spot that slipped through the cracks.

replace :: Text -> Text -> Text -> Text
replace needle@(Text _      _      neeLen)
               (Text repArr repOff repLen)
      haystack@(Text hayArr hayOff hayLen)
  | neeLen == 0 = emptyError "replace"
  | L.null ixs  = haystack
  | len > 0     = Text (A.run x) 0 len
  | len < 0     = overflowError "replace"
  | otherwise   = empty
  where
    ixs = indices needle haystack
    len = hayLen - (neeLen - repLen) * L.length ixs
    x = do {- ... -}

The computation of len can overflow to a incorrect but positive value, whereupon the loop will write off the end of the allocated array. On a 64-bit system, you need to have already allocated quite a lot of memory to trigger this overflow (something like 60 GB):

import qualified Data.Text as T

main = print $ T.head $ T.replace
       (T.singleton 'a')
       (T.replicate (2^34+1) (T.singleton 'b'))
       (T.replicate (2^30) (T.singleton 'a'))

On a 32-bit system, you can reduce both exponents above by 16 and then it is quite easy to reproduce the segmentation fault.

[bos]

Thanks for the report. I fixed this and found a faster checked multiply along the way.