1{-# LANGUAGE BangPatterns, CPP, MagicHash, Rank2Types, UnboxedTuples #-}
2{-# OPTIONS_GHC -fno-warn-orphans #-}
3#if __GLASGOW_HASKELL__ >= 702
4{-# LANGUAGE Trustworthy #-}
6#if __GLASGOW_HASKELL__ >= 708
7{-# LANGUAGE TypeFamilies #-}
12-- Copyright : (c) 2009, 2010, 2011, 2012 Bryan O'Sullivan,
13-- (c) 2009 Duncan Coutts,
14-- (c) 2008, 2009 Tom Harper
17-- Maintainer : bos@serpentine.com
18-- Stability : experimental
21-- A time and space-efficient implementation of Unicode text.
22-- Suitable for performance critical use, both in terms of large data
23-- quantities and high speed.
25-- /Note/: Read below the synopsis for important notes on the use of
28-- This module is intended to be imported @qualified@, to avoid name
29-- clashes with "Prelude" functions, e.g.
31-- > import qualified Data.Text as T
33-- To use an extended and very rich family of functions for working
34-- with Unicode text (including normalization, regular expressions,
35-- non-standard encodings, text breaking, and locales), see
36-- <http://hackage.haskell.org/package/text-icu the text-icu package >.
40 -- * Strict vs lazy types
52 -- * Creation and elimination
115 -- ** Accumulating maps
119 -- ** Generation and unfolding
126 -- ** Breaking strings
148 -- ** Breaking into many substrings
154 -- ** Breaking into lines and words
192 -- * Low level operations
196import Prelude (Char, Bool(..), Int, Maybe(..), String,
197 Eq(..), Ord(..), Ordering(..), (++),
199 (&&), (||), (+), (-), (.), ($), ($!), (>>),
200 not, return, otherwise, quot)
201#if defined(HAVE_DEEPSEQ)
202import Control.DeepSeq (NFData)
205import Control.Exception (assert)
207import Data.Char (isSpace)
208import Data.Data (Data(gfoldl, toConstr, gunfold, dataTypeOf), constrIndex,
209 Constr, mkConstr, DataType, mkDataType, Fixity(Prefix))
210import Control.Monad (foldM)
211import Control.Monad.ST (ST)
212import qualified Data.Text.Array as A
213import qualified Data.List as L
214import Data.Monoid (Monoid(..))
215import Data.String (IsString(..))
216import qualified Data.Text.Internal.Fusion as S
217import qualified Data.Text.Internal.Fusion.Common as S
218import Data.Text.Internal.Fusion (stream, reverseStream, unstream)
219import Data.Text.Internal.Private (span_)
220import Data.Text.Internal (Text(..), empty, empty_, firstf, mul, safe, text)
221import qualified Prelude as P
222import Data.Text.Unsafe (Iter(..), iter, iter_, lengthWord16, reverseIter,
223 reverseIter_, unsafeHead, unsafeTail)
224import Data.Text.Internal.Unsafe.Char (unsafeChr, unsafeWrite)
225import qualified Data.Text.Internal.Functions as F
226import qualified Data.Text.Internal.Encoding.Utf16 as U16
227import Data.Text.Internal.Search (indices)
228#if defined(__HADDOCK__)
229import Data.ByteString (ByteString)
230import qualified Data.Text.Lazy as L
231import Data.Int (Int64)
233#if __GLASGOW_HASKELL__ >= 702
234import qualified GHC.CString as GHC
236import qualified GHC.Base as GHC
238#if __GLASGOW_HASKELL__ >= 708
239import qualified GHC.Exts as Exts
241import GHC.Prim (Addr#)
245-- This package provides both strict and lazy 'Text' types. The
246-- strict type is provided by the "Data.Text" module, while the lazy
247-- type is provided by the "Data.Text.Lazy" module. Internally, the
248-- lazy @Text@ type consists of a list of strict chunks.
250-- The strict 'Text' type requires that an entire string fit into
251-- memory at once. The lazy 'Data.Text.Lazy.Text' type is capable of
252-- streaming strings that are larger than memory using a small memory
253-- footprint. In many cases, the overhead of chunked streaming makes
254-- the lazy 'Data.Text.Lazy.Text' type slower than its strict
255-- counterpart, but this is not always the case. Sometimes, the time
256-- complexity of a function in one module may be different from the
257-- other, due to their differing internal structures.
259-- Each module provides an almost identical API, with the main
260-- difference being that the strict module uses 'Int' values for
261-- lengths and counts, while the lazy module uses 'Data.Int.Int64'
266-- A 'Text' value is a sequence of Unicode scalar values, as defined
268-- <http://www.unicode.org/versions/Unicode5.2.0/ch03.pdf#page=35 §3.9, definition D76 of the Unicode 5.2 standard >.
269-- As such, a 'Text' cannot contain values in the range U+D800 to
270-- U+DFFF inclusive. Haskell implementations admit all Unicode code
272-- (<http://www.unicode.org/versions/Unicode5.2.0/ch03.pdf#page=13 §3.4, definition D10 >)
273-- as 'Char' values, including code points from this invalid range.
274-- This means that there are some 'Char' values that are not valid
275-- Unicode scalar values, and the functions in this module must handle
278-- Within this module, many functions construct a 'Text' from one or
279-- more 'Char' values. Those functions will substitute 'Char' values
280-- that are not valid Unicode scalar values with the replacement
281-- character \"�\" (U+FFFD). Functions that perform this
282-- inspection and replacement are documented with the phrase
283-- \"Performs replacement on invalid scalar values\".
285-- (One reason for this policy of replacement is that internally, a
286-- 'Text' value is represented as packed UTF-16 data. Values in the
287-- range U+D800 through U+DFFF are used by UTF-16 to denote surrogate
288-- code points, and so cannot be represented. The functions replace
289-- invalid scalar values, instead of dropping them, as a security
290-- measure. For details, see
291-- <http://unicode.org/reports/tr36/#Deletion_of_Noncharacters Unicode Technical Report 36, §3.5 >.)
295-- Most of the functions in this module are subject to /fusion/,
296-- meaning that a pipeline of such functions will usually allocate at
297-- most one 'Text' value.
299-- As an example, consider the following pipeline:
301-- > import Data.Text as T
302-- > import Data.Text.Encoding as E
303-- > import Data.ByteString (ByteString)
305-- > countChars :: ByteString -> Int
306-- > countChars = T.length . T.toUpper . E.decodeUtf8
308-- From the type signatures involved, this looks like it should
309-- allocate one 'Data.ByteString.ByteString' value, and two 'Text'
310-- values. However, when a module is compiled with optimisation
311-- enabled under GHC, the two intermediate 'Text' values will be
312-- optimised away, and the function will be compiled down to a single
313-- loop over the source 'Data.ByteString.ByteString'.
315-- Functions that can be fused by the compiler are documented with the
316-- phrase \"Subject to fusion\".
318instance Eq Text where
319 Text arrA offA lenA == Text arrB offB lenB
320 | lenA == lenB = A.equal arrA offA arrB offB lenA
324instance Ord Text where
325 compare = compareText
327instance Show Text where
328 showsPrec p ps r = showsPrec p (unpack ps) r
330instance Read Text where
331 readsPrec p str = [(pack x,y) | (x,y) <- readsPrec p str]
333instance Monoid Text where
338instance IsString Text where
341#if __GLASGOW_HASKELL__ >= 708
342instance Exts.IsList Text where
343 type Item Text = Char
348#if defined(HAVE_DEEPSEQ)
352-- | This instance preserves data abstraction at the cost of inefficiency.
353-- We omit reflection services for the sake of data abstraction.
355-- This instance was created by copying the updated behavior of
356-- @"Data.Set".@'Data.Set.Set' and @"Data.Map".@'Data.Map.Map'. If you
357-- feel a mistake has been made, please feel free to submit
360-- The original discussion is archived here:
361-- <http://groups.google.com/group/haskell-cafe/browse_thread/thread/b5bbb1b28a7e525d/0639d46852575b93 could we get a Data instance for Data.Text.Text? >
363-- The followup discussion that changed the behavior of 'Data.Set.Set'
364-- and 'Data.Map.Map' is archived here:
365-- <http://markmail.org/message/trovdc6zkphyi3cr#query:+page:1+mid:a46der3iacwjcf6n+state:results Proposal: Allow gunfold for Data.Map, ... >
367instance Data Text where
368 gfoldl f z txt = z pack `f` (unpack txt)
369 toConstr _ = packConstr
370 gunfold k z c = case constrIndex c of
372 _ -> P.error "gunfold"
373 dataTypeOf _ = textDataType
376packConstr = mkConstr textDataType "pack" [] Prefix
378textDataType :: DataType
379textDataType = mkDataType "Data.Text.Text" [packConstr]
381-- | /O(n)/ Compare two 'Text' values lexicographically.
382compareText :: Text -> Text -> Ordering
383compareText ta@(Text _arrA _offA lenA) tb@(Text _arrB _offB lenB)
384 | lenA == 0 && lenB == 0 = EQ
388 | i >= lenA || j >= lenB = compare lenA lenB
391 | otherwise = go (i+di) (j+dj)
392 where Iter a di = iter ta i
393 Iter b dj = iter tb j
395-- -----------------------------------------------------------------------------
396-- * Conversion to/from 'Text'
398-- | /O(n)/ Convert a 'String' into a 'Text'. Subject to
399-- fusion. Performs replacement on invalid scalar values.
400pack :: String -> Text
401pack = unstream . S.map safe . S.streamList
402{-# INLINE [1] pack #-}
404-- | /O(n)/ Convert a 'Text' into a 'String'. Subject to fusion.
405unpack :: Text -> String
406unpack = S.unstreamList . stream
407{-# INLINE [1] unpack #-}
409-- | /O(n)/ Convert a literal string into a Text. Subject to fusion.
410unpackCString# :: Addr# -> Text
411unpackCString# addr# = unstream (S.streamCString# addr#)
412{-# NOINLINE unpackCString# #-}
414{-# RULES "TEXT literal" forall a.
415 unstream (S.map safe (S.streamList (GHC.unpackCString# a)))
416 = unpackCString# a #-}
418{-# RULES "TEXT literal UTF8" forall a.
419 unstream (S.map safe (S.streamList (GHC.unpackCStringUtf8# a)))
420 = unpackCString# a #-}
422{-# RULES "TEXT empty literal"
423 unstream (S.map safe (S.streamList []))
426{-# RULES "TEXT singleton literal" forall a.
427 unstream (S.map safe (S.streamList [a]))
430-- | /O(1)/ Convert a character into a Text. Subject to fusion.
431-- Performs replacement on invalid scalar values.
432singleton :: Char -> Text
433singleton = unstream . S.singleton . safe
434{-# INLINE [1] singleton #-}
436{-# RULES "TEXT singleton" forall a.
437 unstream (S.singleton (safe a))
440-- This is intended to reduce inlining bloat.
441singleton_ :: Char -> Text
442singleton_ c = Text (A.run x) 0 len
443 where x :: ST s (A.MArray s)
444 x = do arr <- A.new len
445 _ <- unsafeWrite arr 0 d
447 len | d < '\x10000' = 1
450{-# NOINLINE singleton_ #-}
452-- -----------------------------------------------------------------------------
455-- | /O(n)/ Adds a character to the front of a 'Text'. This function
456-- is more costly than its 'List' counterpart because it requires
457-- copying a new array. Subject to fusion. Performs replacement on
458-- invalid scalar values.
459cons :: Char -> Text -> Text
460cons c t = unstream (S.cons (safe c) (stream t))
465-- | /O(n)/ Adds a character to the end of a 'Text'. This copies the
466-- entire array in the process, unless fused. Subject to fusion.
467-- Performs replacement on invalid scalar values.
468snoc :: Text -> Char -> Text
469snoc t c = unstream (S.snoc (stream t) (safe c))
472-- | /O(n)/ Appends one 'Text' to the other by copying both of them
473-- into a new 'Text'. Subject to fusion.
474append :: Text -> Text -> Text
475append a@(Text arr1 off1 len1) b@(Text arr2 off2 len2)
478 | len > 0 = Text (A.run x) 0 len
479 | otherwise = overflowError "append"
482 x :: ST s (A.MArray s)
485 A.copyI arr 0 arr1 off1 len1
486 A.copyI arr len1 arr2 off2 len
488{-# NOINLINE append #-}
491"TEXT append -> fused" [~1] forall t1 t2.
492 append t1 t2 = unstream (S.append (stream t1) (stream t2))
493"TEXT append -> unfused" [1] forall t1 t2.
494 unstream (S.append (stream t1) (stream t2)) = append t1 t2
497-- | /O(1)/ Returns the first character of a 'Text', which must be
498-- non-empty. Subject to fusion.
500head t = S.head (stream t)
503-- | /O(1)/ Returns the first character and rest of a 'Text', or
504-- 'Nothing' if empty. Subject to fusion.
505uncons :: Text -> Maybe (Char, Text)
506uncons t@(Text arr off len)
508 | otherwise = Just (c, text arr (off+d) (len-d))
509 where Iter c d = iter t 0
510{-# INLINE [1] uncons #-}
512-- | Lifted from Control.Arrow and specialized.
513second :: (b -> c) -> (a,b) -> (a,c)
514second f (a, b) = (a, f b)
516-- | /O(1)/ Returns the last character of a 'Text', which must be
517-- non-empty. Subject to fusion.
519last (Text arr off len)
520 | len <= 0 = emptyError "last"
521 | n < 0xDC00 || n > 0xDFFF = unsafeChr n
522 | otherwise = U16.chr2 n0 n
523 where n = A.unsafeIndex arr (off+len-1)
524 n0 = A.unsafeIndex arr (off+len-2)
525{-# INLINE [1] last #-}
528"TEXT last -> fused" [~1] forall t.
529 last t = S.last (stream t)
530"TEXT last -> unfused" [1] forall t.
531 S.last (stream t) = last t
534-- | /O(1)/ Returns all characters after the head of a 'Text', which
535-- must be non-empty. Subject to fusion.
537tail t@(Text arr off len)
538 | len <= 0 = emptyError "tail"
539 | otherwise = text arr (off+d) (len-d)
541{-# INLINE [1] tail #-}
544"TEXT tail -> fused" [~1] forall t.
545 tail t = unstream (S.tail (stream t))
546"TEXT tail -> unfused" [1] forall t.
547 unstream (S.tail (stream t)) = tail t
550-- | /O(1)/ Returns all but the last character of a 'Text', which must
551-- be non-empty. Subject to fusion.
553init (Text arr off len) | len <= 0 = emptyError "init"
554 | n >= 0xDC00 && n <= 0xDFFF = text arr off (len-2)
555 | otherwise = text arr off (len-1)
557 n = A.unsafeIndex arr (off+len-1)
558{-# INLINE [1] init #-}
561"TEXT init -> fused" [~1] forall t.
562 init t = unstream (S.init (stream t))
563"TEXT init -> unfused" [1] forall t.
564 unstream (S.init (stream t)) = init t
567-- | /O(1)/ Tests whether a 'Text' is empty or not. Subject to
570null (Text _arr _off len) =
575{-# INLINE [1] null #-}
578"TEXT null -> fused" [~1] forall t.
579 null t = S.null (stream t)
580"TEXT null -> unfused" [1] forall t.
581 S.null (stream t) = null t
584-- | /O(1)/ Tests whether a 'Text' contains exactly one character.
586isSingleton :: Text -> Bool
587isSingleton = S.isSingleton . stream
588{-# INLINE isSingleton #-}
590-- | /O(n)/ Returns the number of characters in a 'Text'.
593length t = S.length (stream t)
596-- | /O(n)/ Compare the count of characters in a 'Text' to a number.
599-- This function gives the same answer as comparing against the result
600-- of 'length', but can short circuit if the count of characters is
601-- greater than the number, and hence be more efficient.
602compareLength :: Text -> Int -> Ordering
603compareLength t n = S.compareLengthI (stream t) n
604{-# INLINE [1] compareLength #-}
607"TEXT compareN/length -> compareLength" [~1] forall t n.
608 compare (length t) n = compareLength t n
612"TEXT ==N/length -> compareLength/==EQ" [~1] forall t n.
613 (==) (length t) n = compareLength t n == EQ
617"TEXT /=N/length -> compareLength//=EQ" [~1] forall t n.
618 (/=) (length t) n = compareLength t n /= EQ
622"TEXT <N/length -> compareLength/==LT" [~1] forall t n.
623 (<) (length t) n = compareLength t n == LT
627"TEXT <=N/length -> compareLength//=GT" [~1] forall t n.
628 (<=) (length t) n = compareLength t n /= GT
632"TEXT >N/length -> compareLength/==GT" [~1] forall t n.
633 (>) (length t) n = compareLength t n == GT
637"TEXT >=N/length -> compareLength//=LT" [~1] forall t n.
638 (>=) (length t) n = compareLength t n /= LT
641-- -----------------------------------------------------------------------------
643-- | /O(n)/ 'map' @f@ @t@ is the 'Text' obtained by applying @f@ to
644-- each element of @t@. Subject to fusion. Performs replacement on
645-- invalid scalar values.
646map :: (Char -> Char) -> Text -> Text
647map f t = unstream (S.map (safe . f) (stream t))
648{-# INLINE [1] map #-}
650-- | /O(n)/ The 'intercalate' function takes a 'Text' and a list of
651-- 'Text's and concatenates the list after interspersing the first
652-- argument between each element of the list.
653intercalate :: Text -> [Text] -> Text
654intercalate t = concat . (F.intersperse t)
655{-# INLINE intercalate #-}
657-- | /O(n)/ The 'intersperse' function takes a character and places it
658-- between the characters of a 'Text'. Subject to fusion. Performs
659-- replacement on invalid scalar values.
660intersperse :: Char -> Text -> Text
661intersperse c t = unstream (S.intersperse (safe c) (stream t))
662{-# INLINE intersperse #-}
664-- | /O(n)/ Reverse the characters of a string. Subject to fusion.
665reverse :: Text -> Text
666reverse t = S.reverse (stream t)
667{-# INLINE reverse #-}
669-- | /O(m+n)/ Replace every occurrence of one substring with another.
671-- In (unlikely) bad cases, this function's time complexity degrades
673replace :: Text -> Text -> Text -> Text
674replace needle@(Text _ _ neeLen)
675 (Text repArr repOff repLen)
676 haystack@(Text hayArr hayOff hayLen)
677 | neeLen == 0 = emptyError "replace"
678 | L.null ixs = haystack
679 | len > 0 = Text (A.run x) 0 len
682 ixs = indices needle haystack
683 len = hayLen - (neeLen - repLen) `mul` L.length ixs
684 x :: ST s (A.MArray s)
687 let loop (i:is) o d = do
690 A.copyI marr d hayArr (hayOff+o) d0
691 A.copyI marr d0 repArr repOff d1
692 loop is (i + neeLen) d1
693 loop [] o d = A.copyI marr d hayArr (hayOff+o) len
697-- ----------------------------------------------------------------------------
698-- ** Case conversions (folds)
702-- When case converting 'Text' values, do not use combinators like
703-- @map toUpper@ to case convert each character of a string
704-- individually, as this gives incorrect results according to the
705-- rules of some writing systems. The whole-string case conversion
706-- functions from this module, such as @toUpper@, obey the correct
707-- case conversion rules. As a result, these functions may map one
708-- input character to two or three output characters. For examples,
709-- see the documentation of each function.
711-- /Note/: In some languages, case conversion is a locale- and
712-- context-dependent operation. The case conversion functions in this
713-- module are /not/ locale sensitive. Programs that require locale
714-- sensitivity should use appropriate versions of the
715-- <http://hackage.haskell.org/package/text-icu-0.6.3.7/docs/Data-Text-ICU.html#g:4 case mapping functions from the text-icu package >.
717-- | /O(n)/ Convert a string to folded case. Subject to fusion.
719-- This function is mainly useful for performing caseless (also known
720-- as case insensitive) string comparisons.
722-- A string @x@ is a caseless match for a string @y@ if and only if:
724-- @toCaseFold x == toCaseFold y@
726-- The result string may be longer than the input string, and may
727-- differ from applying 'toLower' to the input string. For instance,
728-- the Armenian small ligature \"ﬓ\" (men now, U+FB13) is case
729-- folded to the sequence \"մ\" (men, U+0574) followed by
730-- \"ն\" (now, U+0576), while the Greek \"µ\" (micro sign,
731-- U+00B5) is case folded to \"μ\" (small letter mu, U+03BC)
733toCaseFold :: Text -> Text
734toCaseFold t = unstream (S.toCaseFold (stream t))
735{-# INLINE [0] toCaseFold #-}
737-- | /O(n)/ Convert a string to lower case, using simple case
738-- conversion. Subject to fusion.
740-- The result string may be longer than the input string. For
741-- instance, \"İ\" (Latin capital letter I with dot above,
742-- U+0130) maps to the sequence \"i\" (Latin small letter i, U+0069)
743-- followed by \" ̇\" (combining dot above, U+0307).
744toLower :: Text -> Text
745toLower t = unstream (S.toLower (stream t))
746{-# INLINE toLower #-}
748-- | /O(n)/ Convert a string to upper case, using simple case
749-- conversion. Subject to fusion.
751-- The result string may be longer than the input string. For
752-- instance, the German \"ß\" (eszett, U+00DF) maps to the
753-- two-letter sequence \"SS\".
754toUpper :: Text -> Text
755toUpper t = unstream (S.toUpper (stream t))
756{-# INLINE toUpper #-}
758-- | /O(n)/ Convert a string to title case, using simple case
759-- conversion. Subject to fusion.
761-- The first letter of the input is converted to title case, as is
762-- every subsequent letter that immediately follows a non-letter.
763-- Every letter that immediately follows another letter is converted
766-- The result string may be longer than the input string. For example,
767-- the Latin small ligature fl (U+FB02) is converted to the
768-- sequence Latin capital letter F (U+0046) followed by Latin small
771-- /Note/: this function does not take language or culture specific
772-- rules into account. For instance, in English, different style
773-- guides disagree on whether the book name \"The Hill of the Red
774-- Fox\" is correctly title cased—but this function will
775-- capitalize /every/ word.
776toTitle :: Text -> Text
777toTitle t = unstream (S.toTitle (stream t))
778{-# INLINE toTitle #-}
780-- | /O(n)/ Left-justify a string to the given length, using the
781-- specified fill character on the right. Subject to fusion.
782-- Performs replacement on invalid scalar values.
786-- > justifyLeft 7 'x' "foo" == "fooxxxx"
787-- > justifyLeft 3 'x' "foobar" == "foobar"
788justifyLeft :: Int -> Char -> Text -> Text
791 | otherwise = t `append` replicateChar (k-len) c
793{-# INLINE [1] justifyLeft #-}
796"TEXT justifyLeft -> fused" [~1] forall k c t.
797 justifyLeft k c t = unstream (S.justifyLeftI k c (stream t))
798"TEXT justifyLeft -> unfused" [1] forall k c t.
799 unstream (S.justifyLeftI k c (stream t)) = justifyLeft k c t
802-- | /O(n)/ Right-justify a string to the given length, using the
803-- specified fill character on the left. Performs replacement on
804-- invalid scalar values.
808-- > justifyRight 7 'x' "bar" == "xxxxbar"
809-- > justifyRight 3 'x' "foobar" == "foobar"
810justifyRight :: Int -> Char -> Text -> Text
813 | otherwise = replicateChar (k-len) c `append` t
815{-# INLINE justifyRight #-}
817-- | /O(n)/ Center a string to the given length, using the specified
818-- fill character on either side. Performs replacement on invalid
823-- > center 8 'x' "HS" = "xxxHSxxx"
824center :: Int -> Char -> Text -> Text
827 | otherwise = replicateChar l c `append` t `append` replicateChar r c
834-- | /O(n)/ The 'transpose' function transposes the rows and columns
835-- of its 'Text' argument. Note that this function uses 'pack',
836-- 'unpack', and the list version of transpose, and is thus not very
838transpose :: [Text] -> [Text]
839transpose ts = P.map pack (L.transpose (P.map unpack ts))
841-- -----------------------------------------------------------------------------
842-- * Reducing 'Text's (folds)
844-- | /O(n)/ 'foldl', applied to a binary operator, a starting value
845-- (typically the left-identity of the operator), and a 'Text',
846-- reduces the 'Text' using the binary operator, from left to right.
848foldl :: (a -> Char -> a) -> a -> Text -> a
849foldl f z t = S.foldl f z (stream t)
852-- | /O(n)/ A strict version of 'foldl'. Subject to fusion.
853foldl' :: (a -> Char -> a) -> a -> Text -> a
854foldl' f z t = S.foldl' f z (stream t)
857-- | /O(n)/ A variant of 'foldl' that has no starting value argument,
858-- and thus must be applied to a non-empty 'Text'. Subject to fusion.
859foldl1 :: (Char -> Char -> Char) -> Text -> Char
860foldl1 f t = S.foldl1 f (stream t)
863-- | /O(n)/ A strict version of 'foldl1'. Subject to fusion.
864foldl1' :: (Char -> Char -> Char) -> Text -> Char
865foldl1' f t = S.foldl1' f (stream t)
866{-# INLINE foldl1' #-}
868-- | /O(n)/ 'foldr', applied to a binary operator, a starting value
869-- (typically the right-identity of the operator), and a 'Text',
870-- reduces the 'Text' using the binary operator, from right to left.
872foldr :: (Char -> a -> a) -> a -> Text -> a
873foldr f z t = S.foldr f z (stream t)
876-- | /O(n)/ A variant of 'foldr' that has no starting value argument,
877-- and thus must be applied to a non-empty 'Text'. Subject to
879foldr1 :: (Char -> Char -> Char) -> Text -> Char
880foldr1 f t = S.foldr1 f (stream t)
883-- -----------------------------------------------------------------------------
886-- | /O(n)/ Concatenate a list of 'Text's.
887concat :: [Text] -> Text
888concat ts = case ts' of
891 _ -> Text (A.run go) 0 len
893 ts' = L.filter (not . null) ts
894 len = sumP "concat" $ L.map lengthWord16 ts'
895 go :: ST s (A.MArray s)
898 let step i (Text a o l) =
899 let !j = i + l in A.copyI arr i a o j >> return j
900 foldM step 0 ts' >> return arr
902-- | /O(n)/ Map a function over a 'Text' that results in a 'Text', and
903-- concatenate the results.
904concatMap :: (Char -> Text) -> Text -> Text
905concatMap f = concat . foldr ((:) . f) []
906{-# INLINE concatMap #-}
908-- | /O(n)/ 'any' @p@ @t@ determines whether any character in the
909-- 'Text' @t@ satisifes the predicate @p@. Subject to fusion.
910any :: (Char -> Bool) -> Text -> Bool
911any p t = S.any p (stream t)
914-- | /O(n)/ 'all' @p@ @t@ determines whether all characters in the
915-- 'Text' @t@ satisify the predicate @p@. Subject to fusion.
916all :: (Char -> Bool) -> Text -> Bool
917all p t = S.all p (stream t)
920-- | /O(n)/ 'maximum' returns the maximum value from a 'Text', which
921-- must be non-empty. Subject to fusion.
922maximum :: Text -> Char
923maximum t = S.maximum (stream t)
924{-# INLINE maximum #-}
926-- | /O(n)/ 'minimum' returns the minimum value from a 'Text', which
927-- must be non-empty. Subject to fusion.
928minimum :: Text -> Char
929minimum t = S.minimum (stream t)
930{-# INLINE minimum #-}
932-- -----------------------------------------------------------------------------
935-- | /O(n)/ 'scanl' is similar to 'foldl', but returns a list of
936-- successive reduced values from the left. Subject to fusion.
937-- Performs replacement on invalid scalar values.
939-- > scanl f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...]
943-- > last (scanl f z xs) == foldl f z xs.
944scanl :: (Char -> Char -> Char) -> Char -> Text -> Text
945scanl f z t = unstream (S.scanl g z (stream t))
946 where g a b = safe (f a b)
949-- | /O(n)/ 'scanl1' is a variant of 'scanl' that has no starting
950-- value argument. Subject to fusion. Performs replacement on
951-- invalid scalar values.
953-- > scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]
954scanl1 :: (Char -> Char -> Char) -> Text -> Text
955scanl1 f t | null t = empty
956 | otherwise = scanl f (unsafeHead t) (unsafeTail t)
959-- | /O(n)/ 'scanr' is the right-to-left dual of 'scanl'. Performs
960-- replacement on invalid scalar values.
962-- > scanr f v == reverse . scanl (flip f) v . reverse
963scanr :: (Char -> Char -> Char) -> Char -> Text -> Text
964scanr f z = S.reverse . S.reverseScanr g z . reverseStream
965 where g a b = safe (f a b)
968-- | /O(n)/ 'scanr1' is a variant of 'scanr' that has no starting
969-- value argument. Subject to fusion. Performs replacement on
970-- invalid scalar values.
971scanr1 :: (Char -> Char -> Char) -> Text -> Text
972scanr1 f t | null t = empty
973 | otherwise = scanr f (last t) (init t)
976-- | /O(n)/ Like a combination of 'map' and 'foldl''. Applies a
977-- function to each element of a 'Text', passing an accumulating
978-- parameter from left to right, and returns a final 'Text'. Performs
979-- replacement on invalid scalar values.
980mapAccumL :: (a -> Char -> (a,Char)) -> a -> Text -> (a, Text)
981mapAccumL f z0 = S.mapAccumL g z0 . stream
982 where g a b = second safe (f a b)
983{-# INLINE mapAccumL #-}
985-- | The 'mapAccumR' function behaves like a combination of 'map' and
986-- a strict 'foldr'; it applies a function to each element of a
987-- 'Text', passing an accumulating parameter from right to left, and
988-- returning a final value of this accumulator together with the new
990-- Performs replacement on invalid scalar values.
991mapAccumR :: (a -> Char -> (a,Char)) -> a -> Text -> (a, Text)
992mapAccumR f z0 = second reverse . S.mapAccumL g z0 . reverseStream
993 where g a b = second safe (f a b)
994{-# INLINE mapAccumR #-}
996-- -----------------------------------------------------------------------------
997-- ** Generating and unfolding 'Text's
999-- | /O(n*m)/ 'replicate' @n@ @t@ is a 'Text' consisting of the input
1000-- @t@ repeated @n@ times.
1001replicate :: Int -> Text -> Text
1002replicate n t@(Text a o l)
1003 | n <= 0 || l <= 0 = empty
1005 | isSingleton t = replicateChar n (unsafeHead t)
1006 | otherwise = Text (A.run x) 0 len
1009 x :: ST s (A.MArray s)
1012 let loop !d !i | i >= n = return arr
1013 | otherwise = let m = d + l
1014 in A.copyI arr d a o m >> loop m (i+1)
1016{-# INLINE [1] replicate #-}
1019"TEXT replicate/singleton -> replicateChar" [~1] forall n c.
1020 replicate n (singleton c) = replicateChar n c
1023-- | /O(n)/ 'replicateChar' @n@ @c@ is a 'Text' of length @n@ with @c@ the
1024-- value of every element. Subject to fusion.
1025replicateChar :: Int -> Char -> Text
1026replicateChar n c = unstream (S.replicateCharI n (safe c))
1027{-# INLINE replicateChar #-}
1029-- | /O(n)/, where @n@ is the length of the result. The 'unfoldr'
1030-- function is analogous to the List 'L.unfoldr'. 'unfoldr' builds a
1031-- 'Text' from a seed value. The function takes the element and
1032-- returns 'Nothing' if it is done producing the 'Text', otherwise
1033-- 'Just' @(a,b)@. In this case, @a@ is the next 'Char' in the
1034-- string, and @b@ is the seed value for further production. Subject
1035-- to fusion. Performs replacement on invalid scalar values.
1036unfoldr :: (a -> Maybe (Char,a)) -> a -> Text
1037unfoldr f s = unstream (S.unfoldr (firstf safe . f) s)
1038{-# INLINE unfoldr #-}
1040-- | /O(n)/ Like 'unfoldr', 'unfoldrN' builds a 'Text' from a seed
1041-- value. However, the length of the result should be limited by the
1042-- first argument to 'unfoldrN'. This function is more efficient than
1043-- 'unfoldr' when the maximum length of the result is known and
1044-- correct, otherwise its performance is similar to 'unfoldr'. Subject
1045-- to fusion. Performs replacement on invalid scalar values.
1046unfoldrN :: Int -> (a -> Maybe (Char,a)) -> a -> Text
1047unfoldrN n f s = unstream (S.unfoldrN n (firstf safe . f) s)
1048{-# INLINE unfoldrN #-}
1050-- -----------------------------------------------------------------------------
1053-- | /O(n)/ 'take' @n@, applied to a 'Text', returns the prefix of the
1054-- 'Text' of length @n@, or the 'Text' itself if @n@ is greater than
1055-- the length of the Text. Subject to fusion.
1056take :: Int -> Text -> Text
1057take n t@(Text arr off len)
1060 | otherwise = text arr off (iterN n t)
1061{-# INLINE [1] take #-}
1063iterN :: Int -> Text -> Int
1064iterN n t@(Text _arr _off len) = loop 0 0
1066 | i >= len || cnt >= n = i
1067 | otherwise = loop (i+d) (cnt+1)
1071"TEXT take -> fused" [~1] forall n t.
1072 take n t = unstream (S.take n (stream t))
1073"TEXT take -> unfused" [1] forall n t.
1074 unstream (S.take n (stream t)) = take n t
1077-- | /O(n)/ 'takeEnd' @n@ @t@ returns the suffix remaining after
1078-- taking @n@ characters from the end of @t@.
1082-- > takeEnd 3 "foobar" == "bar"
1083takeEnd :: Int -> Text -> Text
1084takeEnd n t@(Text arr off len)
1087 | otherwise = text arr (off+i) (len-i)
1088 where i = iterNEnd n t
1090iterNEnd :: Int -> Text -> Int
1091iterNEnd n t@(Text _arr _off len) = loop (len-1) n
1095 | otherwise = loop (i+d) (m-1)
1096 where d = reverseIter_ t i
1098-- | /O(n)/ 'drop' @n@, applied to a 'Text', returns the suffix of the
1099-- 'Text' after the first @n@ characters, or the empty 'Text' if @n@
1100-- is greater than the length of the 'Text'. Subject to fusion.
1101drop :: Int -> Text -> Text
1102drop n t@(Text arr off len)
1105 | otherwise = text arr (off+i) (len-i)
1107{-# INLINE [1] drop #-}
1110"TEXT drop -> fused" [~1] forall n t.
1111 drop n t = unstream (S.drop n (stream t))
1112"TEXT drop -> unfused" [1] forall n t.
1113 unstream (S.drop n (stream t)) = drop n t
1116-- | /O(n)/ 'dropEnd' @n@ @t@ returns the prefix remaining after
1117-- dropping @n@ characters from the end of @t@.
1121-- > dropEnd 3 "foobar" == "foo"
1122dropEnd :: Int -> Text -> Text
1123dropEnd n t@(Text arr off len)
1126 | otherwise = text arr off (iterNEnd n t)
1128-- | /O(n)/ 'takeWhile', applied to a predicate @p@ and a 'Text',
1129-- returns the longest prefix (possibly empty) of elements that
1130-- satisfy @p@. Subject to fusion.
1131takeWhile :: (Char -> Bool) -> Text -> Text
1132takeWhile p t@(Text arr off len) = loop 0
1133 where loop !i | i >= len = t
1135 | otherwise = text arr off i
1136 where Iter c d = iter t i
1137{-# INLINE [1] takeWhile #-}
1140"TEXT takeWhile -> fused" [~1] forall p t.
1141 takeWhile p t = unstream (S.takeWhile p (stream t))
1142"TEXT takeWhile -> unfused" [1] forall p t.
1143 unstream (S.takeWhile p (stream t)) = takeWhile p t
1146-- | /O(n)/ 'dropWhile' @p@ @t@ returns the suffix remaining after
1147-- 'takeWhile' @p@ @t@. Subject to fusion.
1148dropWhile :: (Char -> Bool) -> Text -> Text
1149dropWhile p t@(Text arr off len) = loop 0 0
1150 where loop !i !l | l >= len = empty
1151 | p c = loop (i+d) (l+d)
1152 | otherwise = Text arr (off+i) (len-l)
1153 where Iter c d = iter t i
1154{-# INLINE [1] dropWhile #-}
1157"TEXT dropWhile -> fused" [~1] forall p t.
1158 dropWhile p t = unstream (S.dropWhile p (stream t))
1159"TEXT dropWhile -> unfused" [1] forall p t.
1160 unstream (S.dropWhile p (stream t)) = dropWhile p t
1163-- | /O(n)/ 'dropWhileEnd' @p@ @t@ returns the prefix remaining after
1164-- dropping characters that fail the predicate @p@ from the end of
1165-- @t@. Subject to fusion.
1168-- > dropWhileEnd (=='.') "foo..." == "foo"
1169dropWhileEnd :: (Char -> Bool) -> Text -> Text
1170dropWhileEnd p t@(Text arr off len) = loop (len-1) len
1171 where loop !i !l | l <= 0 = empty
1172 | p c = loop (i+d) (l+d)
1173 | otherwise = Text arr off l
1174 where (c,d) = reverseIter t i
1175{-# INLINE [1] dropWhileEnd #-}
1178"TEXT dropWhileEnd -> fused" [~1] forall p t.
1179 dropWhileEnd p t = S.reverse (S.dropWhile p (S.reverseStream t))
1180"TEXT dropWhileEnd -> unfused" [1] forall p t.
1181 S.reverse (S.dropWhile p (S.reverseStream t)) = dropWhileEnd p t
1184-- | /O(n)/ 'dropAround' @p@ @t@ returns the substring remaining after
1185-- dropping characters that fail the predicate @p@ from both the
1186-- beginning and end of @t@. Subject to fusion.
1187dropAround :: (Char -> Bool) -> Text -> Text
1188dropAround p = dropWhile p . dropWhileEnd p
1189{-# INLINE [1] dropAround #-}
1191-- | /O(n)/ Remove leading white space from a string. Equivalent to:
1193-- > dropWhile isSpace
1194stripStart :: Text -> Text
1195stripStart = dropWhile isSpace
1196{-# INLINE [1] stripStart #-}
1198-- | /O(n)/ Remove trailing white space from a string. Equivalent to:
1200-- > dropWhileEnd isSpace
1201stripEnd :: Text -> Text
1202stripEnd = dropWhileEnd isSpace
1203{-# INLINE [1] stripEnd #-}
1205-- | /O(n)/ Remove leading and trailing white space from a string.
1208-- > dropAround isSpace
1209strip :: Text -> Text
1210strip = dropAround isSpace
1211{-# INLINE [1] strip #-}
1213-- | /O(n)/ 'splitAt' @n t@ returns a pair whose first element is a
1214-- prefix of @t@ of length @n@, and whose second is the remainder of
1215-- the string. It is equivalent to @('take' n t, 'drop' n t)@.
1216splitAt :: Int -> Text -> (Text, Text)
1217splitAt n t@(Text arr off len)
1218 | n <= 0 = (empty, t)
1219 | n >= len = (t, empty)
1220 | otherwise = let k = iterN n t
1221 in (text arr off k, text arr (off+k) (len-k))
1223-- | /O(n)/ 'span', applied to a predicate @p@ and text @t@, returns
1224-- a pair whose first element is the longest prefix (possibly empty)
1225-- of @t@ of elements that satisfy @p@, and whose second is the
1226-- remainder of the list.
1227span :: (Char -> Bool) -> Text -> (Text, Text)
1228span p t = case span_ p t of
1229 (# hd,tl #) -> (hd,tl)
1232-- | /O(n)/ 'break' is like 'span', but the prefix returned is
1233-- over elements that fail the predicate @p@.
1234break :: (Char -> Bool) -> Text -> (Text, Text)
1235break p = span (not . p)
1238-- | /O(n)/ Group characters in a string according to a predicate.
1239groupBy :: (Char -> Char -> Bool) -> Text -> [Text]
1242 loop t@(Text arr off len)
1244 | otherwise = text arr off n : loop (text arr (off+n) (len-n))
1245 where Iter c d = iter t 0
1246 n = d + findAIndexOrEnd (not . p c) (Text arr (off+d) (len-d))
1248-- | Returns the /array/ index (in units of 'Word16') at which a
1249-- character may be found. This is /not/ the same as the logical
1250-- index returned by e.g. 'findIndex'.
1251findAIndexOrEnd :: (Char -> Bool) -> Text -> Int
1252findAIndexOrEnd q t@(Text _arr _off len) = go 0
1253 where go !i | i >= len || q c = i
1254 | otherwise = go (i+d)
1255 where Iter c d = iter t i
1257-- | /O(n)/ Group characters in a string by equality.
1258group :: Text -> [Text]
1261-- | /O(n)/ Return all initial segments of the given 'Text', shortest
1263inits :: Text -> [Text]
1264inits t@(Text arr off len) = loop 0
1265 where loop i | i >= len = [t]
1266 | otherwise = Text arr off i : loop (i + iter_ t i)
1268-- | /O(n)/ Return all final segments of the given 'Text', longest
1270tails :: Text -> [Text]
1271tails t | null t = [empty]
1272 | otherwise = t : tails (unsafeTail t)
1276-- Splitting functions in this library do not perform character-wise
1277-- copies to create substrings; they just construct new 'Text's that
1278-- are slices of the original.
1280-- | /O(m+n)/ Break a 'Text' into pieces separated by the first
1281-- 'Text' argument, consuming the delimiter. An empty delimiter is
1282-- invalid, and will cause an error to be raised.
1286-- > splitOn "\r\n" "a\r\nb\r\nd\r\ne" == ["a","b","d","e"]
1287-- > splitOn "aaa" "aaaXaaaXaaaXaaa" == ["","X","X","X",""]
1288-- > splitOn "x" "x" == ["",""]
1292-- > intercalate s . splitOn s == id
1293-- > splitOn (singleton c) == split (==c)
1295-- In (unlikely) bad cases, this function's time complexity degrades
1297splitOn :: Text -> Text -> [Text]
1298splitOn pat@(Text _ _ l) src@(Text arr off len)
1299 | l <= 0 = emptyError "splitOn"
1300 | isSingleton pat = split (== unsafeHead pat) src
1301 | otherwise = go 0 (indices pat src)
1303 go !s (x:xs) = text arr (s+off) (x-s) : go (x+l) xs
1304 go s _ = [text arr (s+off) (len-s)]
1305{-# INLINE [1] splitOn #-}
1308"TEXT splitOn/singleton -> split/==" [~1] forall c t.
1309 splitOn (singleton c) t = split (==c) t
1312-- | /O(n)/ Splits a 'Text' into components delimited by separators,
1313-- where the predicate returns True for a separator element. The
1314-- resulting components do not contain the separators. Two adjacent
1315-- separators result in an empty component in the output. eg.
1317-- > split (=='a') "aabbaca" == ["","","bb","c",""]
1318-- > split (=='a') "" == [""]
1319split :: (Char -> Bool) -> Text -> [Text]
1320split _ t@(Text _off _arr 0) = [t]
1322 where loop s | null s' = [l]
1323 | otherwise = l : loop (unsafeTail s')
1324 where (# l, s' #) = span_ (not . p) s
1327-- | /O(n)/ Splits a 'Text' into components of length @k@. The last
1328-- element may be shorter than the other chunks, depending on the
1329-- length of the input. Examples:
1331-- > chunksOf 3 "foobarbaz" == ["foo","bar","baz"]
1332-- > chunksOf 4 "haskell.org" == ["hask","ell.","org"]
1333chunksOf :: Int -> Text -> [Text]
1336 go t = case splitAt k t of
1337 (a,b) | null a -> []
1338 | otherwise -> a : go b
1339{-# INLINE chunksOf #-}
1341-- ----------------------------------------------------------------------------
1344-------------------------------------------------------------------------------
1345-- ** Searching with a predicate
1347-- | /O(n)/ The 'find' function takes a predicate and a 'Text', and
1348-- returns the first element matching the predicate, or 'Nothing' if
1349-- there is no such element.
1350find :: (Char -> Bool) -> Text -> Maybe Char
1351find p t = S.findBy p (stream t)
1354-- | /O(n)/ The 'partition' function takes a predicate and a 'Text',
1355-- and returns the pair of 'Text's with elements which do and do not
1356-- satisfy the predicate, respectively; i.e.
1358-- > partition p t == (filter p t, filter (not . p) t)
1359partition :: (Char -> Bool) -> Text -> (Text, Text)
1360partition p t = (filter p t, filter (not . p) t)
1361{-# INLINE partition #-}
1363-- | /O(n)/ 'filter', applied to a predicate and a 'Text',
1364-- returns a 'Text' containing those characters that satisfy the
1366filter :: (Char -> Bool) -> Text -> Text
1367filter p t = unstream (S.filter p (stream t))
1368{-# INLINE filter #-}
1370-- | /O(n+m)/ Find the first instance of @needle@ (which must be
1371-- non-'null') in @haystack@. The first element of the returned tuple
1372-- is the prefix of @haystack@ before @needle@ is matched. The second
1373-- is the remainder of @haystack@, starting with the match.
1377-- > breakOn "::" "a::b::c" ==> ("a", "::b::c")
1378-- > breakOn "/" "foobar" ==> ("foobar", "")
1382-- > append prefix match == haystack
1383-- > where (prefix, match) = breakOn needle haystack
1385-- If you need to break a string by a substring repeatedly (e.g. you
1386-- want to break on every instance of a substring), use 'breakOnAll'
1387-- instead, as it has lower startup overhead.
1389-- In (unlikely) bad cases, this function's time complexity degrades
1391breakOn :: Text -> Text -> (Text, Text)
1392breakOn pat src@(Text arr off len)
1393 | null pat = emptyError "breakOn"
1394 | otherwise = case indices pat src of
1396 (x:_) -> (text arr off x, text arr (off+x) (len-x))
1397{-# INLINE breakOn #-}
1399-- | /O(n+m)/ Similar to 'breakOn', but searches from the end of the
1402-- The first element of the returned tuple is the prefix of @haystack@
1403-- up to and including the last match of @needle@. The second is the
1404-- remainder of @haystack@, following the match.
1406-- > breakOnEnd "::" "a::b::c" ==> ("a::b::", "c")
1407breakOnEnd :: Text -> Text -> (Text, Text)
1408breakOnEnd pat src = (reverse b, reverse a)
1409 where (a,b) = breakOn (reverse pat) (reverse src)
1410{-# INLINE breakOnEnd #-}
1412-- | /O(n+m)/ Find all non-overlapping instances of @needle@ in
1413-- @haystack@. Each element of the returned list consists of a pair:
1415-- * The entire string prior to the /k/th match (i.e. the prefix)
1417-- * The /k/th match, followed by the remainder of the string
1421-- > breakOnAll "::" ""
1423-- > breakOnAll "/" "a/b/c/"
1424-- > ==> [("a", "/b/c/"), ("a/b", "/c/"), ("a/b/c", "/")]
1426-- In (unlikely) bad cases, this function's time complexity degrades
1429-- The @needle@ parameter may not be empty.
1430breakOnAll :: Text -- ^ @needle@ to search for
1431 -> Text -- ^ @haystack@ in which to search
1433breakOnAll pat src@(Text arr off slen)
1434 | null pat = emptyError "breakOnAll"
1435 | otherwise = L.map step (indices pat src)
1437 step x = (chunk 0 x, chunk x (slen-x))
1438 chunk !n !l = text arr (n+off) l
1439{-# INLINE breakOnAll #-}
1441-------------------------------------------------------------------------------
1442-- ** Indexing 'Text's
1446-- If you think of a 'Text' value as an array of 'Char' values (which
1447-- it is not), you run the risk of writing inefficient code.
1449-- An idiom that is common in some languages is to find the numeric
1450-- offset of a character or substring, then use that number to split
1451-- or trim the searched string. With a 'Text' value, this approach
1452-- would require two /O(n)/ operations: one to perform the search, and
1453-- one to operate from wherever the search ended.
1455-- For example, suppose you have a string that you want to split on
1456-- the substring @\"::\"@, such as @\"foo::bar::quux\"@. Instead of
1457-- searching for the index of @\"::\"@ and taking the substrings
1458-- before and after that index, you would instead use @breakOnAll \"::\"@.
1460-- | /O(n)/ 'Text' index (subscript) operator, starting from 0.
1461index :: Text -> Int -> Char
1462index t n = S.index (stream t) n
1465-- | /O(n)/ The 'findIndex' function takes a predicate and a 'Text'
1466-- and returns the index of the first element in the 'Text' satisfying
1467-- the predicate. Subject to fusion.
1468findIndex :: (Char -> Bool) -> Text -> Maybe Int
1469findIndex p t = S.findIndex p (stream t)
1470{-# INLINE findIndex #-}
1472-- | /O(n+m)/ The 'count' function returns the number of times the
1473-- query string appears in the given 'Text'. An empty query string is
1474-- invalid, and will cause an error to be raised.
1476-- In (unlikely) bad cases, this function's time complexity degrades
1478count :: Text -> Text -> Int
1480 | null pat = emptyError "count"
1481 | isSingleton pat = countChar (unsafeHead pat) src
1482 | otherwise = L.length (indices pat src)
1483{-# INLINE [1] count #-}
1486"TEXT count/singleton -> countChar" [~1] forall c t.
1487 count (singleton c) t = countChar c t
1490-- | /O(n)/ The 'countChar' function returns the number of times the
1491-- query element appears in the given 'Text'. Subject to fusion.
1492countChar :: Char -> Text -> Int
1493countChar c t = S.countChar c (stream t)
1494{-# INLINE countChar #-}
1496-------------------------------------------------------------------------------
1499-- | /O(n)/ 'zip' takes two 'Text's and returns a list of
1500-- corresponding pairs of bytes. If one input 'Text' is short,
1501-- excess elements of the longer 'Text' are discarded. This is
1502-- equivalent to a pair of 'unpack' operations.
1503zip :: Text -> Text -> [(Char,Char)]
1504zip a b = S.unstreamList $ S.zipWith (,) (stream a) (stream b)
1505{-# INLINE [0] zip #-}
1507-- | /O(n)/ 'zipWith' generalises 'zip' by zipping with the function
1508-- given as the first argument, instead of a tupling function.
1509-- Performs replacement on invalid scalar values.
1510zipWith :: (Char -> Char -> Char) -> Text -> Text -> Text
1511zipWith f t1 t2 = unstream (S.zipWith g (stream t1) (stream t2))
1512 where g a b = safe (f a b)
1513{-# INLINE [0] zipWith #-}
1515-- | /O(n)/ Breaks a 'Text' up into a list of words, delimited by 'Char's
1516-- representing white space.
1517words :: Text -> [Text]
1518words t@(Text arr off len) = loop 0 0
1521 | n >= len = if start == n
1523 else [Text arr (start+off) (n-start)]
1526 then loop (start+1) (start+1)
1527 else Text arr (start+off) (n-start) : loop (n+d) (n+d)
1528 | otherwise = loop start (n+d)
1529 where Iter c d = iter t n
1532-- | /O(n)/ Breaks a 'Text' up into a list of 'Text's at
1533-- newline 'Char's. The resulting strings do not contain newlines.
1534lines :: Text -> [Text]
1535lines ps | null ps = []
1536 | otherwise = h : if null t
1538 else lines (unsafeTail t)
1539 where (# h,t #) = span_ (/= '\n') ps
1543-- | /O(n)/ Portably breaks a 'Text' up into a list of 'Text's at line
1546-- A line boundary is considered to be either a line feed, a carriage
1547-- return immediately followed by a line feed, or a carriage return.
1548-- This accounts for both Unix and Windows line ending conventions,
1549-- and for the old convention used on Mac OS 9 and earlier.
1550lines' :: Text -> [Text]
1551lines' ps | null ps = []
1552 | otherwise = h : case uncons t of
1555 | c == '\n' -> lines t'
1556 | c == '\r' -> case uncons t' of
1557 Just ('\n',t'') -> lines t''
1559 where (h,t) = span notEOL ps
1560 notEOL c = c /= '\n' && c /= '\r'
1561{-# INLINE lines' #-}
1564-- | /O(n)/ Joins lines, after appending a terminating newline to
1566unlines :: [Text] -> Text
1567unlines = concat . L.map (`snoc` '\n')
1568{-# INLINE unlines #-}
1570-- | /O(n)/ Joins words using single space characters.
1571unwords :: [Text] -> Text
1572unwords = intercalate (singleton ' ')
1573{-# INLINE unwords #-}
1575-- | /O(n)/ The 'isPrefixOf' function takes two 'Text's and returns
1576-- 'True' iff the first is a prefix of the second. Subject to fusion.
1577isPrefixOf :: Text -> Text -> Bool
1578isPrefixOf a@(Text _ _ alen) b@(Text _ _ blen) =
1579 alen <= blen && S.isPrefixOf (stream a) (stream b)
1580{-# INLINE [1] isPrefixOf #-}
1583"TEXT isPrefixOf -> fused" [~1] forall s t.
1584 isPrefixOf s t = S.isPrefixOf (stream s) (stream t)
1587-- | /O(n)/ The 'isSuffixOf' function takes two 'Text's and returns
1588-- 'True' iff the first is a suffix of the second.
1589isSuffixOf :: Text -> Text -> Bool
1590isSuffixOf a@(Text _aarr _aoff alen) b@(Text barr boff blen) =
1592 where d = blen - alen
1594 | otherwise = Text barr (boff+d) alen
1595{-# INLINE isSuffixOf #-}
1597-- | /O(n+m)/ The 'isInfixOf' function takes two 'Text's and returns
1598-- 'True' iff the first is contained, wholly and intact, anywhere
1599-- within the second.
1601-- In (unlikely) bad cases, this function's time complexity degrades
1603isInfixOf :: Text -> Text -> Bool
1604isInfixOf needle haystack
1605 | null needle = True
1606 | isSingleton needle = S.elem (unsafeHead needle) . S.stream $ haystack
1607 | otherwise = not . L.null . indices needle $ haystack
1608{-# INLINE [1] isInfixOf #-}
1611"TEXT isInfixOf/singleton -> S.elem/S.stream" [~1] forall n h.
1612 isInfixOf (singleton n) h = S.elem n (S.stream h)
1615-------------------------------------------------------------------------------
1618-- | /O(n)/ Return the suffix of the second string if its prefix
1619-- matches the entire first string.
1623-- > stripPrefix "foo" "foobar" == Just "bar"
1624-- > stripPrefix "" "baz" == Just "baz"
1625-- > stripPrefix "foo" "quux" == Nothing
1627-- This is particularly useful with the @ViewPatterns@ extension to
1630-- > {-# LANGUAGE ViewPatterns #-}
1631-- > import Data.Text as T
1633-- > fnordLength :: Text -> Int
1634-- > fnordLength (stripPrefix "fnord" -> Just suf) = T.length suf
1635-- > fnordLength _ = -1
1636stripPrefix :: Text -> Text -> Maybe Text
1637stripPrefix p@(Text _arr _off plen) t@(Text arr off len)
1638 | p `isPrefixOf` t = Just $! text arr (off+plen) (len-plen)
1639 | otherwise = Nothing
1641-- | /O(n)/ Find the longest non-empty common prefix of two strings
1642-- and return it, along with the suffixes of each string at which they
1645-- If the strings do not have a common prefix or either one is empty,
1646-- this function returns 'Nothing'.
1650-- > commonPrefixes "foobar" "fooquux" == Just ("foo","bar","quux")
1651-- > commonPrefixes "veeble" "fetzer" == Nothing
1652-- > commonPrefixes "" "baz" == Nothing
1653commonPrefixes :: Text -> Text -> Maybe (Text,Text,Text)
1654commonPrefixes t0@(Text arr0 off0 len0) t1@(Text arr1 off1 len1) = go 0 0
1656 go !i !j | i < len0 && j < len1 && a == b = go (i+d0) (j+d1)
1657 | i > 0 = Just (Text arr0 off0 i,
1658 text arr0 (off0+i) (len0-i),
1659 text arr1 (off1+j) (len1-j))
1660 | otherwise = Nothing
1661 where Iter a d0 = iter t0 i
1662 Iter b d1 = iter t1 j
1664-- | /O(n)/ Return the prefix of the second string if its suffix
1665-- matches the entire first string.
1669-- > stripSuffix "bar" "foobar" == Just "foo"
1670-- > stripSuffix "" "baz" == Just "baz"
1671-- > stripSuffix "foo" "quux" == Nothing
1673-- This is particularly useful with the @ViewPatterns@ extension to
1676-- > {-# LANGUAGE ViewPatterns #-}
1677-- > import Data.Text as T
1679-- > quuxLength :: Text -> Int
1680-- > quuxLength (stripSuffix "quux" -> Just pre) = T.length pre
1681-- > quuxLength _ = -1
1682stripSuffix :: Text -> Text -> Maybe Text
1683stripSuffix p@(Text _arr _off plen) t@(Text arr off len)
1684 | p `isSuffixOf` t = Just $! text arr off (len-plen)
1685 | otherwise = Nothing
1687-- | Add a list of non-negative numbers. Errors out on overflow.
1688sumP :: String -> [Int] -> Int
1691 | ax >= 0 = go ax xs
1692 | otherwise = overflowError fun
1696emptyError :: String -> a
1697emptyError fun = P.error $ "Data.Text." ++ fun ++ ": empty input"
1699overflowError :: String -> a
1700overflowError fun = P.error $ "Data.Text." ++ fun ++ ": size overflow"
1702-- | /O(n)/ Make a distinct copy of the given string, sharing no
1703-- storage with the original string.
1705-- As an example, suppose you read a large string, of which you need
1706-- only a small portion. If you do not use 'copy', the entire original
1707-- array will be kept alive in memory by the smaller string. Making a
1708-- copy \"breaks the link\" to the original array, allowing it to be
1709-- garbage collected if there are no other live references to it.
1711copy (Text arr off len) = Text (A.run go) 0 len
1713 go :: ST s (A.MArray s)
1716 A.copyI marr 0 arr off len
keysesc to close
- j k
- move down, up
- enter
- open
- esc
- back, or up a level
- 1 2 3 4
- readme, files, commits, refs
- /
- filter
- y
- copy the clone command
- c
- compare the chosen commit with another (or shift-click both)
- ?
- show or hide this list