Data/ByteString/Char8.hs

   1 {-# OPTIONS_GHC -cpp -fglasgow-exts #-}
   2 --
   3 -- Module      : Data.ByteString.Char8
   4 -- Copyright   : (c) Don Stewart 2006
   5 -- License     : BSD-style
   6 --
   7 -- Maintainer  : dons@cse.unsw.edu.au
   8 -- Stability   : experimental
   9 -- Portability : portable (tested with GHC>=6.4.1 and Hugs 2005)
  10 --
  11
  12 --
  13 -- | Manipulate 'ByteString's using 'Char' operations. All Chars will be
  14 -- truncated to 8 bits. It can be expected that these functions will run
  15 -- at identical speeds to their 'Word8' equivalents in "Data.ByteString".
  16 --
  17 -- More specifically these byte strings are taken to be in the
  18 -- subset of Unicode covered by code points 0-255. This covers
  19 -- Unicode Basic Latin, Latin-1 Supplement and C0+C1 Controls.
  20 --
  21 -- See:
  22 --
  23 --  * <http://www.unicode.org/charts/>
  24 --
  25 --  * <http://www.unicode.org/charts/PDF/U0000.pdf>
  26 --
  27 --  * <http://www.unicode.org/charts/PDF/U0080.pdf>
  28 --
  29 -- This module is intended to be imported @qualified@, to avoid name
  30 -- clashes with "Prelude" functions.  eg.
  31 --
  32 -- > import qualified Data.ByteString.Char8 as B
  33 --
  34
  35 module Data.ByteString.Char8 (
  36
  37         -- * The @ByteString@ type
  38         ByteString,             -- abstract, instances: Eq, Ord, Show, Read, Data, Typeable, Monoid
  39
  40         -- * Introducing and eliminating 'ByteString's
  41         empty,                  -- :: ByteString
  42         singleton,              -- :: Char   -> ByteString
  43         pack,                   -- :: String -> ByteString
  44         unpack,                 -- :: ByteString -> String
  45
  46         -- * Basic interface
  47         cons,                   -- :: Char -> ByteString -> ByteString
  48         snoc,                   -- :: ByteString -> Char -> ByteString
  49         append,                 -- :: ByteString -> ByteString -> ByteString
  50         head,                   -- :: ByteString -> Char
  51         last,                   -- :: ByteString -> Char
  52         tail,                   -- :: ByteString -> ByteString
  53         init,                   -- :: ByteString -> ByteString
  54         null,                   -- :: ByteString -> Bool
  55         length,                 -- :: ByteString -> Int
  56
  57         -- * Transformating ByteStrings
  58         map,                    -- :: (Char -> Char) -> ByteString -> ByteString
  59         reverse,                -- :: ByteString -> ByteString
  60         intersperse,            -- :: Char -> ByteString -> ByteString
  61         transpose,              -- :: [ByteString] -> [ByteString]
  62
  63         -- * Reducing 'ByteString's (folds)
  64         foldl,                  -- :: (a -> Char -> a) -> a -> ByteString -> a
  65         foldl',                 -- :: (a -> Char -> a) -> a -> ByteString -> a
  66         foldl1,                 -- :: (Char -> Char -> Char) -> ByteString -> Char
  67         foldl1',                -- :: (Char -> Char -> Char) -> ByteString -> Char
  68
  69         foldr,                  -- :: (Char -> a -> a) -> a -> ByteString -> a
  70         foldr',                 -- :: (Char -> a -> a) -> a -> ByteString -> a
  71         foldr1,                 -- :: (Char -> Char -> Char) -> ByteString -> Char
  72         foldr1',                -- :: (Char -> Char -> Char) -> ByteString -> Char
  73
  74         -- ** Special folds
  75         concat,                 -- :: [ByteString] -> ByteString
  76         concatMap,              -- :: (Char -> ByteString) -> ByteString -> ByteString
  77         any,                    -- :: (Char -> Bool) -> ByteString -> Bool
  78         all,                    -- :: (Char -> Bool) -> ByteString -> Bool
  79         maximum,                -- :: ByteString -> Char
  80         minimum,                -- :: ByteString -> Char
  81
  82         -- * Building ByteStrings
  83         -- ** Scans
  84         scanl,                  -- :: (Char -> Char -> Char) -> Char -> ByteString -> ByteString
  85         scanl1,                 -- :: (Char -> Char -> Char) -> ByteString -> ByteString
  86         scanr,                  -- :: (Char -> Char -> Char) -> Char -> ByteString -> ByteString
  87         scanr1,                 -- :: (Char -> Char -> Char) -> ByteString -> ByteString
  88
  89         -- ** Accumulating maps
  90         mapAccumL,              -- :: (acc -> Char -> (acc, Char)) -> acc -> ByteString -> (acc, ByteString)
  91         mapAccumR,              -- :: (acc -> Char -> (acc, Char)) -> acc -> ByteString -> (acc, ByteString)
  92         mapIndexed,             -- :: (Int -> Char -> Char) -> ByteString -> ByteString
  93
  94         -- * Generating and unfolding ByteStrings
  95         replicate,              -- :: Int -> Char -> ByteString
  96         unfoldr,                -- :: (a -> Maybe (Char, a)) -> a -> ByteString
  97         unfoldrN,               -- :: Int -> (a -> Maybe (Char, a)) -> a -> (ByteString, Maybe a)
  98
  99         -- * Substrings
 100
 101         -- ** Breaking strings
 102         take,                   -- :: Int -> ByteString -> ByteString
 103         drop,                   -- :: Int -> ByteString -> ByteString
 104         splitAt,                -- :: Int -> ByteString -> (ByteString, ByteString)
 105         takeWhile,              -- :: (Char -> Bool) -> ByteString -> ByteString
 106         dropWhile,              -- :: (Char -> Bool) -> ByteString -> ByteString
 107         span,                   -- :: (Char -> Bool) -> ByteString -> (ByteString, ByteString)
 108         spanEnd,                -- :: (Char -> Bool) -> ByteString -> (ByteString, ByteString)
 109         break,                  -- :: (Char -> Bool) -> ByteString -> (ByteString, ByteString)
 110         breakEnd,               -- :: (Char -> Bool) -> ByteString -> (ByteString, ByteString)
 111         group,                  -- :: ByteString -> [ByteString]
 112         groupBy,                -- :: (Char -> Char -> Bool) -> ByteString -> [ByteString]
 113         inits,                  -- :: ByteString -> [ByteString]
 114         tails,                  -- :: ByteString -> [ByteString]
 115
 116         -- ** Breaking into many substrings
 117         split,                  -- :: Char -> ByteString -> [ByteString]
 118         splitWith,              -- :: (Char -> Bool) -> ByteString -> [ByteString]
 119
 120         -- ** Breaking into lines and words
 121         lines,                  -- :: ByteString -> [ByteString]
 122         words,                  -- :: ByteString -> [ByteString]
 123         unlines,                -- :: [ByteString] -> ByteString
 124         unwords,                -- :: ByteString -> [ByteString]
 125
 126         -- ** Joining strings
 127         join,                   -- :: ByteString -> [ByteString] -> ByteString
 128
 129         -- ** Searching for substrings
 130         isPrefixOf,             -- :: ByteString -> ByteString -> Bool
 131         isSuffixOf,             -- :: ByteString -> ByteString -> Bool
 132         isSubstringOf,          -- :: ByteString -> ByteString -> Bool
 133         findSubstring,          -- :: ByteString -> ByteString -> Maybe Int
 134         findSubstrings,         -- :: ByteString -> ByteString -> [Int]
 135
 136         -- * Searching ByteStrings
 137
 138         -- ** Searching by equality
 139         elem,                   -- :: Char -> ByteString -> Bool
 140         notElem,                -- :: Char -> ByteString -> Bool
 141
 142         -- ** Searching with a predicate
 143         find,                   -- :: (Char -> Bool) -> ByteString -> Maybe Char
 144         filter,                 -- :: (Char -> Bool) -> ByteString -> ByteString
 145 --      partition               -- :: (Char -> Bool) -> ByteString -> (ByteString, ByteString)
 146
 147         -- * Indexing ByteStrings
 148         index,                  -- :: ByteString -> Int -> Char
 149         elemIndex,              -- :: Char -> ByteString -> Maybe Int
 150         elemIndices,            -- :: Char -> ByteString -> [Int]
 151         elemIndexEnd,           -- :: Char -> ByteString -> Maybe Int
 152         findIndex,              -- :: (Char -> Bool) -> ByteString -> Maybe Int
 153         findIndices,            -- :: (Char -> Bool) -> ByteString -> [Int]
 154         count,                  -- :: Char -> ByteString -> Int
 155
 156         -- * Zipping and unzipping ByteStrings
 157         zip,                    -- :: ByteString -> ByteString -> [(Char,Char)]
 158         zipWith,                -- :: (Char -> Char -> c) -> ByteString -> ByteString -> [c]
 159         unzip,                  -- :: [(Char,Char)] -> (ByteString,ByteString)
 160
 161         -- * Ordered ByteStrings
 162         sort,                   -- :: ByteString -> ByteString
 163
 164         -- * Reading from ByteStrings
 165         readInt,                -- :: ByteString -> Maybe (Int, ByteString)
 166         readInteger,            -- :: ByteString -> Maybe (Integer, ByteString)
 167
 168         -- * Low level CString conversions
 169
 170         -- ** Packing CStrings and pointers
 171         packCString,            -- :: CString -> ByteString
 172         packCStringLen,         -- :: CString -> ByteString
 173         packMallocCString,      -- :: CString -> ByteString
 174
 175         -- ** Using ByteStrings as CStrings
 176         useAsCString,           -- :: ByteString -> (CString -> IO a) -> IO a
 177         useAsCStringLen,        -- :: ByteString -> (CStringLen -> IO a) -> IO a
 178
 179         -- * Copying ByteStrings
 180         copy,                   -- :: ByteString -> ByteString
 181         copyCString,            -- :: CString -> IO ByteString
 182         copyCStringLen,         -- :: CStringLen -> IO ByteString
 183
 184         -- * I\/O with @ByteString@s
 185
 186         -- ** Standard input and output
 187         getLine,                -- :: IO ByteString
 188         getContents,            -- :: IO ByteString
 189         putStr,                 -- :: ByteString -> IO ()
 190         putStrLn,               -- :: ByteString -> IO ()
 191         interact,               -- :: (ByteString -> ByteString) -> IO ()
 192
 193         -- ** Files
 194         readFile,               -- :: FilePath -> IO ByteString
 195         writeFile,              -- :: FilePath -> ByteString -> IO ()
 196         appendFile,             -- :: FilePath -> ByteString -> IO ()
 197 --      mmapFile,               -- :: FilePath -> IO ByteString
 198
 199         -- ** I\/O with Handles
 200         hGetLine,               -- :: Handle -> IO ByteString
 201         hGetNonBlocking,        -- :: Handle -> Int -> IO ByteString
 202         hGetContents,           -- :: Handle -> IO ByteString
 203         hGet,                   -- :: Handle -> Int -> IO ByteString
 204         hPut,                   -- :: Handle -> ByteString -> IO ()
 205         hPutStr,                -- :: Handle -> ByteString -> IO ()
 206         hPutStrLn,              -- :: Handle -> ByteString -> IO ()
 207
 208 #if defined(__GLASGOW_HASKELL__)
 209         -- * Low level construction
 210         -- | For constructors from foreign language types see "Data.ByteString"
 211         packAddress,            -- :: Addr# -> ByteString
 212         unsafePackAddress,      -- :: Int -> Addr# -> ByteString
 213 #endif
 214
 215         -- * Utilities (needed for array fusion)
 216 #if defined(__GLASGOW_HASKELL__)
 217         unpackList,
 218 #endif
 219
 220     ) where
 221
 222 import qualified Prelude as P
 223 import Prelude hiding           (reverse,head,tail,last,init,null
 224                                 ,length,map,lines,foldl,foldr,unlines
 225                                 ,concat,any,take,drop,splitAt,takeWhile
 226                                 ,dropWhile,span,break,elem,filter,unwords
 227                                 ,words,maximum,minimum,all,concatMap
 228                                 ,scanl,scanl1,scanr,scanr1
 229                                 ,appendFile,readFile,writeFile
 230                                 ,foldl1,foldr1,replicate
 231                                 ,getContents,getLine,putStr,putStrLn,interact
 232                                 ,zip,zipWith,unzip,notElem)
 233
 234 import qualified Data.ByteString as B
 235 import qualified Data.ByteString.Base as B
 236
 237 -- Listy functions transparently exported
 238 import Data.ByteString (empty,null,length,tail,init,append
 239                        ,inits,tails,reverse,transpose
 240                        ,concat,take,drop,splitAt,join
 241                        ,sort,isPrefixOf,isSuffixOf,isSubstringOf,findSubstring
 242                        ,findSubstrings,copy,group
 243
 244                        ,getLine, getContents, putStr, putStrLn, interact
 245                        ,hGetContents, hGet, hPut, hPutStr, hPutStrLn
 246                        ,hGetLine, hGetNonBlocking
 247                        ,packCString,packCStringLen, packMallocCString
 248                        ,useAsCString,useAsCStringLen, copyCString,copyCStringLen
 249 #if defined(__GLASGOW_HASKELL__)
 250                        ,unpackList
 251 #endif
 252                        )
 253
 254 import Data.ByteString.Base (
 255                         ByteString(..)
 256 #if defined(__GLASGOW_HASKELL__)
 257                        ,packAddress, unsafePackAddress
 258 #endif
 259                        ,c2w, w2c, unsafeTail, isSpaceWord8, inlinePerformIO
 260                        )
 261
 262 import Data.Char    ( isSpace )
 263 import qualified Data.List as List (intersperse)
 264
 265 import System.IO                (openFile,hClose,hFileSize,IOMode(..))
 266 import Control.Exception        (bracket)
 267 import Foreign
 268
 269 #if defined(__GLASGOW_HASKELL__)
 270 import GHC.Base                 (Char(..),unpackCString#,unsafeCoerce#)
 271 import GHC.IOBase               (IO(..),stToIO)
 272 import GHC.Prim                 (Addr#,writeWord8OffAddr#,plusAddr#)
 273 import GHC.Ptr                  (Ptr(..))
 274 import GHC.ST                   (ST(..))
 275 #endif
 276
 277 #define STRICT1(f) f a | a `seq` False = undefined
 278 #define STRICT2(f) f a b | a `seq` b `seq` False = undefined
 279 #define STRICT3(f) f a b c | a `seq` b `seq` c `seq` False = undefined
 280 #define STRICT4(f) f a b c d | a `seq` b `seq` c `seq` d `seq` False = undefined
 281
 282 ------------------------------------------------------------------------
 283
 284 -- | /O(1)/ Convert a 'Char' into a 'ByteString'
 285 singleton :: Char -> ByteString
 286 singleton = B.singleton . c2w
 287 {-# INLINE singleton #-}
 288
 289 -- | /O(n)/ Convert a 'String' into a 'ByteString'
 290 --
 291 -- For applications with large numbers of string literals, pack can be a
 292 -- bottleneck. In such cases, consider using packAddress (GHC only).
 293 pack :: String -> ByteString
 294 #if !defined(__GLASGOW_HASKELL__)
 295
 296 pack str = B.unsafeCreate (P.length str) $ \p -> go p str
 297     where go _ []     = return ()
 298           go p (x:xs) = poke p (c2w x) >> go (p `plusPtr` 1) xs
 299
 300 #else /* hack away */
 301
 302 pack str = B.unsafeCreate (P.length str) $ \(Ptr p) -> stToIO (go p str)
 303   where
 304     go :: Addr# -> [Char] -> ST a ()
 305     go _ []        = return ()
 306     go p (C# c:cs) = writeByte p (unsafeCoerce# c) >> go (p `plusAddr#` 1#) cs
 307
 308     writeByte p c = ST $ \s# ->
 309         case writeWord8OffAddr# p 0# c s# of s2# -> (# s2#, () #)
 310     {-# INLINE writeByte #-}
 311 {-# INLINE [1] pack #-}
 312
 313 {-# RULES
 314     "FPS pack/packAddress" forall s .
 315        pack (unpackCString# s) = B.packAddress s
 316  #-}
 317
 318 #endif
 319
 320 -- | /O(n)/ Converts a 'ByteString' to a 'String'.
 321 unpack :: ByteString -> [Char]
 322 unpack = P.map w2c . B.unpack
 323 {-# INLINE unpack #-}
 324
 325 -- | /O(n)/ 'cons' is analogous to (:) for lists, but of different
 326 -- complexity, as it requires a memcpy.
 327 cons :: Char -> ByteString -> ByteString
 328 cons = B.cons . c2w
 329 {-# INLINE cons #-}
 330
 331 -- | /O(n)/ Append a Char to the end of a 'ByteString'. Similar to
 332 -- 'cons', this function performs a memcpy.
 333 snoc :: ByteString -> Char -> ByteString
 334 snoc p = B.snoc p . c2w
 335 {-# INLINE snoc #-}
 336
 337 -- | /O(1)/ Extract the first element of a ByteString, which must be non-empty.
 338 head :: ByteString -> Char
 339 head = w2c . B.head
 340 {-# INLINE head #-}
 341
 342 -- | /O(1)/ Extract the last element of a packed string, which must be non-empty.
 343 last :: ByteString -> Char
 344 last = w2c . B.last
 345 {-# INLINE last #-}
 346
 347 -- | /O(n)/ 'map' @f xs@ is the ByteString obtained by applying @f@ to each element of @xs@
 348 map :: (Char -> Char) -> ByteString -> ByteString
 349 map f = B.map (c2w . f . w2c)
 350 {-# INLINE map #-}
 351
 352 -- | /O(n)/ The 'intersperse' function takes a Char and a 'ByteString'
 353 -- and \`intersperses\' that Char between the elements of the
 354 -- 'ByteString'.  It is analogous to the intersperse function on Lists.
 355 intersperse :: Char -> ByteString -> ByteString
 356 intersperse = B.intersperse . c2w
 357 {-# INLINE intersperse #-}
 358
 359 -- | 'foldl', applied to a binary operator, a starting value (typically
 360 -- the left-identity of the operator), and a ByteString, reduces the
 361 -- ByteString using the binary operator, from left to right.
 362 foldl :: (a -> Char -> a) -> a -> ByteString -> a
 363 foldl f = B.foldl (\a c -> f a (w2c c))
 364 {-# INLINE foldl #-}
 365
 366 -- | 'foldl\'' is like foldl, but strict in the accumulator.
 367 foldl' :: (a -> Char -> a) -> a -> ByteString -> a
 368 foldl' f = B.foldl' (\a c -> f a (w2c c))
 369 {-# INLINE foldl' #-}
 370
 371 -- | 'foldr', applied to a binary operator, a starting value
 372 -- (typically the right-identity of the operator), and a packed string,
 373 -- reduces the packed string using the binary operator, from right to left.
 374 foldr :: (Char -> a -> a) -> a -> ByteString -> a
 375 foldr f = B.foldr (\c a -> f (w2c c) a)
 376 {-# INLINE foldr #-}
 377
 378 -- | 'foldr\'' is a strict variant of foldr
 379 foldr' :: (Char -> a -> a) -> a -> ByteString -> a
 380 foldr' f = B.foldr' (\c a -> f (w2c c) a)
 381 {-# INLINE foldr' #-}
 382
 383 -- | 'foldl1' is a variant of 'foldl' that has no starting value
 384 -- argument, and thus must be applied to non-empty 'ByteStrings'.
 385 foldl1 :: (Char -> Char -> Char) -> ByteString -> Char
 386 foldl1 f ps = w2c (B.foldl1 (\x y -> c2w (f (w2c x) (w2c y))) ps)
 387 {-# INLINE foldl1 #-}
 388
 389 -- | A strict version of 'foldl1'
 390 foldl1' :: (Char -> Char -> Char) -> ByteString -> Char
 391 foldl1' f ps = w2c (B.foldl1' (\x y -> c2w (f (w2c x) (w2c y))) ps)
 392 {-# INLINE foldl1' #-}
 393
 394 -- | 'foldr1' is a variant of 'foldr' that has no starting value argument,
 395 -- and thus must be applied to non-empty 'ByteString's
 396 foldr1 :: (Char -> Char -> Char) -> ByteString -> Char
 397 foldr1 f ps = w2c (B.foldr1 (\x y -> c2w (f (w2c x) (w2c y))) ps)
 398 {-# INLINE foldr1 #-}
 399
 400 -- | A strict variant of foldr1
 401 foldr1' :: (Char -> Char -> Char) -> ByteString -> Char
 402 foldr1' f ps = w2c (B.foldr1' (\x y -> c2w (f (w2c x) (w2c y))) ps)
 403 {-# INLINE foldr1' #-}
 404
 405 -- | Map a function over a 'ByteString' and concatenate the results
 406 concatMap :: (Char -> ByteString) -> ByteString -> ByteString
 407 concatMap f = B.concatMap (f . w2c)
 408 {-# INLINE concatMap #-}
 409
 410 -- | Applied to a predicate and a ByteString, 'any' determines if
 411 -- any element of the 'ByteString' satisfies the predicate.
 412 any :: (Char -> Bool) -> ByteString -> Bool
 413 any f = B.any (f . w2c)
 414 {-# INLINE any #-}
 415
 416 -- | Applied to a predicate and a 'ByteString', 'all' determines if
 417 -- all elements of the 'ByteString' satisfy the predicate.
 418 all :: (Char -> Bool) -> ByteString -> Bool
 419 all f = B.all (f . w2c)
 420 {-# INLINE all #-}
 421
 422 -- | 'maximum' returns the maximum value from a 'ByteString'
 423 maximum :: ByteString -> Char
 424 maximum = w2c . B.maximum
 425 {-# INLINE maximum #-}
 426
 427 -- | 'minimum' returns the minimum value from a 'ByteString'
 428 minimum :: ByteString -> Char
 429 minimum = w2c . B.minimum
 430 {-# INLINE minimum #-}
 431
 432 -- | /O(n)/ map Char functions, provided with the index at each position
 433 mapIndexed :: (Int -> Char -> Char) -> ByteString -> ByteString
 434 mapIndexed f = B.mapIndexed (\i c -> c2w (f i (w2c c)))
 435 {-# INLINE mapIndexed #-}
 436
 437 -- | The 'mapAccumL' function behaves like a combination of 'map' and
 438 -- 'foldl'; it applies a function to each element of a ByteString,
 439 -- passing an accumulating parameter from left to right, and returning a
 440 -- final value of this accumulator together with the new list.
 441 mapAccumL :: (acc -> Char -> (acc, Char)) -> acc -> ByteString -> (acc, ByteString)
 442 mapAccumL f = B.mapAccumL (\acc w -> case f acc (w2c w) of (acc', c) -> (acc', c2w c))
 443
 444 -- | The 'mapAccumR' function behaves like a combination of 'map' and
 445 -- 'foldr'; it applies a function to each element of a ByteString,
 446 -- passing an accumulating parameter from right to left, and returning a
 447 -- final value of this accumulator together with the new ByteString.
 448 mapAccumR :: (acc -> Char -> (acc, Char)) -> acc -> ByteString -> (acc, ByteString)
 449 mapAccumR f = B.mapAccumR (\acc w -> case f acc (w2c w) of (acc', c) -> (acc', c2w c))
 450
 451 -- | 'scanl' is similar to 'foldl', but returns a list of successive
 452 -- reduced values from the left:
 453 --
 454 -- > scanl f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...]
 455 --
 456 -- Note that
 457 --
 458 -- > last (scanl f z xs) == foldl f z xs.
 459 scanl :: (Char -> Char -> Char) -> Char -> ByteString -> ByteString
 460 scanl f z = B.scanl (\a b -> c2w (f (w2c a) (w2c b))) (c2w z)
 461
 462 -- | 'scanl1' is a variant of 'scanl' that has no starting value argument:
 463 --
 464 -- > scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]
 465 scanl1 :: (Char -> Char -> Char) -> ByteString -> ByteString
 466 scanl1 f = B.scanl1 (\a b -> c2w (f (w2c a) (w2c b)))
 467
 468 -- | scanr is the right-to-left dual of scanl.
 469 scanr :: (Char -> Char -> Char) -> Char -> ByteString -> ByteString
 470 scanr f z = B.scanr (\a b -> c2w (f (w2c a) (w2c b))) (c2w z)
 471
 472 -- | 'scanr1' is a variant of 'scanr' that has no starting value argument.
 473 scanr1 :: (Char -> Char -> Char) -> ByteString -> ByteString
 474 scanr1 f = B.scanr1 (\a b -> c2w (f (w2c a) (w2c b)))
 475
 476 -- | /O(n)/ 'replicate' @n x@ is a ByteString of length @n@ with @x@
 477 -- the value of every element. The following holds:
 478 --
 479 -- > replicate w c = unfoldr w (\u -> Just (u,u)) c
 480 --
 481 -- This implemenation uses @memset(3)@
 482 replicate :: Int -> Char -> ByteString
 483 replicate w = B.replicate w . c2w
 484 {-# INLINE replicate #-}
 485
 486 -- | /O(n)/, where /n/ is the length of the result.  The 'unfoldr'
 487 -- function is analogous to the List \'unfoldr\'.  'unfoldr' builds a
 488 -- ByteString from a seed value.  The function takes the element and
 489 -- returns 'Nothing' if it is done producing the ByteString or returns
 490 -- 'Just' @(a,b)@, in which case, @a@ is the next character in the string,
 491 -- and @b@ is the seed value for further production.
 492 --
 493 -- Examples:
 494 --
 495 -- > unfoldr (\x -> if x <= '9' then Just (x, succ x) else Nothing) '0' == "0123456789"
 496 unfoldr :: (a -> Maybe (Char, a)) -> a -> ByteString
 497 unfoldr f x0 = B.unfoldr (fmap k . f) x0
 498     where k (i, j) = (c2w i, j)
 499
 500 -- | /O(n)/ Like 'unfoldr', 'unfoldrN' builds a ByteString from a seed
 501 -- value.  However, the length of the result is limited by the first
 502 -- argument to 'unfoldrN'.  This function is more efficient than 'unfoldr'
 503 -- when the maximum length of the result is known.
 504 --
 505 -- The following equation relates 'unfoldrN' and 'unfoldr':
 506 --
 507 -- > unfoldrN n f s == take n (unfoldr f s)
 508 unfoldrN :: Int -> (a -> Maybe (Char, a)) -> a -> (ByteString, Maybe a)
 509 unfoldrN n f w = B.unfoldrN n ((k `fmap`) . f) w
 510     where k (i,j) = (c2w i, j)
 511 {-# INLINE unfoldrN #-}
 512
 513 -- | 'takeWhile', applied to a predicate @p@ and a ByteString @xs@,
 514 -- returns the longest prefix (possibly empty) of @xs@ of elements that
 515 -- satisfy @p@.
 516 takeWhile :: (Char -> Bool) -> ByteString -> ByteString
 517 takeWhile f = B.takeWhile (f . w2c)
 518 {-# INLINE takeWhile #-}
 519
 520 -- | 'dropWhile' @p xs@ returns the suffix remaining after 'takeWhile' @p xs@.
 521 dropWhile :: (Char -> Bool) -> ByteString -> ByteString
 522 dropWhile f = B.dropWhile (f . w2c)
 523 #if defined(__GLASGOW_HASKELL__)
 524 {-# INLINE [1] dropWhile #-}
 525 #endif
 526
 527 -- | 'break' @p@ is equivalent to @'span' ('not' . p)@.
 528 break :: (Char -> Bool) -> ByteString -> (ByteString, ByteString)
 529 break f = B.break (f . w2c)
 530 #if defined(__GLASGOW_HASKELL__)
 531 {-# INLINE [1] break #-}
 532 #endif
 533
 534 -- | 'span' @p xs@ breaks the ByteString into two segments. It is
 535 -- equivalent to @('takeWhile' p xs, 'dropWhile' p xs)@
 536 span :: (Char -> Bool) -> ByteString -> (ByteString, ByteString)
 537 span f = B.span (f . w2c)
 538 {-# INLINE span #-}
 539
 540 -- | 'spanEnd' behaves like 'span' but from the end of the 'ByteString'.
 541 -- We have
 542 --
 543 -- > spanEnd (not.isSpace) "x y z" == ("x y ","z")
 544 --
 545 -- and
 546 --
 547 -- > spanEnd (not . isSpace) ps
 548 -- >    ==
 549 -- > let (x,y) = span (not.isSpace) (reverse ps) in (reverse y, reverse x)
 550 --
 551 spanEnd :: (Char -> Bool) -> ByteString -> (ByteString, ByteString)
 552 spanEnd f = B.spanEnd (f . w2c)
 553 {-# INLINE spanEnd #-}
 554
 555 -- | 'breakEnd' behaves like 'break' but from the end of the 'ByteString'
 556 --
 557 -- breakEnd p == spanEnd (not.p)
 558 breakEnd :: (Char -> Bool) -> ByteString -> (ByteString, ByteString)
 559 breakEnd f = B.breakEnd (f . w2c)
 560 {-# INLINE breakEnd #-}
 561
 562 {-
 563 -- | 'breakChar' breaks its ByteString argument at the first occurence
 564 -- of the specified Char. It is more efficient than 'break' as it is
 565 -- implemented with @memchr(3)@. I.e.
 566 --
 567 -- > break (=='c') "abcd" == breakChar 'c' "abcd"
 568 --
 569 breakChar :: Char -> ByteString -> (ByteString, ByteString)
 570 breakChar = B.breakByte . c2w
 571 {-# INLINE breakChar #-}
 572
 573 -- | 'spanChar' breaks its ByteString argument at the first
 574 -- occurence of a Char other than its argument. It is more efficient
 575 -- than 'span (==)'
 576 --
 577 -- > span  (=='c') "abcd" == spanByte 'c' "abcd"
 578 --
 579 spanChar :: Char -> ByteString -> (ByteString, ByteString)
 580 spanChar = B.spanByte . c2w
 581 {-# INLINE spanChar #-}
 582 -}
 583
 584 -- | /O(n)/ Break a 'ByteString' into pieces separated by the byte
 585 -- argument, consuming the delimiter. I.e.
 586 --
 587 -- > split '\n' "a\nb\nd\ne" == ["a","b","d","e"]
 588 -- > split 'a'  "aXaXaXa"    == ["","X","X","X",""]
 589 -- > split 'x'  "x"          == ["",""]
 590 --
 591 -- and
 592 --
 593 -- > join [c] . split c == id
 594 -- > split == splitWith . (==)
 595 --
 596 -- As for all splitting functions in this library, this function does
 597 -- not copy the substrings, it just constructs new 'ByteStrings' that
 598 -- are slices of the original.
 599 --
 600 split :: Char -> ByteString -> [ByteString]
 601 split = B.split . c2w
 602 {-# INLINE split #-}
 603
 604 -- | /O(n)/ Splits a 'ByteString' into components delimited by
 605 -- separators, where the predicate returns True for a separator element.
 606 -- The resulting components do not contain the separators.  Two adjacent
 607 -- separators result in an empty component in the output.  eg.
 608 --
 609 -- > splitWith (=='a') "aabbaca" == ["","","bb","c",""]
 610 --
 611 splitWith :: (Char -> Bool) -> ByteString -> [ByteString]
 612 splitWith f = B.splitWith (f . w2c)
 613 {-# INLINE splitWith #-}
 614 -- the inline makes a big difference here.
 615
 616 {-
 617 -- | Like 'splitWith', except that sequences of adjacent separators are
 618 -- treated as a single separator. eg.
 619 --
 620 -- > tokens (=='a') "aabbaca" == ["bb","c"]
 621 --
 622 tokens :: (Char -> Bool) -> ByteString -> [ByteString]
 623 tokens f = B.tokens (f . w2c)
 624 {-# INLINE tokens #-}
 625 -}
 626
 627 -- | The 'groupBy' function is the non-overloaded version of 'group'.
 628 groupBy :: (Char -> Char -> Bool) -> ByteString -> [ByteString]
 629 groupBy k = B.groupBy (\a b -> k (w2c a) (w2c b))
 630
 631 {-
 632 -- | /O(n)/ joinWithChar. An efficient way to join to two ByteStrings with a
 633 -- char. Around 4 times faster than the generalised join.
 634 --
 635 joinWithChar :: Char -> ByteString -> ByteString -> ByteString
 636 joinWithChar = B.joinWithByte . c2w
 637 {-# INLINE joinWithChar #-}
 638 -}
 639
 640 -- | /O(1)/ 'ByteString' index (subscript) operator, starting from 0.
 641 index :: ByteString -> Int -> Char
 642 index = (w2c .) . B.index
 643 {-# INLINE index #-}
 644
 645 -- | /O(n)/ The 'elemIndex' function returns the index of the first
 646 -- element in the given 'ByteString' which is equal (by memchr) to the
 647 -- query element, or 'Nothing' if there is no such element.
 648 elemIndex :: Char -> ByteString -> Maybe Int
 649 elemIndex = B.elemIndex . c2w
 650 {-# INLINE elemIndex #-}
 651
 652 -- | /O(n)/ The 'elemIndexEnd' function returns the last index of the
 653 -- element in the given 'ByteString' which is equal to the query
 654 -- element, or 'Nothing' if there is no such element. The following
 655 -- holds:
 656 --
 657 -- > elemIndexEnd c xs ==
 658 -- > (-) (length xs - 1) `fmap` elemIndex c (reverse xs)
 659 --
 660 elemIndexEnd :: Char -> ByteString -> Maybe Int
 661 elemIndexEnd = B.elemIndexEnd . c2w
 662 {-# INLINE elemIndexEnd #-}
 663
 664 -- | /O(n)/ The 'elemIndices' function extends 'elemIndex', by returning
 665 -- the indices of all elements equal to the query element, in ascending order.
 666 elemIndices :: Char -> ByteString -> [Int]
 667 elemIndices = B.elemIndices . c2w
 668 {-# INLINE elemIndices #-}
 669
 670 -- | The 'findIndex' function takes a predicate and a 'ByteString' and
 671 -- returns the index of the first element in the ByteString satisfying the predicate.
 672 findIndex :: (Char -> Bool) -> ByteString -> Maybe Int
 673 findIndex f = B.findIndex (f . w2c)
 674 {-# INLINE findIndex #-}
 675
 676 -- | The 'findIndices' function extends 'findIndex', by returning the
 677 -- indices of all elements satisfying the predicate, in ascending order.
 678 findIndices :: (Char -> Bool) -> ByteString -> [Int]
 679 findIndices f = B.findIndices (f . w2c)
 680
 681 -- | count returns the number of times its argument appears in the ByteString
 682 --
 683 -- > count = length . elemIndices
 684 --
 685 -- Also
 686 --
 687 -- > count '\n' == length . lines
 688 --
 689 -- But more efficiently than using length on the intermediate list.
 690 count :: Char -> ByteString -> Int
 691 count c = B.count (c2w c)
 692
 693 -- | /O(n)/ 'elem' is the 'ByteString' membership predicate. This
 694 -- implementation uses @memchr(3)@.
 695 elem :: Char -> ByteString -> Bool
 696 elem    c = B.elem (c2w c)
 697 {-# INLINE elem #-}
 698
 699 -- | /O(n)/ 'notElem' is the inverse of 'elem'
 700 notElem :: Char -> ByteString -> Bool
 701 notElem c = B.notElem (c2w c)
 702 {-# INLINE notElem #-}
 703
 704 -- | /O(n)/ 'filter', applied to a predicate and a ByteString,
 705 -- returns a ByteString containing those characters that satisfy the
 706 -- predicate.
 707 filter :: (Char -> Bool) -> ByteString -> ByteString
 708 filter f = B.filter (f . w2c)
 709 {-# INLINE filter #-}
 710
 711 -- | /O(n)/ The 'find' function takes a predicate and a ByteString,
 712 -- and returns the first element in matching the predicate, or 'Nothing'
 713 -- if there is no such element.
 714 find :: (Char -> Bool) -> ByteString -> Maybe Char
 715 find f ps = w2c `fmap` B.find (f . w2c) ps
 716 {-# INLINE find #-}
 717
 718 {-
 719 -- | /O(n)/ A first order equivalent of /filter . (==)/, for the common
 720 -- case of filtering a single Char. It is more efficient to use
 721 -- filterChar in this case.
 722 --
 723 -- > filterChar == filter . (==)
 724 --
 725 -- filterChar is around 10x faster, and uses much less space, than its
 726 -- filter equivalent
 727 --
 728 filterChar :: Char -> ByteString -> ByteString
 729 filterChar c = B.filterByte (c2w c)
 730 {-# INLINE filterChar #-}
 731
 732 -- | /O(n)/ A first order equivalent of /filter . (\/=)/, for the common
 733 -- case of filtering a single Char out of a list. It is more efficient
 734 -- to use /filterNotChar/ in this case.
 735 --
 736 -- > filterNotChar == filter . (/=)
 737 --
 738 -- filterNotChar is around 3x faster, and uses much less space, than its
 739 -- filter equivalent
 740 --
 741 filterNotChar :: Char -> ByteString -> ByteString
 742 filterNotChar c = B.filterNotByte (c2w c)
 743 {-# INLINE filterNotChar #-}
 744 -}
 745
 746 -- | /O(n)/ 'zip' takes two ByteStrings and returns a list of
 747 -- corresponding pairs of Chars. If one input ByteString is short,
 748 -- excess elements of the longer ByteString are discarded. This is
 749 -- equivalent to a pair of 'unpack' operations, and so space
 750 -- usage may be large for multi-megabyte ByteStrings
 751 zip :: ByteString -> ByteString -> [(Char,Char)]
 752 zip ps qs
 753     | B.null ps || B.null qs = []
 754     | otherwise = (unsafeHead ps, unsafeHead qs) : zip (B.unsafeTail ps) (B.unsafeTail qs)
 755
 756 -- | 'zipWith' generalises 'zip' by zipping with the function given as
 757 -- the first argument, instead of a tupling function.  For example,
 758 -- @'zipWith' (+)@ is applied to two ByteStrings to produce the list
 759 -- of corresponding sums.
 760 zipWith :: (Char -> Char -> a) -> ByteString -> ByteString -> [a]
 761 zipWith f = B.zipWith ((. w2c) . f . w2c)
 762
 763 -- | 'unzip' transforms a list of pairs of Chars into a pair of
 764 -- ByteStrings. Note that this performs two 'pack' operations.
 765 unzip :: [(Char,Char)] -> (ByteString,ByteString)
 766 unzip ls = (pack (P.map fst ls), pack (P.map snd ls))
 767 {-# INLINE unzip #-}
 768
 769 -- | A variety of 'head' for non-empty ByteStrings. 'unsafeHead' omits
 770 -- the check for the empty case, which is good for performance, but
 771 -- there is an obligation on the programmer to provide a proof that the
 772 -- ByteString is non-empty.
 773 unsafeHead :: ByteString -> Char
 774 unsafeHead  = w2c . B.unsafeHead
 775 {-# INLINE unsafeHead #-}
 776
 777 -- ---------------------------------------------------------------------
 778 -- Things that depend on the encoding
 779
 780 {-# RULES
 781     "FPS specialise break -> breakSpace"
 782         break isSpace = breakSpace
 783   #-}
 784
 785 -- | 'breakSpace' returns the pair of ByteStrings when the argument is
 786 -- broken at the first whitespace byte. I.e.
 787 --
 788 -- > break isSpace == breakSpace
 789 --
 790 breakSpace :: ByteString -> (ByteString,ByteString)
 791 breakSpace (PS x s l) = inlinePerformIO $ withForeignPtr x $ \p -> do
 792     i <- firstspace (p `plusPtr` s) 0 l
 793     return $! case () of {_
 794         | i == 0    -> (empty, PS x s l)
 795         | i == l    -> (PS x s l, empty)
 796         | otherwise -> (PS x s i, PS x (s+i) (l-i))
 797     }
 798 {-# INLINE breakSpace #-}
 799
 800 firstspace :: Ptr Word8 -> Int -> Int -> IO Int
 801 STRICT3(firstspace)
 802 firstspace ptr n m
 803     | n >= m    = return n
 804     | otherwise = do w <- peekByteOff ptr n
 805                      if (not . isSpaceWord8) w then firstspace ptr (n+1) m else return n
 806
 807 {-# RULES
 808     "FPS specialise dropWhile isSpace -> dropSpace"
 809         dropWhile isSpace = dropSpace
 810   #-}
 811
 812 -- | 'dropSpace' efficiently returns the 'ByteString' argument with
 813 -- white space Chars removed from the front. It is more efficient than
 814 -- calling dropWhile for removing whitespace. I.e.
 815 --
 816 -- > dropWhile isSpace == dropSpace
 817 --
 818 dropSpace :: ByteString -> ByteString
 819 dropSpace (PS x s l) = inlinePerformIO $ withForeignPtr x $ \p -> do
 820     i <- firstnonspace (p `plusPtr` s) 0 l
 821     return $! if i == l then empty else PS x (s+i) (l-i)
 822 {-# INLINE dropSpace #-}
 823
 824 firstnonspace :: Ptr Word8 -> Int -> Int -> IO Int
 825 STRICT3(firstnonspace)
 826 firstnonspace ptr n m
 827     | n >= m    = return n
 828     | otherwise = do w <- peekElemOff ptr n
 829                      if isSpaceWord8 w then firstnonspace ptr (n+1) m else return n
 830
 831 {-
 832 -- | 'dropSpaceEnd' efficiently returns the 'ByteString' argument with
 833 -- white space removed from the end. I.e.
 834 --
 835 -- > reverse . (dropWhile isSpace) . reverse == dropSpaceEnd
 836 --
 837 -- but it is more efficient than using multiple reverses.
 838 --
 839 dropSpaceEnd :: ByteString -> ByteString
 840 dropSpaceEnd (PS x s l) = inlinePerformIO $ withForeignPtr x $ \p -> do
 841     i <- lastnonspace (p `plusPtr` s) (l-1)
 842     return $! if i == (-1) then empty else PS x s (i+1)
 843 {-# INLINE dropSpaceEnd #-}
 844
 845 lastnonspace :: Ptr Word8 -> Int -> IO Int
 846 STRICT2(lastnonspace)
 847 lastnonspace ptr n
 848     | n < 0     = return n
 849     | otherwise = do w <- peekElemOff ptr n
 850                      if isSpaceWord8 w then lastnonspace ptr (n-1) else return n
 851 -}
 852
 853 -- | 'lines' breaks a ByteString up into a list of ByteStrings at
 854 -- newline Chars. The resulting strings do not contain newlines.
 855 --
 856 lines :: ByteString -> [ByteString]
 857 lines ps
 858     | null ps = []
 859     | otherwise = case search ps of
 860              Nothing -> [ps]
 861              Just n  -> take n ps : lines (drop (n+1) ps)
 862     where search = elemIndex '\n'
 863 {-# INLINE lines #-}
 864
 865 {-
 866 -- Just as fast, but more complex. Should be much faster, I thought.
 867 lines :: ByteString -> [ByteString]
 868 lines (PS _ _ 0) = []
 869 lines (PS x s l) = inlinePerformIO $ withForeignPtr x $ \p -> do
 870         let ptr = p `plusPtr` s
 871
 872             STRICT1(loop)
 873             loop n = do
 874                 let q = memchr (ptr `plusPtr` n) 0x0a (fromIntegral (l-n))
 875                 if q == nullPtr
 876                     then return [PS x (s+n) (l-n)]
 877                     else do let i = q `minusPtr` ptr
 878                             ls <- loop (i+1)
 879                             return $! PS x (s+n) (i-n) : ls
 880         loop 0
 881 -}
 882
 883 -- | 'unlines' is an inverse operation to 'lines'.  It joins lines,
 884 -- after appending a terminating newline to each.
 885 unlines :: [ByteString] -> ByteString
 886 unlines [] = empty
 887 unlines ss = (concat $ List.intersperse nl ss) `append` nl -- half as much space
 888     where nl = singleton '\n'
 889
 890 -- | 'words' breaks a ByteString up into a list of words, which
 891 -- were delimited by Chars representing white space. And
 892 --
 893 -- > tokens isSpace = words
 894 --
 895 words :: ByteString -> [ByteString]
 896 words = P.filter (not . B.null) . B.splitWith isSpaceWord8
 897 {-# INLINE words #-}
 898
 899 -- | The 'unwords' function is analogous to the 'unlines' function, on words.
 900 unwords :: [ByteString] -> ByteString
 901 unwords = join (singleton ' ')
 902 {-# INLINE unwords #-}
 903
 904 -- ---------------------------------------------------------------------
 905 -- Reading from ByteStrings
 906
 907 -- | readInt reads an Int from the beginning of the ByteString.  If there is no
 908 -- integer at the beginning of the string, it returns Nothing, otherwise
 909 -- it just returns the int read, and the rest of the string.
 910 readInt :: ByteString -> Maybe (Int, ByteString)
 911 readInt as
 912     | null as   = Nothing
 913     | otherwise =
 914         case unsafeHead as of
 915             '-' -> loop True  0 0 (unsafeTail as)
 916             '+' -> loop False 0 0 (unsafeTail as)
 917             _   -> loop False 0 0 as
 918
 919     where loop :: Bool -> Int -> Int -> ByteString -> Maybe (Int, ByteString)
 920           STRICT4(loop)
 921           loop neg i n ps
 922               | null ps   = end neg i n ps
 923               | otherwise =
 924                   case B.unsafeHead ps of
 925                     w | w >= 0x30
 926                      && w <= 0x39 -> loop neg (i+1)
 927                                           (n * 10 + (fromIntegral w - 0x30))
 928                                           (unsafeTail ps)
 929                       | otherwise -> end neg i n ps
 930
 931           end _    0 _ _  = Nothing
 932           end True _ n ps = Just (negate n, ps)
 933           end _    _ n ps = Just (n, ps)
 934
 935 -- | readInteger reads an Integer from the beginning of the ByteString.  If
 936 -- there is no integer at the beginning of the string, it returns Nothing,
 937 -- otherwise it just returns the int read, and the rest of the string.
 938 readInteger :: ByteString -> Maybe (Integer, ByteString)
 939 readInteger as
 940     | null as   = Nothing
 941     | otherwise =
 942         case unsafeHead as of
 943             '-' -> first (unsafeTail as) >>= \(n, bs) -> return (-n, bs)
 944             '+' -> first (unsafeTail as)
 945             _   -> first as
 946
 947     where first ps | null ps   = Nothing
 948                    | otherwise =
 949                        case B.unsafeHead ps of
 950                         w | w >= 0x30 && w <= 0x39 -> Just $
 951                             loop 1 (fromIntegral w - 0x30) [] (unsafeTail ps)
 952                           | otherwise              -> Nothing
 953
 954           loop :: Int -> Int -> [Integer]
 955                -> ByteString -> (Integer, ByteString)
 956           STRICT4(loop)
 957           loop d acc ns ps
 958               | null ps   = combine d acc ns empty
 959               | otherwise =
 960                   case B.unsafeHead ps of
 961                    w | w >= 0x30 && w <= 0x39 ->
 962                        if d == 9 then loop 1 (fromIntegral w - 0x30)
 963                                            (toInteger acc : ns)
 964                                            (unsafeTail ps)
 965                                  else loop (d+1)
 966                                            (10*acc + (fromIntegral w - 0x30))
 967                                            ns (unsafeTail ps)
 968                      | otherwise -> combine d acc ns ps
 969
 970           combine _ acc [] ps = (toInteger acc, ps)
 971           combine d acc ns ps =
 972               ((10^d * combine1 1000000000 ns + toInteger acc), ps)
 973
 974           combine1 _ [n] = n
 975           combine1 b ns  = combine1 (b*b) $ combine2 b ns
 976
 977           combine2 b (n:m:ns) = let t = m*b + n in t `seq` (t : combine2 b ns)
 978           combine2 _ ns       = ns
 979
 980 -- | Read an entire file strictly into a 'ByteString'.  This is far more
 981 -- efficient than reading the characters into a 'String' and then using
 982 -- 'pack'.  It also may be more efficient than opening the file and
 983 -- reading it using hGet.
 984 readFile :: FilePath -> IO ByteString
 985 readFile f = bracket (openFile f ReadMode) hClose
 986     (\h -> hFileSize h >>= hGet h . fromIntegral)
 987
 988 -- | Write a 'ByteString' to a file.
 989 writeFile :: FilePath -> ByteString -> IO ()
 990 writeFile f txt = bracket (openFile f WriteMode) hClose
 991     (\h -> hPut h txt)
 992
 993 -- | Append a 'ByteString' to a file.
 994 appendFile :: FilePath -> ByteString -> IO ()
 995 appendFile f txt = bracket (openFile f AppendMode) hClose
 996     (\h -> hPut h txt)
 997