Data/ByteString/Char8.hs

   1 {-# OPTIONS_GHC -cpp -fffi #-}
   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 ByteStrings 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(..),         -- instances: Eq, Ord, Show, Read, Data, Typeable
  39
  40         -- * Introducing and eliminating 'ByteString's
  41         empty,                  -- :: ByteString
  42         packChar,               -- :: Char   -> ByteString
  43         pack,                   -- :: String -> ByteString
  44         unpack,                 -- :: ByteString -> String
  45
  46         -- * Basic interface
  47         cons,                   -- :: Char -> ByteString -> ByteString
  48         snoc,                   -- :: Char -> ByteString -> ByteString
  49         null,                   -- :: ByteString -> Bool
  50         length,                 -- :: ByteString -> Int
  51         head,                   -- :: ByteString -> Char
  52         tail,                   -- :: ByteString -> ByteString
  53         last,                   -- :: ByteString -> Char
  54         init,                   -- :: ByteString -> ByteString
  55         append,                 -- :: ByteString -> ByteString -> ByteString
  56
  57         -- * Special ByteStrings
  58         inits,                  -- :: ByteString -> [ByteString]
  59         tails,                  -- :: ByteString -> [ByteString]
  60         elems,                  -- :: ByteString -> [ByteString]
  61
  62         -- * Transformating ByteStrings
  63         map,                    -- :: (Char -> Char) -> ByteString -> ByteString
  64         reverse,                -- :: ByteString -> ByteString
  65         intersperse,            -- :: Char -> ByteString -> ByteString
  66         transpose,              -- :: [ByteString] -> [ByteString]
  67
  68         -- * Reducing 'ByteString's
  69         foldl,                  -- :: (a -> Char -> a) -> a -> ByteString -> a
  70         foldr,                  -- :: (Char -> a -> a) -> a -> ByteString -> a
  71         foldl1,                 -- :: (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         mapIndexed,             -- :: (Int -> Char -> Char) -> ByteString -> ByteString
  82         hash,                   -- :: ByteString -> Int32
  83
  84         -- * Generating and unfolding ByteStrings
  85         replicate,              -- :: Int -> Char -> ByteString
  86         unfoldrN,               -- :: (Char -> Maybe (Char, Char)) -> Char -> ByteString
  87
  88         -- * Substrings
  89
  90         -- ** Breaking strings
  91         take,                   -- :: Int -> ByteString -> ByteString
  92         drop,                   -- :: Int -> ByteString -> ByteString
  93         splitAt,                -- :: Int -> ByteString -> (ByteString, ByteString)
  94         takeWhile,              -- :: (Char -> Bool) -> ByteString -> ByteString
  95         dropWhile,              -- :: (Char -> Bool) -> ByteString -> ByteString
  96         break,                  -- :: (Char -> Bool) -> ByteString -> (ByteString, ByteString)
  97         span,                   -- :: (Char -> Bool) -> ByteString -> (ByteString, ByteString)
  98         spanEnd,                -- :: (Char -> Bool) -> ByteString -> (ByteString, ByteString)
  99
 100         -- ** Breaking and dropping on specific Chars
 101         breakChar,              -- :: Char -> ByteString -> (ByteString, ByteString)
 102         breakFirst,             -- :: Char -> ByteString -> Maybe (ByteString,ByteString)
 103         breakLast,              -- :: Char -> ByteString -> Maybe (ByteString,ByteString)
 104         breakSpace,             -- :: ByteString -> Maybe (ByteString,ByteString)
 105         dropSpace,              -- :: ByteString -> ByteString
 106         dropSpaceEnd,           -- :: ByteString -> ByteString
 107
 108         -- ** Breaking into many substrings
 109         split,                  -- :: Char -> ByteString -> [ByteString]
 110         splitWith,              -- :: (Char -> Bool) -> ByteString -> [ByteString]
 111         tokens,                 -- :: (Char -> Bool) -> ByteString -> [ByteString]
 112
 113         -- ** Breaking into lines and words
 114         lines,                  -- :: ByteString -> [ByteString]
 115         words,                  -- :: ByteString -> [ByteString]
 116         unlines,                -- :: [ByteString] -> ByteString
 117         unwords,                -- :: ByteString -> [ByteString]
 118
 119         lines',                 -- :: ByteString -> [ByteString]
 120         unlines',               -- :: [ByteString] -> ByteString
 121         linesCRLF',             -- :: ByteString -> [ByteString]
 122         unlinesCRLF',           -- :: [ByteString] -> ByteString
 123         words',                 -- :: ByteString -> [ByteString]
 124         unwords',               -- :: ByteString -> [ByteString]
 125
 126         lineIndices,            -- :: ByteString -> [Int]
 127         betweenLines,           -- :: ByteString -> ByteString -> ByteString -> Maybe (ByteString)
 128
 129         -- ** Joining strings
 130         join,                   -- :: ByteString -> [ByteString] -> ByteString
 131         joinWithChar,           -- :: Char -> ByteString -> ByteString -> ByteString
 132
 133         -- * Indexing ByteStrings
 134         index,                  -- :: ByteString -> Int -> Char
 135         elemIndex,              -- :: Char -> ByteString -> Maybe Int
 136         elemIndexLast,          -- :: Char -> ByteString -> Maybe Int
 137         elemIndices,            -- :: Char -> ByteString -> [Int]
 138         findIndex,              -- :: (Char -> Bool) -> ByteString -> Maybe Int
 139         findIndices,            -- :: (Char -> Bool) -> ByteString -> [Int]
 140         count,                  -- :: Char -> ByteString -> Int
 141
 142         -- * Ordered ByteStrings
 143         sort,                   -- :: ByteString -> ByteString
 144
 145         -- * Searching ByteStrings
 146
 147         -- ** Searching by equality
 148         elem,                   -- :: Char -> ByteString -> Bool
 149         notElem,                -- :: Char -> ByteString -> Bool
 150         filterChar,             -- :: Char -> ByteString -> ByteString
 151         filterNotChar,          -- :: Char -> ByteString -> ByteString
 152
 153         -- ** Searching with a predicate
 154         filter,                 -- :: (Char -> Bool) -> ByteString -> ByteString
 155         find,                   -- :: (Char -> Bool) -> ByteString -> Maybe Char
 156
 157         -- ** Searching for substrings
 158         isPrefixOf,             -- :: ByteString -> ByteString -> Bool
 159         isSuffixOf,             -- :: ByteString -> ByteString -> Bool
 160         isSubstringOf,          -- :: ByteString -> ByteString -> Bool
 161         findSubstring,          -- :: ByteString -> ByteString -> Maybe Int
 162         findSubstrings,         -- :: ByteString -> ByteString -> [Int]
 163
 164         -- * Zipping and unzipping ByteString
 165         zip,                    -- :: ByteString -> ByteString -> [(Char,Char)]
 166         zipWith,                -- :: (Char -> Char -> c) -> ByteString -> ByteString -> [c]
 167         unzip,                  -- :: [(Char,Char)] -> (ByteString,ByteString)
 168
 169         -- * Unchecked access
 170         unsafeHead,             -- :: ByteString -> Char
 171         unsafeTail,             -- :: ByteString -> ByteString
 172         unsafeIndex,            -- :: ByteString -> Int -> Char
 173         w2c,                    -- :: Word8 -> Char
 174         c2w,                    -- :: Char  -> Word8
 175
 176         -- * Reading from ByteStrings
 177         readInt,                -- :: ByteString -> Maybe Int
 178         unsafeReadInt,          -- :: ByteString -> Maybe Int
 179
 180         -- * Copying ByteStrings
 181         copy,                   -- :: ByteString -> ByteString
 182
 183         -- * I\/O with @ByteString@s
 184
 185         -- ** Standard input and output
 186
 187 #if defined(__GLASGOW_HASKELL__)
 188         getLine,                -- :: IO ByteString
 189 #endif
 190         getContents,            -- :: IO ByteString
 191         putStr,                 -- :: ByteString -> IO ()
 192         putStrLn,               -- :: ByteString -> IO ()
 193
 194         -- ** Files
 195         readFile,               -- :: FilePath -> IO ByteString
 196         writeFile,              -- :: FilePath -> ByteString -> IO ()
 197
 198         -- ** I\/O with Handles
 199 #if defined(__GLASGOW_HASKELL__)
 200         getArgs,                -- :: IO [ByteString]
 201         hGetLine,               -- :: Handle -> IO ByteString
 202         hGetNonBlocking,        -- :: Handle -> Int -> IO ByteString
 203 #endif
 204         hGetContents,           -- :: Handle -> IO ByteString
 205         hGet,                   -- :: Handle -> Int -> IO ByteString
 206         hPut,                   -- :: 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     ) where
 216
 217 import qualified Prelude as P
 218 import Prelude hiding           (reverse,head,tail,last,init,null
 219                                 ,length,map,lines,foldl,foldr,unlines
 220                                 ,concat,any,take,drop,splitAt,takeWhile
 221                                 ,dropWhile,span,break,elem,filter,unwords
 222                                 ,words,maximum,minimum,all,concatMap
 223                                 ,foldl1,foldr1,readFile,writeFile,replicate
 224                                 ,getContents,getLine,putStr,putStrLn
 225                                 ,zip,zipWith,unzip,notElem)
 226
 227 import qualified Data.ByteString as B
 228
 229 -- Listy functions transparently exported
 230 import Data.ByteString (ByteString(..)
 231                        ,empty,null,length,tail,init,append
 232                        ,inits,tails,elems,reverse,transpose
 233                        ,concat,hash,take,drop,splitAt,join
 234                        ,sort,isPrefixOf,isSuffixOf,isSubstringOf,findSubstring
 235                        ,findSubstrings,unsafeTail,copy
 236
 237                        ,getContents, putStr, putStrLn
 238                        ,readFile, writeFile
 239                        ,hGetContents, hGet, hPut
 240 #if defined(__GLASGOW_HASKELL__)
 241                        ,getLine, getArgs, hGetLine, hGetNonBlocking
 242                        ,packAddress, unsafePackAddress
 243 #endif
 244                        ,useAsCString, unsafeUseAsCString
 245                        )
 246
 247 import Data.Char
 248
 249 import qualified Data.List as List (intersperse)
 250
 251 import Foreign
 252 import Foreign.C.Types          (CLong)
 253 import Foreign.Marshal.Utils    (with)
 254
 255 #if defined(__GLASGOW_HASKELL__)
 256 import GHC.Base                 (Char(..),unsafeChr,unpackCString#,unsafeCoerce#)
 257 import GHC.IOBase               (IO(..),stToIO)
 258 import GHC.Prim                 (Addr#,writeWord8OffAddr#,realWorld#,plusAddr#)
 259 import GHC.Ptr                  (Ptr(..))
 260 import GHC.ST                   (ST(..))
 261 #endif
 262
 263 #define STRICT1(f) f a | a `seq` False = undefined
 264 #define STRICT2(f) f a b | a `seq` b `seq` False = undefined
 265 #define STRICT3(f) f a b c | a `seq` b `seq` c `seq` False = undefined
 266
 267 ------------------------------------------------------------------------
 268
 269 -- | /O(1)/ Convert a 'Char' into a 'ByteString'
 270 packChar :: Char -> ByteString
 271 packChar = B.packByte . c2w
 272 {-# INLINE packChar #-}
 273
 274 -- | /O(n)/ Convert a 'String' into a 'ByteString'
 275 --
 276 -- For applications with large numbers of string literals, pack can be a
 277 -- bottleneck. In such cases, consider using packAddress (GHC only).
 278 pack :: String -> ByteString
 279 #if !defined(__GLASGOW_HASKELL__)
 280
 281 pack str = B.create (P.length str) $ \p -> go p str
 282     where go _ []     = return ()
 283           go p (x:xs) = poke p (c2w x) >> go (p `plusPtr` 1) xs
 284
 285 #else /* hack away */
 286
 287 pack str = B.create (P.length str) $ \(Ptr p) -> stToIO (go p str)
 288   where
 289     go :: Addr# -> [Char] -> ST a ()
 290     go _ []        = return ()
 291     go p (C# c:cs) = writeByte p (unsafeCoerce# c) >> go (p `plusAddr#` 1#) cs
 292
 293     writeByte p c = ST $ \s# ->
 294         case writeWord8OffAddr# p 0# c s# of s2# -> (# s2#, () #)
 295     {-# INLINE writeByte #-}
 296
 297 {-# RULES
 298 "pack/packAddress" forall s# .
 299                    pack (unpackCString# s#) = B.packAddress s#
 300  #-}
 301
 302 #endif
 303
 304 {-# INLINE pack #-}
 305
 306 -- | /O(n)/ Converts a 'ByteString' to a 'String'.
 307 unpack :: ByteString -> [Char]
 308 unpack = B.unpackWith w2c
 309 {-# INLINE unpack #-}
 310
 311 -- | /O(n)/ 'cons' is analogous to (:) for lists, but of different
 312 -- complexity, as it requires a memcpy.
 313 cons :: Char -> ByteString -> ByteString
 314 cons = B.cons . c2w
 315 {-# INLINE cons #-}
 316
 317 -- | /O(n)/ Append a Char to the end of a 'ByteString'. Similar to
 318 -- 'cons', this function performs a memcpy.
 319 snoc :: ByteString -> Char -> ByteString
 320 snoc p = B.snoc p . c2w
 321 {-# INLINE snoc #-}
 322
 323 -- | /O(1)/ Extract the first element of a ByteString, which must be non-empty.
 324 head :: ByteString -> Char
 325 head = w2c . B.head
 326 {-# INLINE head #-}
 327
 328 -- | /O(1)/ Extract the last element of a packed string, which must be non-empty.
 329 last :: ByteString -> Char
 330 last = w2c . B.last
 331 {-# INLINE last #-}
 332
 333 -- | /O(n)/ 'map' @f xs@ is the ByteString obtained by applying @f@ to each element of @xs@
 334 map :: (Char -> Char) -> ByteString -> ByteString
 335 map f = B.map (c2w . f . w2c)
 336 {-# INLINE map #-}
 337
 338 -- | /O(n)/ The 'intersperse' function takes a Char and a 'ByteString'
 339 -- and \`intersperses\' that Char between the elements of the
 340 -- 'ByteString'.  It is analogous to the intersperse function on Lists.
 341 intersperse :: Char -> ByteString -> ByteString
 342 intersperse = B.intersperse . c2w
 343 {-# INLINE intersperse #-}
 344
 345 -- | 'foldl', applied to a binary operator, a starting value (typically
 346 -- the left-identity of the operator), and a ByteString, reduces the
 347 -- ByteString using the binary operator, from left to right.
 348 foldl :: (a -> Char -> a) -> a -> ByteString -> a
 349 foldl f = B.foldl (\a c -> f a (w2c c))
 350 {-# INLINE foldl #-}
 351
 352 -- | 'foldr', applied to a binary operator, a starting value
 353 -- (typically the right-identity of the operator), and a packed string,
 354 -- reduces the packed string using the binary operator, from right to left.
 355 foldr :: (Char -> a -> a) -> a -> ByteString -> a
 356 foldr f = B.foldr (\c a -> f (w2c c) a)
 357 {-# INLINE foldr #-}
 358
 359 -- | 'foldl1' is a variant of 'foldl' that has no starting value
 360 -- argument, and thus must be applied to non-empty 'ByteStrings'.
 361 foldl1 :: (Char -> Char -> Char) -> ByteString -> Char
 362 foldl1 f ps = w2c (B.foldl1 (\x y -> c2w (f (w2c x) (w2c y))) ps)
 363 {-# INLINE foldl1 #-}
 364
 365 -- | 'foldr1' is a variant of 'foldr' that has no starting value argument,
 366 -- and thus must be applied to non-empty 'ByteString's
 367 foldr1 :: (Char -> Char -> Char) -> ByteString -> Char
 368 foldr1 f ps = w2c (B.foldl1 (\x y -> c2w (f (w2c x) (w2c y))) ps)
 369 {-# INLINE foldr1 #-}
 370
 371 -- | Map a function over a 'ByteString' and concatenate the results
 372 concatMap :: (Char -> ByteString) -> ByteString -> ByteString
 373 concatMap f = B.concatMap (f . w2c)
 374 {-# INLINE concatMap #-}
 375
 376 -- | Applied to a predicate and a ByteString, 'any' determines if
 377 -- any element of the 'ByteString' satisfies the predicate.
 378 any :: (Char -> Bool) -> ByteString -> Bool
 379 any f = B.any (f . w2c)
 380 {-# INLINE any #-}
 381
 382 -- | Applied to a predicate and a 'ByteString', 'all' determines if
 383 -- all elements of the 'ByteString' satisfy the predicate.
 384 all :: (Char -> Bool) -> ByteString -> Bool
 385 all f = B.all (f . w2c)
 386 {-# INLINE all #-}
 387
 388 -- | 'maximum' returns the maximum value from a 'ByteString'
 389 maximum :: ByteString -> Char
 390 maximum = w2c . B.maximum
 391 {-# INLINE maximum #-}
 392
 393 -- | 'minimum' returns the minimum value from a 'ByteString'
 394 minimum :: ByteString -> Char
 395 minimum = w2c . B.minimum
 396 {-# INLINE minimum #-}
 397
 398 -- | /O(n)/ map Char functions, provided with the index at each position
 399 mapIndexed :: (Int -> Char -> Char) -> ByteString -> ByteString
 400 mapIndexed f = B.mapIndexed (\i c -> c2w (f i (w2c c)))
 401 {-# INLINE mapIndexed #-}
 402
 403 -- | /O(n)/ 'replicate' @n x@ is a ByteString of length @n@ with @x@
 404 -- the value of every element. The following holds:
 405 --
 406 -- > replicate w c = unfoldr w (\u -> Just (u,u)) c
 407 --
 408 -- This implemenation uses @memset(3)@
 409 replicate :: Int -> Char -> ByteString
 410 replicate w = B.replicate w . c2w
 411 {-# INLINE replicate #-}
 412
 413 -- | /O(n)/ The 'unfoldrN' function is analogous to the List \'unfoldr\'.
 414 -- 'unfoldrN' builds a ByteString from a seed value.  The function takes
 415 -- the element and returns 'Nothing' if it is done producing the
 416 -- ByteString or returns 'Just' @(a,b)@, in which case, @a@ is a
 417 -- prepending to the ByteString and @b@ is used as the next element in a
 418 -- recursive call.
 419 --
 420 -- To preven unfoldrN having /O(n^2)/ complexity (as prepending a
 421 -- character to a ByteString is /O(n)/, this unfoldr requires a maximum
 422 -- final size of the ByteString as an argument. 'cons' can then be
 423 -- implemented in /O(1)/ (i.e.  a 'poke'), and the unfoldr itself has
 424 -- linear complexity. The depth of the recursion is limited to this
 425 -- size, but may be less. For lazy, infinite unfoldr, use
 426 -- 'Data.List.unfoldr' (from 'Data.List').
 427 --
 428 -- Examples:
 429 --
 430 -- > unfoldrN 10 (\x -> Just (x, chr (ord x + 1))) '0' == "0123456789"
 431 --
 432 -- The following equation connects the depth-limited unfoldr to the List unfoldr:
 433 --
 434 -- > unfoldrN n == take n $ List.unfoldr
 435 --
 436 unfoldrN :: Int -> (Char -> Maybe (Char, Char)) -> Char -> ByteString
 437 unfoldrN n f w = B.unfoldrN n ((k `fmap`) . f . w2c) (c2w w)
 438     where k (i,j) = (c2w i, c2w j) -- (c2w *** c2w)
 439 {-# INLINE unfoldrN #-}
 440
 441 -- | 'takeWhile', applied to a predicate @p@ and a ByteString @xs@,
 442 -- returns the longest prefix (possibly empty) of @xs@ of elements that
 443 -- satisfy @p@.
 444 takeWhile :: (Char -> Bool) -> ByteString -> ByteString
 445 takeWhile f = B.takeWhile (f . w2c)
 446 {-# INLINE takeWhile #-}
 447
 448 -- | 'dropWhile' @p xs@ returns the suffix remaining after 'takeWhile' @p xs@.
 449 dropWhile :: (Char -> Bool) -> ByteString -> ByteString
 450 dropWhile f = B.dropWhile (f . w2c)
 451 {-# INLINE dropWhile #-}
 452
 453 -- | 'break' @p@ is equivalent to @'span' ('not' . p)@.
 454 break :: (Char -> Bool) -> ByteString -> (ByteString, ByteString)
 455 break f = B.break (f . w2c)
 456 {-# INLINE break #-}
 457
 458 -- | 'span' @p xs@ breaks the ByteString into two segments. It is
 459 -- equivalent to @('takeWhile' p xs, 'dropWhile' p xs)@
 460 span :: (Char -> Bool) -> ByteString -> (ByteString, ByteString)
 461 span f = B.span (f . w2c)
 462 {-# INLINE span #-}
 463
 464 -- | 'spanEnd' behaves like 'span' but from the end of the 'ByteString'.
 465 -- We have
 466 --
 467 -- > spanEnd (not.isSpace) "x y z" == ("x y ","z")
 468 --
 469 -- and
 470 --
 471 -- > spanEnd (not . isSpace) ps
 472 -- >    ==
 473 -- > let (x,y) = span (not.isSpace) (reverse ps) in (reverse y, reverse x)
 474 --
 475 spanEnd :: (Char -> Bool) -> ByteString -> (ByteString, ByteString)
 476 spanEnd f = B.spanEnd (f . w2c)
 477 {-# INLINE spanEnd #-}
 478
 479 -- | 'breakChar' breaks its ByteString argument at the first occurence
 480 -- of the specified Char. It is more efficient than 'break' as it is
 481 -- implemented with @memchr(3)@. I.e.
 482 --
 483 -- > break (=='c') "abcd" == breakChar 'c' "abcd"
 484 --
 485 breakChar :: Char -> ByteString -> (ByteString, ByteString)
 486 breakChar = B.breakByte . c2w
 487 {-# INLINE breakChar #-}
 488
 489 -- | /O(n)/ 'breakFirst' breaks the given ByteString on the first
 490 -- occurence of @w@. It behaves like 'break', except the delimiter is
 491 -- not returned, and @Nothing@ is returned if the delimiter is not in
 492 -- the ByteString. I.e.
 493 --
 494 -- > breakFirst 'b' "aabbcc" == Just ("aa","bcc")
 495 --
 496 -- > breakFirst c xs ==
 497 -- > let (x,y) = break (== c) xs
 498 -- > in if null y then Nothing else Just (x, drop 1 y))
 499 --
 500 breakFirst :: Char -> ByteString -> Maybe (ByteString,ByteString)
 501 breakFirst = B.breakFirst . c2w
 502 {-# INLINE breakFirst #-}
 503
 504 -- | /O(n)/ 'breakLast' behaves like breakFirst, but from the end of the
 505 -- ByteString.
 506 --
 507 -- > breakLast ('b') (pack "aabbcc") == Just ("aab","cc")
 508 --
 509 -- and the following are equivalent:
 510 --
 511 -- > breakLast 'c' "abcdef"
 512 -- > let (x,y) = break (=='c') (reverse "abcdef")
 513 -- > in if null x then Nothing else Just (reverse (drop 1 y), reverse x)
 514 --
 515 breakLast :: Char -> ByteString -> Maybe (ByteString,ByteString)
 516 breakLast = B.breakLast . c2w
 517 {-# INLINE breakLast #-}
 518
 519 -- | /O(n)/ Break a 'ByteString' into pieces separated by the byte
 520 -- argument, consuming the delimiter. I.e.
 521 --
 522 -- > split '\n' "a\nb\nd\ne" == ["a","b","d","e"]
 523 -- > split 'a'  "aXaXaXa"    == ["","X","X","X"]
 524 -- > split 'x'  "x"          == ["",""]
 525 --
 526 -- and
 527 --
 528 -- > join [c] . split c == id
 529 -- > split == splitWith . (==)
 530 --
 531 -- As for all splitting functions in this library, this function does
 532 -- not copy the substrings, it just constructs new 'ByteStrings' that
 533 -- are slices of the original.
 534 --
 535 split :: Char -> ByteString -> [ByteString]
 536 split = B.split . c2w
 537 {-# INLINE split #-}
 538
 539 -- | /O(n)/ Splits a 'ByteString' into components delimited by
 540 -- separators, where the predicate returns True for a separator element.
 541 -- The resulting components do not contain the separators.  Two adjacent
 542 -- separators result in an empty component in the output.  eg.
 543 --
 544 -- > splitWith (=='a') "aabbaca" == ["","","bb","c",""]
 545 --
 546 splitWith :: (Char -> Bool) -> ByteString -> [ByteString]
 547 splitWith f = B.splitWith (f . w2c)
 548 {-# INLINE splitWith #-}
 549 -- the inline makes a big difference here.
 550
 551 -- | Like 'splitWith', except that sequences of adjacent separators are
 552 -- treated as a single separator. eg.
 553 --
 554 -- > tokens (=='a') "aabbaca" == ["bb","c"]
 555 --
 556 tokens :: (Char -> Bool) -> ByteString -> [ByteString]
 557 tokens f = B.tokens (f . w2c)
 558 {-# INLINE tokens #-}
 559
 560 -- | /O(n)/ joinWithChar. An efficient way to join to two ByteStrings with a
 561 -- char. Around 4 times faster than the generalised join.
 562 --
 563 joinWithChar :: Char -> ByteString -> ByteString -> ByteString
 564 joinWithChar = B.joinWithByte . c2w
 565 {-# INLINE joinWithChar #-}
 566
 567 -- | /O(1)/ 'ByteString' index (subscript) operator, starting from 0.
 568 index :: ByteString -> Int -> Char
 569 index = (w2c .) . B.index
 570 {-# INLINE index #-}
 571
 572 -- | /O(n)/ The 'elemIndex' function returns the index of the first
 573 -- element in the given 'ByteString' which is equal (by memchr) to the
 574 -- query element, or 'Nothing' if there is no such element.
 575 elemIndex :: Char -> ByteString -> Maybe Int
 576 elemIndex = B.elemIndex . c2w
 577 {-# INLINE elemIndex #-}
 578
 579 -- | /O(n)/ The 'elemIndexLast' function returns the last index of the
 580 -- element in the given 'ByteString' which is equal to the query
 581 -- element, or 'Nothing' if there is no such element. The following
 582 -- holds:
 583 --
 584 -- > elemIndexLast c xs ==
 585 -- > (-) (length xs - 1) `fmap` elemIndex c (reverse xs)
 586 --
 587 elemIndexLast :: Char -> ByteString -> Maybe Int
 588 elemIndexLast = B.elemIndexLast . c2w
 589 {-# INLINE elemIndexLast #-}
 590
 591 -- | /O(n)/ The 'elemIndices' function extends 'elemIndex', by returning
 592 -- the indices of all elements equal to the query element, in ascending order.
 593 elemIndices :: Char -> ByteString -> [Int]
 594 elemIndices = B.elemIndices . c2w
 595 {-# INLINE elemIndices #-}
 596
 597 -- | The 'findIndex' function takes a predicate and a 'ByteString' and
 598 -- returns the index of the first element in the ByteString satisfying the predicate.
 599 findIndex :: (Char -> Bool) -> ByteString -> Maybe Int
 600 findIndex f = B.findIndex (f . w2c)
 601 {-# INLINE findIndex #-}
 602
 603 -- | The 'findIndices' function extends 'findIndex', by returning the
 604 -- indices of all elements satisfying the predicate, in ascending order.
 605 findIndices :: (Char -> Bool) -> ByteString -> [Int]
 606 findIndices f = B.findIndices (f . w2c)
 607
 608 -- | count returns the number of times its argument appears in the ByteString
 609 --
 610 -- > count = length . elemIndices
 611 --
 612 -- But more efficiently than using length on the intermediate list.
 613 count :: Char -> ByteString -> Int
 614 count c = B.count (c2w c)
 615
 616 -- | /O(n)/ 'elem' is the 'ByteString' membership predicate. This
 617 -- implementation uses @memchr(3)@.
 618 elem :: Char -> ByteString -> Bool
 619 elem    c = B.elem (c2w c)
 620 {-# INLINE elem #-}
 621
 622 -- | /O(n)/ 'notElem' is the inverse of 'elem'
 623 notElem :: Char -> ByteString -> Bool
 624 notElem c = B.notElem (c2w c)
 625 {-# INLINE notElem #-}
 626
 627 -- | /O(n)/ 'filter', applied to a predicate and a ByteString,
 628 -- returns a ByteString containing those characters that satisfy the
 629 -- predicate.
 630 filter :: (Char -> Bool) -> ByteString -> ByteString
 631 filter f = B.filter (f . w2c)
 632 {-# INLINE filter #-}
 633
 634 -- | /O(n)/ The 'find' function takes a predicate and a ByteString,
 635 -- and returns the first element in matching the predicate, or 'Nothing'
 636 -- if there is no such element.
 637 find :: (Char -> Bool) -> ByteString -> Maybe Char
 638 find f ps = w2c `fmap` B.find (f . w2c) ps
 639 {-# INLINE find #-}
 640
 641 -- | /O(n)/ A first order equivalent of /filter . (==)/, for the common
 642 -- case of filtering a single Char. It is more efficient to use
 643 -- filterChar in this case.
 644 --
 645 -- > filterChar == filter . (==)
 646 --
 647 -- filterChar is around 10x faster, and uses much less space, than its
 648 -- filter equivalent
 649 --
 650 filterChar :: Char -> ByteString -> ByteString
 651 filterChar c = B.filterByte (c2w c)
 652 {-# INLINE filterChar #-}
 653
 654 -- | /O(n)/ A first order equivalent of /filter . (\/=)/, for the common
 655 -- case of filtering a single Char out of a list. It is more efficient
 656 -- to use /filterNotChar/ in this case.
 657 --
 658 -- > filterNotChar == filter . (/=)
 659 --
 660 -- filterNotChar is around 3x faster, and uses much less space, than its
 661 -- filter equivalent
 662 --
 663 filterNotChar :: Char -> ByteString -> ByteString
 664 filterNotChar c = B.filterNotByte (c2w c)
 665 {-# INLINE filterNotChar #-}
 666
 667 -- | /O(n)/ 'zip' takes two ByteStrings and returns a list of
 668 -- corresponding pairs of Chars. If one input ByteString is short,
 669 -- excess elements of the longer ByteString are discarded. This is
 670 -- equivalent to a pair of 'unpack' operations, and so space
 671 -- usage may be large for multi-megabyte ByteStrings
 672 zip :: ByteString -> ByteString -> [(Char,Char)]
 673 zip ps qs
 674     | B.null ps || B.null qs = []
 675     | otherwise = (unsafeHead ps, unsafeHead qs) : zip (B.unsafeTail ps) (B.unsafeTail qs)
 676
 677 -- | 'zipWith' generalises 'zip' by zipping with the function given as
 678 -- the first argument, instead of a tupling function.  For example,
 679 -- @'zipWith' (+)@ is applied to two ByteStrings to produce the list
 680 -- of corresponding sums.
 681 zipWith :: (Char -> Char -> a) -> ByteString -> ByteString -> [a]
 682 zipWith f = B.zipWith ((. w2c) . f . w2c)
 683
 684 -- | 'unzip' transforms a list of pairs of Chars into a pair of
 685 -- ByteStrings. Note that this performs two 'pack' operations.
 686 unzip :: [(Char,Char)] -> (ByteString,ByteString)
 687 unzip ls = (pack (P.map fst ls), pack (P.map snd ls))
 688 {-# INLINE unzip #-}
 689
 690 -- | A variety of 'head' for non-empty ByteStrings. 'unsafeHead' omits
 691 -- the check for the empty case, which is good for performance, but
 692 -- there is an obligation on the programmer to provide a proof that the
 693 -- ByteString is non-empty.
 694 unsafeHead :: ByteString -> Char
 695 unsafeHead  = w2c . B.unsafeHead
 696 {-# INLINE unsafeHead #-}
 697
 698 -- | Unsafe 'ByteString' index (subscript) operator, starting from 0, returning a Char.
 699 -- This omits the bounds check, which means there is an accompanying
 700 -- obligation on the programmer to ensure the bounds are checked in some
 701 -- other way.
 702 unsafeIndex :: ByteString -> Int -> Char
 703 unsafeIndex = (w2c .) . B.unsafeIndex
 704 {-# INLINE unsafeIndex #-}
 705
 706 -- | Conversion between 'Word8' and 'Char'. Should compile to a no-op.
 707 w2c :: Word8 -> Char
 708 #if !defined(__GLASGOW_HASKELL__)
 709 w2c = chr . fromIntegral
 710 #else
 711 w2c = unsafeChr . fromIntegral
 712 #endif
 713 {-# INLINE w2c #-}
 714
 715 -- | Unsafe conversion between 'Char' and 'Word8'. This is a no-op and
 716 -- silently truncates to 8 bits Chars > '\255'. It is provided as
 717 -- convenience for ByteString construction.
 718 c2w :: Char -> Word8
 719 c2w = fromIntegral . ord
 720 {-# INLINE c2w #-}
 721
 722 -- ---------------------------------------------------------------------
 723 -- Things that depend on the encoding
 724
 725 -- | 'breakSpace' returns the pair of ByteStrings when the argument is
 726 -- broken at the first whitespace byte. I.e.
 727 --
 728 -- > break isSpace == breakSpace
 729 --
 730 breakSpace :: ByteString -> (ByteString,ByteString)
 731 breakSpace (PS x s l) = inlinePerformIO $ withForeignPtr x $ \p -> do
 732     i <- firstspace (p `plusPtr` s) 0 l
 733     return $ case () of {_
 734         | i == 0    -> (empty, PS x s l)
 735         | i == l    -> (PS x s l, empty)
 736         | otherwise -> (PS x s i, PS x (s+i) (l-i))
 737     }
 738 {-# INLINE breakSpace #-}
 739
 740 firstspace :: Ptr Word8 -> Int -> Int -> IO Int
 741 STRICT3(firstspace)
 742 firstspace ptr n m
 743     | n >= m    = return n
 744     | otherwise = do w <- peekByteOff ptr n
 745                      if (not . isSpaceWord8) w then firstspace ptr (n+1) m else return n
 746
 747 -- | 'dropSpace' efficiently returns the 'ByteString' argument with
 748 -- white space Chars removed from the front. It is more efficient than
 749 -- calling dropWhile for removing whitespace. I.e.
 750 --
 751 -- > dropWhile isSpace == dropSpace
 752 --
 753 dropSpace :: ByteString -> ByteString
 754 dropSpace (PS x s l) = inlinePerformIO $ withForeignPtr x $ \p -> do
 755     i <- firstnonspace (p `plusPtr` s) 0 l
 756     return $ if i == l then empty else PS x (s+i) (l-i)
 757 {-# INLINE dropSpace #-}
 758
 759 firstnonspace :: Ptr Word8 -> Int -> Int -> IO Int
 760 STRICT3(firstnonspace)
 761 firstnonspace ptr n m
 762     | n >= m    = return n
 763     | otherwise = do w <- peekElemOff ptr n
 764                      if isSpaceWord8 w then firstnonspace ptr (n+1) m else return n
 765
 766 -- | 'dropSpaceEnd' efficiently returns the 'ByteString' argument with
 767 -- white space removed from the end. I.e.
 768 --
 769 -- > reverse . (dropWhile isSpace) . reverse == dropSpaceEnd
 770 --
 771 -- but it is more efficient than using multiple reverses.
 772 --
 773 dropSpaceEnd :: ByteString -> ByteString
 774 dropSpaceEnd (PS x s l) = inlinePerformIO $ withForeignPtr x $ \p -> do
 775     i <- lastnonspace (p `plusPtr` s) (l-1)
 776     return $ if i == (-1) then empty else PS x s (i+1)
 777 {-# INLINE dropSpaceEnd #-}
 778
 779 lastnonspace :: Ptr Word8 -> Int -> IO Int
 780 STRICT2(lastnonspace)
 781 lastnonspace ptr n
 782     | n < 0     = return n
 783     | otherwise = do w <- peekElemOff ptr n
 784                      if isSpaceWord8 w then lastnonspace ptr (n-1) else return n
 785
 786 -- | 'lines' breaks a ByteString up into a list of ByteStrings at
 787 -- newline Chars. The resulting strings do not contain newlines.
 788 lines :: ByteString -> [ByteString]
 789 lines ps
 790     | null ps = []
 791     | otherwise = case search ps of
 792              Nothing -> [ps]
 793              Just n  -> take n ps : lines (drop (n+1) ps)
 794     where search = elemIndex '\n'
 795 {-# INLINE lines #-}
 796
 797 {-
 798 -- Just as fast, but more complex. Should be much faster, I thought.
 799 lines :: ByteString -> [ByteString]
 800 lines (PS _ _ 0) = []
 801 lines (PS x s l) = inlinePerformIO $ withForeignPtr x $ \p -> do
 802         let ptr = p `plusPtr` s
 803
 804             STRICT1(loop)
 805             loop n = do
 806                 let q = memchr (ptr `plusPtr` n) 0x0a (fromIntegral (l-n))
 807                 if q == nullPtr
 808                     then return [PS x (s+n) (l-n)]
 809                     else do let i = q `minusPtr` ptr
 810                             ls <- loop (i+1)
 811                             return $! PS x (s+n) (i-n) : ls
 812         loop 0
 813 -}
 814
 815 -- | 'unlines' is an inverse operation to 'lines'.  It joins lines,
 816 -- after appending a terminating newline to each.
 817 unlines :: [ByteString] -> ByteString
 818 unlines [] = empty
 819 unlines ss = (concat $ List.intersperse nl ss) `append` nl -- half as much space
 820     where nl = packChar '\n'
 821
 822 -- | 'words' breaks a ByteString up into a list of words, which
 823 -- were delimited by Chars representing white space. And
 824 --
 825 -- > tokens isSpace = words
 826 --
 827 words :: ByteString -> [ByteString]
 828 words = B.tokens isSpaceWord8
 829
 830 -- | The 'unwords' function is analogous to the 'unlines' function, on words.
 831 unwords :: [ByteString] -> ByteString
 832 unwords = join (packChar ' ')
 833
 834 -- | /O(n)/ Indicies of newlines. Shorthand for
 835 --
 836 -- > elemIndices '\n'
 837 --
 838 lineIndices :: ByteString -> [Int]
 839 lineIndices = elemIndices '\n'
 840
 841 -- | 'lines\'' behaves like 'lines', in that it breaks a ByteString on
 842 -- newline Chars. However, unlike the Prelude functions, 'lines\'' and
 843 -- 'unlines\'' correctly reconstruct lines that are missing terminating
 844 -- newlines characters. I.e.
 845 --
 846 -- > unlines  (lines "a\nb\nc")  == "a\nb\nc\n"
 847 -- > unlines' (lines' "a\nb\nc") == "a\nb\nc"
 848 --
 849 -- Note that this means:
 850 --
 851 -- > lines  "a\nb\nc\n" == ["a","b","c"]
 852 -- > lines' "a\nb\nc\n" == ["a","b","c",""]
 853 --
 854 lines' :: ByteString -> [ByteString]
 855 lines' ps = ps `seq` case elemIndex '\n' ps of
 856      Nothing -> [ps]
 857      Just n -> take n ps : lines' (drop (n+1) ps)
 858
 859 -- | 'linesCRLF\'' behaves like 'lines\'', but breaks on (\\cr?\\lf)
 860 linesCRLF' :: ByteString -> [ByteString]
 861 linesCRLF' ps = ps `seq` case elemIndex '\n' ps of
 862      Nothing -> [ps]
 863      Just 0  -> empty : linesCRLF' (drop 1 ps)
 864      Just n  -> let k = if ps `unsafeIndex` (n-1) == '\r' then n-1 else n
 865                 in take k ps : linesCRLF' (drop (n+1) ps)
 866
 867 -- | 'unlines\'' behaves like 'unlines', except that it also correctly
 868 -- retores lines that do not have terminating newlines (see the
 869 -- description for 'lines\'').
 870 --
 871 unlines' :: [ByteString] -> ByteString
 872 unlines' ss = concat $ intersperse_newlines ss
 873     where intersperse_newlines (a:b:s) = a:newline: intersperse_newlines (b:s)
 874           intersperse_newlines s = s
 875           newline = packChar '\n'
 876
 877 -- | 'unlines\'' behaves like 'unlines', except that it also correctly
 878 -- retores lines that do not have terminating newlines (see the
 879 -- description for 'lines\''). Uses CRLF instead of LF.
 880 --
 881 unlinesCRLF' :: [ByteString] -> ByteString
 882 unlinesCRLF' ss = concat $ intersperse_newlines ss
 883     where intersperse_newlines (a:b:s) = a:newline: intersperse_newlines (b:s)
 884           intersperse_newlines s = s
 885           newline = pack "\r\n"
 886
 887 -- | 'words\'' behaves like 'words', with the exception that it produces
 888 -- output on ByteStrings with trailing whitespace that can be
 889 -- correctly inverted by 'unwords'. I.e.
 890 --
 891 -- > words  "a b c " == ["a","b","c"]
 892 -- > words' "a b c " == ["a","b","c",""]
 893 --
 894 -- > unwords $ words  "a b c " == "a b c"
 895 -- > unwords $ words' "a b c " == "a b c "
 896 --
 897 words' :: ByteString -> [ByteString]
 898 words' = B.splitWith isSpaceWord8
 899
 900 -- | 'unwords\'' behaves like 'unwords'. It is provided for consistency
 901 -- with the other invertable words and lines functions.
 902 unwords' :: [ByteString] -> ByteString
 903 unwords' = unwords
 904
 905 -- | 'betweenLines' returns the ByteString between the two lines given,
 906 -- or Nothing if they do not appear.  The returned string is the first
 907 -- and shortest string such that the line before it is the given first
 908 -- line, and the line after it is the given second line.
 909 betweenLines :: ByteString -- ^ First line to look for
 910              -> ByteString -- ^ Second line to look for
 911              -> ByteString -- ^ 'ByteString' to look in
 912              -> Maybe (ByteString)
 913
 914 betweenLines start end ps =
 915     case P.break (start ==) (lines ps) of
 916         (_, _:rest@(PS ps1 s1 _:_)) ->
 917             case P.break (end ==) rest of
 918                 (_, PS _ s2 _:_) -> Just $ PS ps1 s1 (s2 - s1)
 919                 _ -> Nothing
 920         _ -> Nothing
 921
 922 -- ---------------------------------------------------------------------
 923 -- Reading from ByteStrings
 924
 925 -- | readInt skips any whitespace at the beginning of its argument, and
 926 -- reads an Int from the beginning of the ByteString.  If there is no
 927 -- integer at the beginning of the string, it returns Nothing, otherwise
 928 -- it just returns the int read, and the rest of the string.
 929 readInt :: ByteString -> Maybe (Int, ByteString)
 930 readInt p@(PS x s l) = inlinePerformIO $ useAsCString p $ \cstr ->
 931     with (castPtr cstr) $ \endpp -> do
 932         val     <- c_strtol (castPtr cstr) endpp 0
 933         skipped <- (`minusPtr` cstr) `fmap` peek endpp
 934         return $ if skipped == 0
 935                  then Nothing
 936                  else Just (fromIntegral val, PS x (s+skipped) (l-skipped))
 937
 938 -- | unsafeReadInt is like readInt, but requires a null terminated
 939 -- ByteString. It avoids a copy if this is the case. It returns the Int
 940 -- read, if any, and the rest of the string.
 941 unsafeReadInt :: ByteString -> Maybe (Int, ByteString)
 942 unsafeReadInt p@(PS x s l) = inlinePerformIO $ unsafeUseAsCString p $ \cstr ->
 943     with (castPtr cstr) $ \endpp -> do
 944         val     <- c_strtol (castPtr cstr) endpp 0
 945         skipped <- (`minusPtr` cstr) `fmap` peek endpp
 946         return $ if skipped == 0
 947                  then Nothing
 948                  else Just (fromIntegral val, PS x (s+skipped) (l-skipped))
 949
 950 foreign import ccall unsafe "stdlib.h strtol" c_strtol
 951     :: Ptr Word8 -> Ptr (Ptr Word8) -> Int -> IO CLong
 952
 953 {-
 954 --
 955 -- not quite there yet
 956 --
 957 readInt :: ByteString -> Maybe (Int, ByteString)
 958 readInt = go 0
 959     where
 960         STRICT2(go)
 961         go i ps
 962             | B.null ps = Nothing
 963             | x == '-'  = neg 0 xs
 964             | otherwise = pos (parse x) xs
 965             where (x, xs) = (ps `unsafeIndex` 0, unsafeTail ps)
 966
 967         STRICT2(neg)
 968         neg n qs | isSpace x   = return $ Just ((i-n),xs)
 969                  | otherwise   = neg (parse x + (10 * n)) xs
 970                  where (x, xs) = (qs `unsafeIndex` 0, unsafeTail qs)
 971
 972         STRICT2(pos)
 973         pos n qs | isSpace x = go (i+n) xs
 974                  | otherwise = pos (parse x + (10 * n)) xs
 975                  where (x, xs) = (qs `unsafeIndexWord8` 0, unsafeTail qs)
 976
 977         parse w = fromIntegral (w - 48) :: Int
 978         {-# INLINE parse #-}
 979 -}
 980
 981 -- ---------------------------------------------------------------------
 982 -- Internals
 983
 984 -- Just like inlinePerformIO, but we inline it. Big performance gains as
 985 -- it exposes lots of things to further inlining
 986 --
 987 {-# INLINE inlinePerformIO #-}
 988 inlinePerformIO :: IO a -> a
 989 #if defined(__GLASGOW_HASKELL__)
 990 inlinePerformIO (IO m) = case m realWorld# of (# _, r #) -> r
 991 #else
 992 inlinePerformIO = unsafePerformIO
 993 #endif
 994
 995 -- ordered by frequency
 996 -- Idea from Ketil
 997 isSpaceWord8 :: Word8 -> Bool
 998 isSpaceWord8 w = case w of
 999     0x20 -> True -- SPACE
1000     0x0A -> True -- LF, \n
1001     0x09 -> True -- HT, \t
1002     0x0C -> True -- FF, \f
1003     0x0D -> True -- CR, \r
1004     0x0B -> True -- VT, \v
1005     _    -> False
1006 {-# INLINE isSpaceWord8 #-}
1007