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