Sync with FPS head
[packages/old-time.git] / 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