Data/ByteString/Char8.hs

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