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
149 -- ** Breaking into many substrings
155 -- ** Breaking into lines and words
193 -- * Low level operations
198import Prelude (Char, Bool(..), Int, Maybe(..), String,
199 Eq(..), Ord(..), Ordering(..), (++),
201 (&&), (||), (+), (-), (.), ($), ($!), (>>),
202 not, return, otherwise, quot)
203#if defined(HAVE_DEEPSEQ)
204import Control.DeepSeq (NFData(rnf))
207import Control.Exception (assert)
209import Data.Char (isSpace)
210import Data.Data (Data(gfoldl, toConstr, gunfold, dataTypeOf), constrIndex,
211 Constr, mkConstr, DataType, mkDataType, Fixity(Prefix))
212import Control.Monad (foldM)
213import Control.Monad.ST (ST)
214import qualified Data.Text.Array as A
215import qualified Data.List as L
216import Data.Binary (Binary(get, put))
217import Data.Monoid (Monoid(..))
218#if MIN_VERSION_base(4,9,0)
219import Data.Semigroup (Semigroup(..))
221import Data.String (IsString(..))
222import qualified Data.Text.Internal.Fusion as S
223import qualified Data.Text.Internal.Fusion.Common as S
224import Data.Text.Encoding (decodeUtf8', encodeUtf8)
225import Data.Text.Internal.Fusion (stream, reverseStream, unstream)
226import Data.Text.Internal.Private (span_)
227import Data.Text.Internal (Text(..), empty, firstf, mul, safe, text)
228import Data.Text.Show (singleton, unpack, unpackCString#)
229import qualified Prelude as P
230import Data.Text.Unsafe (Iter(..), iter, iter_, lengthWord16, reverseIter,
231 reverseIter_, unsafeHead, unsafeTail)
232import Data.Text.Internal.Unsafe.Char (unsafeChr)
233import qualified Data.Text.Internal.Functions as F
234import qualified Data.Text.Internal.Encoding.Utf16 as U16
235import Data.Text.Internal.Search (indices)
236#if defined(__HADDOCK__)
237import Data.ByteString (ByteString)
238import qualified Data.Text.Lazy as L
239import Data.Int (Int64)
241import GHC.Base (eqInt, neInt, gtInt, geInt, ltInt, leInt)
242#if __GLASGOW_HASKELL__ >= 708
243import qualified GHC.Exts as Exts
245#if MIN_VERSION_base(4,7,0)
246import Text.Printf (PrintfArg, formatArg, formatString)
251-- This package provides both strict and lazy 'Text' types. The
252-- strict type is provided by the "Data.Text" module, while the lazy
253-- type is provided by the "Data.Text.Lazy" module. Internally, the
254-- lazy @Text@ type consists of a list of strict chunks.
256-- The strict 'Text' type requires that an entire string fit into
257-- memory at once. The lazy 'Data.Text.Lazy.Text' type is capable of
258-- streaming strings that are larger than memory using a small memory
259-- footprint. In many cases, the overhead of chunked streaming makes
260-- the lazy 'Data.Text.Lazy.Text' type slower than its strict
261-- counterpart, but this is not always the case. Sometimes, the time
262-- complexity of a function in one module may be different from the
263-- other, due to their differing internal structures.
265-- Each module provides an almost identical API, with the main
266-- difference being that the strict module uses 'Int' values for
267-- lengths and counts, while the lazy module uses 'Data.Int.Int64'
272-- A 'Text' value is a sequence of Unicode scalar values, as defined
274-- <http://www.unicode.org/versions/Unicode5.2.0/ch03.pdf#page=35 §3.9, definition D76 of the Unicode 5.2 standard >.
275-- As such, a 'Text' cannot contain values in the range U+D800 to
276-- U+DFFF inclusive. Haskell implementations admit all Unicode code
278-- (<http://www.unicode.org/versions/Unicode5.2.0/ch03.pdf#page=13 §3.4, definition D10 >)
279-- as 'Char' values, including code points from this invalid range.
280-- This means that there are some 'Char' values that are not valid
281-- Unicode scalar values, and the functions in this module must handle
284-- Within this module, many functions construct a 'Text' from one or
285-- more 'Char' values. Those functions will substitute 'Char' values
286-- that are not valid Unicode scalar values with the replacement
287-- character \"�\" (U+FFFD). Functions that perform this
288-- inspection and replacement are documented with the phrase
289-- \"Performs replacement on invalid scalar values\".
291-- (One reason for this policy of replacement is that internally, a
292-- 'Text' value is represented as packed UTF-16 data. Values in the
293-- range U+D800 through U+DFFF are used by UTF-16 to denote surrogate
294-- code points, and so cannot be represented. The functions replace
295-- invalid scalar values, instead of dropping them, as a security
296-- measure. For details, see
297-- <http://unicode.org/reports/tr36/#Deletion_of_Noncharacters Unicode Technical Report 36, §3.5 >.)
301-- Most of the functions in this module are subject to /fusion/,
302-- meaning that a pipeline of such functions will usually allocate at
303-- most one 'Text' value.
305-- As an example, consider the following pipeline:
307-- > import Data.Text as T
308-- > import Data.Text.Encoding as E
309-- > import Data.ByteString (ByteString)
311-- > countChars :: ByteString -> Int
312-- > countChars = T.length . T.toUpper . E.decodeUtf8
314-- From the type signatures involved, this looks like it should
315-- allocate one 'Data.ByteString.ByteString' value, and two 'Text'
316-- values. However, when a module is compiled with optimisation
317-- enabled under GHC, the two intermediate 'Text' values will be
318-- optimised away, and the function will be compiled down to a single
319-- loop over the source 'Data.ByteString.ByteString'.
321-- Functions that can be fused by the compiler are documented with the
322-- phrase \"Subject to fusion\".
324instance Eq Text where
325 Text arrA offA lenA == Text arrB offB lenB
326 | lenA == lenB = A.equal arrA offA arrB offB lenA
330instance Ord Text where
331 compare = compareText
333instance Read Text where
334 readsPrec p str = [(pack x,y) | (x,y) <- readsPrec p str]
336#if MIN_VERSION_base(4,9,0)
337-- Semigroup orphan instances for older GHCs are provided by
338-- 'semigroups` package
340instance Semigroup Text where
344instance Monoid Text where
346#if MIN_VERSION_base(4,9,0)
347 mappend = (<>) -- future-proof definition
353instance IsString Text where
356#if __GLASGOW_HASKELL__ >= 708
357instance Exts.IsList Text where
358 type Item Text = Char
363#if defined(HAVE_DEEPSEQ)
364instance NFData Text where rnf !_ = ()
367instance Binary Text where
368 put t = put (encodeUtf8 t)
371 case decodeUtf8' bs of
372 P.Left exn -> P.fail (P.show exn)
373 P.Right a -> P.return a
375-- | This instance preserves data abstraction at the cost of inefficiency.
376-- We omit reflection services for the sake of data abstraction.
378-- This instance was created by copying the updated behavior of
379-- @"Data.Set".@'Data.Set.Set' and @"Data.Map".@'Data.Map.Map'. If you
380-- feel a mistake has been made, please feel free to submit
383-- The original discussion is archived here:
384-- <http://groups.google.com/group/haskell-cafe/browse_thread/thread/b5bbb1b28a7e525d/0639d46852575b93 could we get a Data instance for Data.Text.Text? >
386-- The followup discussion that changed the behavior of 'Data.Set.Set'
387-- and 'Data.Map.Map' is archived here:
388-- <http://markmail.org/message/trovdc6zkphyi3cr#query:+page:1+mid:a46der3iacwjcf6n+state:results Proposal: Allow gunfold for Data.Map, ... >
390instance Data Text where
391 gfoldl f z txt = z pack `f` (unpack txt)
392 toConstr _ = packConstr
393 gunfold k z c = case constrIndex c of
395 _ -> P.error "gunfold"
396 dataTypeOf _ = textDataType
398#if MIN_VERSION_base(4,7,0)
399-- | Only defined for @base-4.7.0.0@ and later
400instance PrintfArg Text where
401 formatArg txt = formatString $ unpack txt
405packConstr = mkConstr textDataType "pack" [] Prefix
407textDataType :: DataType
408textDataType = mkDataType "Data.Text.Text" [packConstr]
410-- | /O(n)/ Compare two 'Text' values lexicographically.
411compareText :: Text -> Text -> Ordering
412compareText ta@(Text _arrA _offA lenA) tb@(Text _arrB _offB lenB)
413 | lenA == 0 && lenB == 0 = EQ
417 | i >= lenA || j >= lenB = compare lenA lenB
420 | otherwise = go (i+di) (j+dj)
421 where Iter a di = iter ta i
422 Iter b dj = iter tb j
424-- -----------------------------------------------------------------------------
425-- * Conversion to/from 'Text'
427-- | /O(n)/ Convert a 'String' into a 'Text'. Subject to
428-- fusion. Performs replacement on invalid scalar values.
429pack :: String -> Text
430pack = unstream . S.map safe . S.streamList
431{-# INLINE [1] pack #-}
433-- -----------------------------------------------------------------------------
436-- | /O(n)/ Adds a character to the front of a 'Text'. This function
437-- is more costly than its 'List' counterpart because it requires
438-- copying a new array. Subject to fusion. Performs replacement on
439-- invalid scalar values.
440cons :: Char -> Text -> Text
441cons c t = unstream (S.cons (safe c) (stream t))
446-- | /O(n)/ Adds a character to the end of a 'Text'. This copies the
447-- entire array in the process, unless fused. Subject to fusion.
448-- Performs replacement on invalid scalar values.
449snoc :: Text -> Char -> Text
450snoc t c = unstream (S.snoc (stream t) (safe c))
453-- | /O(n)/ Appends one 'Text' to the other by copying both of them
454-- into a new 'Text'. Subject to fusion.
455append :: Text -> Text -> Text
456append a@(Text arr1 off1 len1) b@(Text arr2 off2 len2)
459 | len > 0 = Text (A.run x) 0 len
460 | otherwise = overflowError "append"
463 x :: ST s (A.MArray s)
466 A.copyI arr 0 arr1 off1 len1
467 A.copyI arr len1 arr2 off2 len
469{-# NOINLINE append #-}
472"TEXT append -> fused" [~1] forall t1 t2.
473 append t1 t2 = unstream (S.append (stream t1) (stream t2))
474"TEXT append -> unfused" [1] forall t1 t2.
475 unstream (S.append (stream t1) (stream t2)) = append t1 t2
478-- | /O(1)/ Returns the first character of a 'Text', which must be
479-- non-empty. Subject to fusion.
481head t = S.head (stream t)
484-- | /O(1)/ Returns the first character and rest of a 'Text', or
485-- 'Nothing' if empty. Subject to fusion.
486uncons :: Text -> Maybe (Char, Text)
487uncons t@(Text arr off len)
489 | otherwise = Just $ let !(Iter c d) = iter t 0
490 in (c, text arr (off+d) (len-d))
491{-# INLINE [1] uncons #-}
493-- | Lifted from Control.Arrow and specialized.
494second :: (b -> c) -> (a,b) -> (a,c)
495second f (a, b) = (a, f b)
497-- | /O(1)/ Returns the last character of a 'Text', which must be
498-- non-empty. Subject to fusion.
500last (Text arr off len)
501 | len <= 0 = emptyError "last"
502 | n < 0xDC00 || n > 0xDFFF = unsafeChr n
503 | otherwise = U16.chr2 n0 n
504 where n = A.unsafeIndex arr (off+len-1)
505 n0 = A.unsafeIndex arr (off+len-2)
506{-# INLINE [1] last #-}
509"TEXT last -> fused" [~1] forall t.
510 last t = S.last (stream t)
511"TEXT last -> unfused" [1] forall t.
512 S.last (stream t) = last t
515-- | /O(1)/ Returns all characters after the head of a 'Text', which
516-- must be non-empty. Subject to fusion.
518tail t@(Text arr off len)
519 | len <= 0 = emptyError "tail"
520 | otherwise = text arr (off+d) (len-d)
522{-# INLINE [1] tail #-}
525"TEXT tail -> fused" [~1] forall t.
526 tail t = unstream (S.tail (stream t))
527"TEXT tail -> unfused" [1] forall t.
528 unstream (S.tail (stream t)) = tail t
531-- | /O(1)/ Returns all but the last character of a 'Text', which must
532-- be non-empty. Subject to fusion.
534init (Text arr off len) | len <= 0 = emptyError "init"
535 | n >= 0xDC00 && n <= 0xDFFF = text arr off (len-2)
536 | otherwise = text arr off (len-1)
538 n = A.unsafeIndex arr (off+len-1)
539{-# INLINE [1] init #-}
542"TEXT init -> fused" [~1] forall t.
543 init t = unstream (S.init (stream t))
544"TEXT init -> unfused" [1] forall t.
545 unstream (S.init (stream t)) = init t
548-- | /O(1)/ Tests whether a 'Text' is empty or not. Subject to
551null (Text _arr _off len) =
556{-# INLINE [1] null #-}
559"TEXT null -> fused" [~1] forall t.
560 null t = S.null (stream t)
561"TEXT null -> unfused" [1] forall t.
562 S.null (stream t) = null t
565-- | /O(1)/ Tests whether a 'Text' contains exactly one character.
567isSingleton :: Text -> Bool
568isSingleton = S.isSingleton . stream
569{-# INLINE isSingleton #-}
571-- | /O(n)/ Returns the number of characters in a 'Text'.
574length t = S.length (stream t)
575{-# INLINE [0] length #-}
576-- length needs to be phased after the compareN/length rules otherwise
577-- it may inline before the rules have an opportunity to fire.
579-- | /O(n)/ Compare the count of characters in a 'Text' to a number.
582-- This function gives the same answer as comparing against the result
583-- of 'length', but can short circuit if the count of characters is
584-- greater than the number, and hence be more efficient.
585compareLength :: Text -> Int -> Ordering
586compareLength t n = S.compareLengthI (stream t) n
587{-# INLINE [1] compareLength #-}
590"TEXT compareN/length -> compareLength" [~1] forall t n.
591 compare (length t) n = compareLength t n
595"TEXT ==N/length -> compareLength/==EQ" [~1] forall t n.
596 eqInt (length t) n = compareLength t n == EQ
600"TEXT /=N/length -> compareLength//=EQ" [~1] forall t n.
601 neInt (length t) n = compareLength t n /= EQ
605"TEXT <N/length -> compareLength/==LT" [~1] forall t n.
606 ltInt (length t) n = compareLength t n == LT
610"TEXT <=N/length -> compareLength//=GT" [~1] forall t n.
611 leInt (length t) n = compareLength t n /= GT
615"TEXT >N/length -> compareLength/==GT" [~1] forall t n.
616 gtInt (length t) n = compareLength t n == GT
620"TEXT >=N/length -> compareLength//=LT" [~1] forall t n.
621 geInt (length t) n = compareLength t n /= LT
624-- -----------------------------------------------------------------------------
626-- | /O(n)/ 'map' @f@ @t@ is the 'Text' obtained by applying @f@ to
627-- each element of @t@. Subject to fusion. Performs replacement on
628-- invalid scalar values.
629map :: (Char -> Char) -> Text -> Text
630map f t = unstream (S.map (safe . f) (stream t))
631{-# INLINE [1] map #-}
633-- | /O(n)/ The 'intercalate' function takes a 'Text' and a list of
634-- 'Text's and concatenates the list after interspersing the first
635-- argument between each element of the list.
636intercalate :: Text -> [Text] -> Text
637intercalate t = concat . (F.intersperse t)
638{-# INLINE intercalate #-}
640-- | /O(n)/ The 'intersperse' function takes a character and places it
641-- between the characters of a 'Text'. Subject to fusion. Performs
642-- replacement on invalid scalar values.
643intersperse :: Char -> Text -> Text
644intersperse c t = unstream (S.intersperse (safe c) (stream t))
645{-# INLINE intersperse #-}
647-- | /O(n)/ Reverse the characters of a string. Subject to fusion.
648reverse :: Text -> Text
649reverse t = S.reverse (stream t)
650{-# INLINE reverse #-}
652-- | /O(m+n)/ Replace every non-overlapping occurrence of @needle@ in
653-- @haystack@ with @replacement@.
655-- This function behaves as though it was defined as follows:
658-- replace needle replacement haystack =
659-- 'intercalate' replacement ('splitOn' needle haystack)
662-- As this suggests, each occurrence is replaced exactly once. So if
663-- @needle@ occurs in @replacement@, that occurrence will /not/ itself
664-- be replaced recursively:
666-- > replace "oo" "foo" "oo" == "foo"
668-- In cases where several instances of @needle@ overlap, only the
669-- first one will be replaced:
671-- > replace "ofo" "bar" "ofofo" == "barfo"
673-- In (unlikely) bad cases, this function's time complexity degrades
676 -- ^ @needle@ to search for. If this string is empty, an
679 -- ^ @replacement@ to replace @needle@ with.
681 -- ^ @haystack@ in which to search.
683replace needle@(Text _ _ neeLen)
684 (Text repArr repOff repLen)
685 haystack@(Text hayArr hayOff hayLen)
686 | neeLen == 0 = emptyError "replace"
687 | L.null ixs = haystack
688 | len > 0 = Text (A.run x) 0 len
691 ixs = indices needle haystack
692 len = hayLen - (neeLen - repLen) `mul` L.length ixs
693 x :: ST s (A.MArray s)
696 let loop (i:is) o d = do
699 A.copyI marr d hayArr (hayOff+o) d0
700 A.copyI marr d0 repArr repOff d1
701 loop is (i + neeLen) d1
702 loop [] o d = A.copyI marr d hayArr (hayOff+o) len
706-- ----------------------------------------------------------------------------
707-- ** Case conversions (folds)
711-- When case converting 'Text' values, do not use combinators like
712-- @map toUpper@ to case convert each character of a string
713-- individually, as this gives incorrect results according to the
714-- rules of some writing systems. The whole-string case conversion
715-- functions from this module, such as @toUpper@, obey the correct
716-- case conversion rules. As a result, these functions may map one
717-- input character to two or three output characters. For examples,
718-- see the documentation of each function.
720-- /Note/: In some languages, case conversion is a locale- and
721-- context-dependent operation. The case conversion functions in this
722-- module are /not/ locale sensitive. Programs that require locale
723-- sensitivity should use appropriate versions of the
724-- <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 >.
726-- | /O(n)/ Convert a string to folded case. Subject to fusion.
728-- This function is mainly useful for performing caseless (also known
729-- as case insensitive) string comparisons.
731-- A string @x@ is a caseless match for a string @y@ if and only if:
733-- @toCaseFold x == toCaseFold y@
735-- The result string may be longer than the input string, and may
736-- differ from applying 'toLower' to the input string. For instance,
737-- the Armenian small ligature \"ﬓ\" (men now, U+FB13) is case
738-- folded to the sequence \"մ\" (men, U+0574) followed by
739-- \"ն\" (now, U+0576), while the Greek \"µ\" (micro sign,
740-- U+00B5) is case folded to \"μ\" (small letter mu, U+03BC)
742toCaseFold :: Text -> Text
743toCaseFold t = unstream (S.toCaseFold (stream t))
744{-# INLINE toCaseFold #-}
746-- | /O(n)/ Convert a string to lower case, using simple case
747-- conversion. Subject to fusion.
749-- The result string may be longer than the input string. For
750-- instance, \"İ\" (Latin capital letter I with dot above,
751-- U+0130) maps to the sequence \"i\" (Latin small letter i, U+0069)
752-- followed by \" ̇\" (combining dot above, U+0307).
753toLower :: Text -> Text
754toLower t = unstream (S.toLower (stream t))
755{-# INLINE toLower #-}
757-- | /O(n)/ Convert a string to upper case, using simple case
758-- conversion. Subject to fusion.
760-- The result string may be longer than the input string. For
761-- instance, the German \"ß\" (eszett, U+00DF) maps to the
762-- two-letter sequence \"SS\".
763toUpper :: Text -> Text
764toUpper t = unstream (S.toUpper (stream t))
765{-# INLINE toUpper #-}
767-- | /O(n)/ Convert a string to title case, using simple case
768-- conversion. Subject to fusion.
770-- The first letter of the input is converted to title case, as is
771-- every subsequent letter that immediately follows a non-letter.
772-- Every letter that immediately follows another letter is converted
775-- The result string may be longer than the input string. For example,
776-- the Latin small ligature fl (U+FB02) is converted to the
777-- sequence Latin capital letter F (U+0046) followed by Latin small
780-- /Note/: this function does not take language or culture specific
781-- rules into account. For instance, in English, different style
782-- guides disagree on whether the book name \"The Hill of the Red
783-- Fox\" is correctly title cased—but this function will
784-- capitalize /every/ word.
785toTitle :: Text -> Text
786toTitle t = unstream (S.toTitle (stream t))
787{-# INLINE toTitle #-}
789-- | /O(n)/ Left-justify a string to the given length, using the
790-- specified fill character on the right. Subject to fusion.
791-- Performs replacement on invalid scalar values.
795-- > justifyLeft 7 'x' "foo" == "fooxxxx"
796-- > justifyLeft 3 'x' "foobar" == "foobar"
797justifyLeft :: Int -> Char -> Text -> Text
800 | otherwise = t `append` replicateChar (k-len) c
802{-# INLINE [1] justifyLeft #-}
805"TEXT justifyLeft -> fused" [~1] forall k c t.
806 justifyLeft k c t = unstream (S.justifyLeftI k c (stream t))
807"TEXT justifyLeft -> unfused" [1] forall k c t.
808 unstream (S.justifyLeftI k c (stream t)) = justifyLeft k c t
811-- | /O(n)/ Right-justify a string to the given length, using the
812-- specified fill character on the left. Performs replacement on
813-- invalid scalar values.
817-- > justifyRight 7 'x' "bar" == "xxxxbar"
818-- > justifyRight 3 'x' "foobar" == "foobar"
819justifyRight :: Int -> Char -> Text -> Text
822 | otherwise = replicateChar (k-len) c `append` t
824{-# INLINE justifyRight #-}
826-- | /O(n)/ Center a string to the given length, using the specified
827-- fill character on either side. Performs replacement on invalid
832-- > center 8 'x' "HS" = "xxxHSxxx"
833center :: Int -> Char -> Text -> Text
836 | otherwise = replicateChar l c `append` t `append` replicateChar r c
843-- | /O(n)/ The 'transpose' function transposes the rows and columns
844-- of its 'Text' argument. Note that this function uses 'pack',
845-- 'unpack', and the list version of transpose, and is thus not very
847transpose :: [Text] -> [Text]
848transpose ts = P.map pack (L.transpose (P.map unpack ts))
850-- -----------------------------------------------------------------------------
851-- * Reducing 'Text's (folds)
853-- | /O(n)/ 'foldl', applied to a binary operator, a starting value
854-- (typically the left-identity of the operator), and a 'Text',
855-- reduces the 'Text' using the binary operator, from left to right.
857foldl :: (a -> Char -> a) -> a -> Text -> a
858foldl f z t = S.foldl f z (stream t)
861-- | /O(n)/ A strict version of 'foldl'. Subject to fusion.
862foldl' :: (a -> Char -> a) -> a -> Text -> a
863foldl' f z t = S.foldl' f z (stream t)
866-- | /O(n)/ A variant of 'foldl' that has no starting value argument,
867-- and thus must be applied to a non-empty 'Text'. Subject to fusion.
868foldl1 :: (Char -> Char -> Char) -> Text -> Char
869foldl1 f t = S.foldl1 f (stream t)
872-- | /O(n)/ A strict version of 'foldl1'. Subject to fusion.
873foldl1' :: (Char -> Char -> Char) -> Text -> Char
874foldl1' f t = S.foldl1' f (stream t)
875{-# INLINE foldl1' #-}
877-- | /O(n)/ 'foldr', applied to a binary operator, a starting value
878-- (typically the right-identity of the operator), and a 'Text',
879-- reduces the 'Text' using the binary operator, from right to left.
881foldr :: (Char -> a -> a) -> a -> Text -> a
882foldr f z t = S.foldr f z (stream t)
885-- | /O(n)/ A variant of 'foldr' that has no starting value argument,
886-- and thus must be applied to a non-empty 'Text'. Subject to
888foldr1 :: (Char -> Char -> Char) -> Text -> Char
889foldr1 f t = S.foldr1 f (stream t)
892-- -----------------------------------------------------------------------------
895-- | /O(n)/ Concatenate a list of 'Text's.
896concat :: [Text] -> Text
897concat ts = case ts' of
900 _ -> Text (A.run go) 0 len
902 ts' = L.filter (not . null) ts
903 len = sumP "concat" $ L.map lengthWord16 ts'
904 go :: ST s (A.MArray s)
907 let step i (Text a o l) =
908 let !j = i + l in A.copyI arr i a o j >> return j
909 foldM step 0 ts' >> return arr
911-- | /O(n)/ Map a function over a 'Text' that results in a 'Text', and
912-- concatenate the results.
913concatMap :: (Char -> Text) -> Text -> Text
914concatMap f = concat . foldr ((:) . f) []
915{-# INLINE concatMap #-}
917-- | /O(n)/ 'any' @p@ @t@ determines whether any character in the
918-- 'Text' @t@ satisfies the predicate @p@. Subject to fusion.
919any :: (Char -> Bool) -> Text -> Bool
920any p t = S.any p (stream t)
923-- | /O(n)/ 'all' @p@ @t@ determines whether all characters in the
924-- 'Text' @t@ satisfy the predicate @p@. Subject to fusion.
925all :: (Char -> Bool) -> Text -> Bool
926all p t = S.all p (stream t)
929-- | /O(n)/ 'maximum' returns the maximum value from a 'Text', which
930-- must be non-empty. Subject to fusion.
931maximum :: Text -> Char
932maximum t = S.maximum (stream t)
933{-# INLINE maximum #-}
935-- | /O(n)/ 'minimum' returns the minimum value from a 'Text', which
936-- must be non-empty. Subject to fusion.
937minimum :: Text -> Char
938minimum t = S.minimum (stream t)
939{-# INLINE minimum #-}
941-- -----------------------------------------------------------------------------
944-- | /O(n)/ 'scanl' is similar to 'foldl', but returns a list of
945-- successive reduced values from the left. Subject to fusion.
946-- Performs replacement on invalid scalar values.
948-- > scanl f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...]
952-- > last (scanl f z xs) == foldl f z xs.
953scanl :: (Char -> Char -> Char) -> Char -> Text -> Text
954scanl f z t = unstream (S.scanl g z (stream t))
955 where g a b = safe (f a b)
958-- | /O(n)/ 'scanl1' is a variant of 'scanl' that has no starting
959-- value argument. Subject to fusion. Performs replacement on
960-- invalid scalar values.
962-- > scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]
963scanl1 :: (Char -> Char -> Char) -> Text -> Text
964scanl1 f t | null t = empty
965 | otherwise = scanl f (unsafeHead t) (unsafeTail t)
968-- | /O(n)/ 'scanr' is the right-to-left dual of 'scanl'. Performs
969-- replacement on invalid scalar values.
971-- > scanr f v == reverse . scanl (flip f) v . reverse
972scanr :: (Char -> Char -> Char) -> Char -> Text -> Text
973scanr f z = S.reverse . S.reverseScanr g z . reverseStream
974 where g a b = safe (f a b)
977-- | /O(n)/ 'scanr1' is a variant of 'scanr' that has no starting
978-- value argument. Subject to fusion. Performs replacement on
979-- invalid scalar values.
980scanr1 :: (Char -> Char -> Char) -> Text -> Text
981scanr1 f t | null t = empty
982 | otherwise = scanr f (last t) (init t)
985-- | /O(n)/ Like a combination of 'map' and 'foldl''. Applies a
986-- function to each element of a 'Text', passing an accumulating
987-- parameter from left to right, and returns a final 'Text'. Performs
988-- replacement on invalid scalar values.
989mapAccumL :: (a -> Char -> (a,Char)) -> a -> Text -> (a, Text)
990mapAccumL f z0 = S.mapAccumL g z0 . stream
991 where g a b = second safe (f a b)
992{-# INLINE mapAccumL #-}
994-- | The 'mapAccumR' function behaves like a combination of 'map' and
995-- a strict 'foldr'; it applies a function to each element of a
996-- 'Text', passing an accumulating parameter from right to left, and
997-- returning a final value of this accumulator together with the new
999-- Performs replacement on invalid scalar values.
1000mapAccumR :: (a -> Char -> (a,Char)) -> a -> Text -> (a, Text)
1001mapAccumR f z0 = second reverse . S.mapAccumL g z0 . reverseStream
1002 where g a b = second safe (f a b)
1003{-# INLINE mapAccumR #-}
1005-- -----------------------------------------------------------------------------
1006-- ** Generating and unfolding 'Text's
1008-- | /O(n*m)/ 'replicate' @n@ @t@ is a 'Text' consisting of the input
1009-- @t@ repeated @n@ times.
1010replicate :: Int -> Text -> Text
1011replicate n t@(Text a o l)
1012 | n <= 0 || l <= 0 = empty
1014 | isSingleton t = replicateChar n (unsafeHead t)
1015 | otherwise = Text (A.run x) 0 len
1018 x :: ST s (A.MArray s)
1021 let loop !d !i | i >= n = return arr
1022 | otherwise = let m = d + l
1023 in A.copyI arr d a o m >> loop m (i+1)
1025{-# INLINE [1] replicate #-}
1028"TEXT replicate/singleton -> replicateChar" [~1] forall n c.
1029 replicate n (singleton c) = replicateChar n c
1032-- | /O(n)/ 'replicateChar' @n@ @c@ is a 'Text' of length @n@ with @c@ the
1033-- value of every element. Subject to fusion.
1034replicateChar :: Int -> Char -> Text
1035replicateChar n c = unstream (S.replicateCharI n (safe c))
1036{-# INLINE replicateChar #-}
1038-- | /O(n)/, where @n@ is the length of the result. The 'unfoldr'
1039-- function is analogous to the List 'L.unfoldr'. 'unfoldr' builds a
1040-- 'Text' from a seed value. The function takes the element and
1041-- returns 'Nothing' if it is done producing the 'Text', otherwise
1042-- 'Just' @(a,b)@. In this case, @a@ is the next 'Char' in the
1043-- string, and @b@ is the seed value for further production. Subject
1044-- to fusion. Performs replacement on invalid scalar values.
1045unfoldr :: (a -> Maybe (Char,a)) -> a -> Text
1046unfoldr f s = unstream (S.unfoldr (firstf safe . f) s)
1047{-# INLINE unfoldr #-}
1049-- | /O(n)/ Like 'unfoldr', 'unfoldrN' builds a 'Text' from a seed
1050-- value. However, the length of the result should be limited by the
1051-- first argument to 'unfoldrN'. This function is more efficient than
1052-- 'unfoldr' when the maximum length of the result is known and
1053-- correct, otherwise its performance is similar to 'unfoldr'. Subject
1054-- to fusion. Performs replacement on invalid scalar values.
1055unfoldrN :: Int -> (a -> Maybe (Char,a)) -> a -> Text
1056unfoldrN n f s = unstream (S.unfoldrN n (firstf safe . f) s)
1057{-# INLINE unfoldrN #-}
1059-- -----------------------------------------------------------------------------
1062-- | /O(n)/ 'take' @n@, applied to a 'Text', returns the prefix of the
1063-- 'Text' of length @n@, or the 'Text' itself if @n@ is greater than
1064-- the length of the Text. Subject to fusion.
1065take :: Int -> Text -> Text
1066take n t@(Text arr off len)
1069 | otherwise = text arr off (iterN n t)
1070{-# INLINE [1] take #-}
1072iterN :: Int -> Text -> Int
1073iterN n t@(Text _arr _off len) = loop 0 0
1075 | i >= len || cnt >= n = i
1076 | otherwise = loop (i+d) (cnt+1)
1080"TEXT take -> fused" [~1] forall n t.
1081 take n t = unstream (S.take n (stream t))
1082"TEXT take -> unfused" [1] forall n t.
1083 unstream (S.take n (stream t)) = take n t
1086-- | /O(n)/ 'takeEnd' @n@ @t@ returns the suffix remaining after
1087-- taking @n@ characters from the end of @t@.
1091-- > takeEnd 3 "foobar" == "bar"
1092takeEnd :: Int -> Text -> Text
1093takeEnd n t@(Text arr off len)
1096 | otherwise = text arr (off+i) (len-i)
1097 where i = iterNEnd n t
1099iterNEnd :: Int -> Text -> Int
1100iterNEnd n t@(Text _arr _off len) = loop (len-1) n
1104 | otherwise = loop (i+d) (m-1)
1105 where d = reverseIter_ t i
1107-- | /O(n)/ 'drop' @n@, applied to a 'Text', returns the suffix of the
1108-- 'Text' after the first @n@ characters, or the empty 'Text' if @n@
1109-- is greater than the length of the 'Text'. Subject to fusion.
1110drop :: Int -> Text -> Text
1111drop n t@(Text arr off len)
1114 | otherwise = text arr (off+i) (len-i)
1116{-# INLINE [1] drop #-}
1119"TEXT drop -> fused" [~1] forall n t.
1120 drop n t = unstream (S.drop n (stream t))
1121"TEXT drop -> unfused" [1] forall n t.
1122 unstream (S.drop n (stream t)) = drop n t
1125-- | /O(n)/ 'dropEnd' @n@ @t@ returns the prefix remaining after
1126-- dropping @n@ characters from the end of @t@.
1130-- > dropEnd 3 "foobar" == "foo"
1131dropEnd :: Int -> Text -> Text
1132dropEnd n t@(Text arr off len)
1135 | otherwise = text arr off (iterNEnd n t)
1137-- | /O(n)/ 'takeWhile', applied to a predicate @p@ and a 'Text',
1138-- returns the longest prefix (possibly empty) of elements that
1139-- satisfy @p@. Subject to fusion.
1140takeWhile :: (Char -> Bool) -> Text -> Text
1141takeWhile p t@(Text arr off len) = loop 0
1142 where loop !i | i >= len = t
1144 | otherwise = text arr off i
1145 where Iter c d = iter t i
1146{-# INLINE [1] takeWhile #-}
1149"TEXT takeWhile -> fused" [~1] forall p t.
1150 takeWhile p t = unstream (S.takeWhile p (stream t))
1151"TEXT takeWhile -> unfused" [1] forall p t.
1152 unstream (S.takeWhile p (stream t)) = takeWhile p t
1155-- | /O(n)/ 'takeWhileEnd', applied to a predicate @p@ and a 'Text',
1156-- returns the longest suffix (possibly empty) of elements that
1157-- satisfy @p@. Subject to fusion.
1160-- > takeWhileEnd (=='o') "foo" == "oo"
1161takeWhileEnd :: (Char -> Bool) -> Text -> Text
1162takeWhileEnd p t@(Text arr off len) = loop (len-1) len
1163 where loop !i !l | l <= 0 = t
1164 | p c = loop (i+d) (l+d)
1165 | otherwise = text arr (off+l) (len-l)
1166 where (c,d) = reverseIter t i
1167{-# INLINE [1] takeWhileEnd #-}
1170"TEXT takeWhileEnd -> fused" [~1] forall p t.
1171 takeWhileEnd p t = S.reverse (S.takeWhile p (S.reverseStream t))
1172"TEXT takeWhileEnd -> unfused" [1] forall p t.
1173 S.reverse (S.takeWhile p (S.reverseStream t)) = takeWhileEnd p t
1176-- | /O(n)/ 'dropWhile' @p@ @t@ returns the suffix remaining after
1177-- 'takeWhile' @p@ @t@. Subject to fusion.
1178dropWhile :: (Char -> Bool) -> Text -> Text
1179dropWhile p t@(Text arr off len) = loop 0 0
1180 where loop !i !l | l >= len = empty
1181 | p c = loop (i+d) (l+d)
1182 | otherwise = Text arr (off+i) (len-l)
1183 where Iter c d = iter t i
1184{-# INLINE [1] dropWhile #-}
1187"TEXT dropWhile -> fused" [~1] forall p t.
1188 dropWhile p t = unstream (S.dropWhile p (stream t))
1189"TEXT dropWhile -> unfused" [1] forall p t.
1190 unstream (S.dropWhile p (stream t)) = dropWhile p t
1193-- | /O(n)/ 'dropWhileEnd' @p@ @t@ returns the prefix remaining after
1194-- dropping characters that satisfy the predicate @p@ from the end of
1195-- @t@. Subject to fusion.
1199-- > dropWhileEnd (=='.') "foo..." == "foo"
1200dropWhileEnd :: (Char -> Bool) -> Text -> Text
1201dropWhileEnd p t@(Text arr off len) = loop (len-1) len
1202 where loop !i !l | l <= 0 = empty
1203 | p c = loop (i+d) (l+d)
1204 | otherwise = Text arr off l
1205 where (c,d) = reverseIter t i
1206{-# INLINE [1] dropWhileEnd #-}
1209"TEXT dropWhileEnd -> fused" [~1] forall p t.
1210 dropWhileEnd p t = S.reverse (S.dropWhile p (S.reverseStream t))
1211"TEXT dropWhileEnd -> unfused" [1] forall p t.
1212 S.reverse (S.dropWhile p (S.reverseStream t)) = dropWhileEnd p t
1215-- | /O(n)/ 'dropAround' @p@ @t@ returns the substring remaining after
1216-- dropping characters that satisfy the predicate @p@ from both the
1217-- beginning and end of @t@. Subject to fusion.
1218dropAround :: (Char -> Bool) -> Text -> Text
1219dropAround p = dropWhile p . dropWhileEnd p
1220{-# INLINE [1] dropAround #-}
1222-- | /O(n)/ Remove leading white space from a string. Equivalent to:
1224-- > dropWhile isSpace
1225stripStart :: Text -> Text
1226stripStart = dropWhile isSpace
1227{-# INLINE [1] stripStart #-}
1229-- | /O(n)/ Remove trailing white space from a string. Equivalent to:
1231-- > dropWhileEnd isSpace
1232stripEnd :: Text -> Text
1233stripEnd = dropWhileEnd isSpace
1234{-# INLINE [1] stripEnd #-}
1236-- | /O(n)/ Remove leading and trailing white space from a string.
1239-- > dropAround isSpace
1240strip :: Text -> Text
1241strip = dropAround isSpace
1242{-# INLINE [1] strip #-}
1244-- | /O(n)/ 'splitAt' @n t@ returns a pair whose first element is a
1245-- prefix of @t@ of length @n@, and whose second is the remainder of
1246-- the string. It is equivalent to @('take' n t, 'drop' n t)@.
1247splitAt :: Int -> Text -> (Text, Text)
1248splitAt n t@(Text arr off len)
1249 | n <= 0 = (empty, t)
1250 | n >= len = (t, empty)
1251 | otherwise = let k = iterN n t
1252 in (text arr off k, text arr (off+k) (len-k))
1254-- | /O(n)/ 'span', applied to a predicate @p@ and text @t@, returns
1255-- a pair whose first element is the longest prefix (possibly empty)
1256-- of @t@ of elements that satisfy @p@, and whose second is the
1257-- remainder of the list.
1258span :: (Char -> Bool) -> Text -> (Text, Text)
1259span p t = case span_ p t of
1260 (# hd,tl #) -> (hd,tl)
1263-- | /O(n)/ 'break' is like 'span', but the prefix returned is
1264-- over elements that fail the predicate @p@.
1265break :: (Char -> Bool) -> Text -> (Text, Text)
1266break p = span (not . p)
1269-- | /O(n)/ Group characters in a string according to a predicate.
1270groupBy :: (Char -> Char -> Bool) -> Text -> [Text]
1273 loop t@(Text arr off len)
1275 | otherwise = text arr off n : loop (text arr (off+n) (len-n))
1276 where Iter c d = iter t 0
1277 n = d + findAIndexOrEnd (not . p c) (Text arr (off+d) (len-d))
1279-- | Returns the /array/ index (in units of 'Word16') at which a
1280-- character may be found. This is /not/ the same as the logical
1281-- index returned by e.g. 'findIndex'.
1282findAIndexOrEnd :: (Char -> Bool) -> Text -> Int
1283findAIndexOrEnd q t@(Text _arr _off len) = go 0
1284 where go !i | i >= len || q c = i
1285 | otherwise = go (i+d)
1286 where Iter c d = iter t i
1288-- | /O(n)/ Group characters in a string by equality.
1289group :: Text -> [Text]
1292-- | /O(n)/ Return all initial segments of the given 'Text', shortest
1294inits :: Text -> [Text]
1295inits t@(Text arr off len) = loop 0
1296 where loop i | i >= len = [t]
1297 | otherwise = Text arr off i : loop (i + iter_ t i)
1299-- | /O(n)/ Return all final segments of the given 'Text', longest
1301tails :: Text -> [Text]
1302tails t | null t = [empty]
1303 | otherwise = t : tails (unsafeTail t)
1307-- Splitting functions in this library do not perform character-wise
1308-- copies to create substrings; they just construct new 'Text's that
1309-- are slices of the original.
1311-- | /O(m+n)/ Break a 'Text' into pieces separated by the first 'Text'
1312-- argument (which cannot be empty), consuming the delimiter. An empty
1313-- delimiter is invalid, and will cause an error to be raised.
1317-- > splitOn "\r\n" "a\r\nb\r\nd\r\ne" == ["a","b","d","e"]
1318-- > splitOn "aaa" "aaaXaaaXaaaXaaa" == ["","X","X","X",""]
1319-- > splitOn "x" "x" == ["",""]
1323-- > intercalate s . splitOn s == id
1324-- > splitOn (singleton c) == split (==c)
1326-- (Note: the string @s@ to split on above cannot be empty.)
1328-- In (unlikely) bad cases, this function's time complexity degrades
1331 -- ^ String to split on. If this string is empty, an error
1336splitOn pat@(Text _ _ l) src@(Text arr off len)
1337 | l <= 0 = emptyError "splitOn"
1338 | isSingleton pat = split (== unsafeHead pat) src
1339 | otherwise = go 0 (indices pat src)
1341 go !s (x:xs) = text arr (s+off) (x-s) : go (x+l) xs
1342 go s _ = [text arr (s+off) (len-s)]
1343{-# INLINE [1] splitOn #-}
1346"TEXT splitOn/singleton -> split/==" [~1] forall c t.
1347 splitOn (singleton c) t = split (==c) t
1350-- | /O(n)/ Splits a 'Text' into components delimited by separators,
1351-- where the predicate returns True for a separator element. The
1352-- resulting components do not contain the separators. Two adjacent
1353-- separators result in an empty component in the output. eg.
1355-- > split (=='a') "aabbaca" == ["","","bb","c",""]
1356-- > split (=='a') "" == [""]
1357split :: (Char -> Bool) -> Text -> [Text]
1358split _ t@(Text _off _arr 0) = [t]
1360 where loop s | null s' = [l]
1361 | otherwise = l : loop (unsafeTail s')
1362 where (# l, s' #) = span_ (not . p) s
1365-- | /O(n)/ Splits a 'Text' into components of length @k@. The last
1366-- element may be shorter than the other chunks, depending on the
1367-- length of the input. Examples:
1369-- > chunksOf 3 "foobarbaz" == ["foo","bar","baz"]
1370-- > chunksOf 4 "haskell.org" == ["hask","ell.","org"]
1371chunksOf :: Int -> Text -> [Text]
1374 go t = case splitAt k t of
1375 (a,b) | null a -> []
1376 | otherwise -> a : go b
1377{-# INLINE chunksOf #-}
1379-- ----------------------------------------------------------------------------
1382-------------------------------------------------------------------------------
1383-- ** Searching with a predicate
1385-- | /O(n)/ The 'find' function takes a predicate and a 'Text', and
1386-- returns the first element matching the predicate, or 'Nothing' if
1387-- there is no such element.
1388find :: (Char -> Bool) -> Text -> Maybe Char
1389find p t = S.findBy p (stream t)
1392-- | /O(n)/ The 'partition' function takes a predicate and a 'Text',
1393-- and returns the pair of 'Text's with elements which do and do not
1394-- satisfy the predicate, respectively; i.e.
1396-- > partition p t == (filter p t, filter (not . p) t)
1397partition :: (Char -> Bool) -> Text -> (Text, Text)
1398partition p t = (filter p t, filter (not . p) t)
1399{-# INLINE partition #-}
1401-- | /O(n)/ 'filter', applied to a predicate and a 'Text',
1402-- returns a 'Text' containing those characters that satisfy the
1404filter :: (Char -> Bool) -> Text -> Text
1405filter p t = unstream (S.filter p (stream t))
1406{-# INLINE filter #-}
1408-- | /O(n+m)/ Find the first instance of @needle@ (which must be
1409-- non-'null') in @haystack@. The first element of the returned tuple
1410-- is the prefix of @haystack@ before @needle@ is matched. The second
1411-- is the remainder of @haystack@, starting with the match.
1415-- > breakOn "::" "a::b::c" ==> ("a", "::b::c")
1416-- > breakOn "/" "foobar" ==> ("foobar", "")
1420-- > append prefix match == haystack
1421-- > where (prefix, match) = breakOn needle haystack
1423-- If you need to break a string by a substring repeatedly (e.g. you
1424-- want to break on every instance of a substring), use 'breakOnAll'
1425-- instead, as it has lower startup overhead.
1427-- In (unlikely) bad cases, this function's time complexity degrades
1429breakOn :: Text -> Text -> (Text, Text)
1430breakOn pat src@(Text arr off len)
1431 | null pat = emptyError "breakOn"
1432 | otherwise = case indices pat src of
1434 (x:_) -> (text arr off x, text arr (off+x) (len-x))
1435{-# INLINE breakOn #-}
1437-- | /O(n+m)/ Similar to 'breakOn', but searches from the end of the
1440-- The first element of the returned tuple is the prefix of @haystack@
1441-- up to and including the last match of @needle@. The second is the
1442-- remainder of @haystack@, following the match.
1444-- > breakOnEnd "::" "a::b::c" ==> ("a::b::", "c")
1445breakOnEnd :: Text -> Text -> (Text, Text)
1446breakOnEnd pat src = (reverse b, reverse a)
1447 where (a,b) = breakOn (reverse pat) (reverse src)
1448{-# INLINE breakOnEnd #-}
1450-- | /O(n+m)/ Find all non-overlapping instances of @needle@ in
1451-- @haystack@. Each element of the returned list consists of a pair:
1453-- * The entire string prior to the /k/th match (i.e. the prefix)
1455-- * The /k/th match, followed by the remainder of the string
1459-- > breakOnAll "::" ""
1461-- > breakOnAll "/" "a/b/c/"
1462-- > ==> [("a", "/b/c/"), ("a/b", "/c/"), ("a/b/c", "/")]
1464-- In (unlikely) bad cases, this function's time complexity degrades
1467-- The @needle@ parameter may not be empty.
1468breakOnAll :: Text -- ^ @needle@ to search for
1469 -> Text -- ^ @haystack@ in which to search
1471breakOnAll pat src@(Text arr off slen)
1472 | null pat = emptyError "breakOnAll"
1473 | otherwise = L.map step (indices pat src)
1475 step x = (chunk 0 x, chunk x (slen-x))
1476 chunk !n !l = text arr (n+off) l
1477{-# INLINE breakOnAll #-}
1479-------------------------------------------------------------------------------
1480-- ** Indexing 'Text's
1484-- If you think of a 'Text' value as an array of 'Char' values (which
1485-- it is not), you run the risk of writing inefficient code.
1487-- An idiom that is common in some languages is to find the numeric
1488-- offset of a character or substring, then use that number to split
1489-- or trim the searched string. With a 'Text' value, this approach
1490-- would require two /O(n)/ operations: one to perform the search, and
1491-- one to operate from wherever the search ended.
1493-- For example, suppose you have a string that you want to split on
1494-- the substring @\"::\"@, such as @\"foo::bar::quux\"@. Instead of
1495-- searching for the index of @\"::\"@ and taking the substrings
1496-- before and after that index, you would instead use @breakOnAll \"::\"@.
1498-- | /O(n)/ 'Text' index (subscript) operator, starting from 0.
1499index :: Text -> Int -> Char
1500index t n = S.index (stream t) n
1503-- | /O(n)/ The 'findIndex' function takes a predicate and a 'Text'
1504-- and returns the index of the first element in the 'Text' satisfying
1505-- the predicate. Subject to fusion.
1506findIndex :: (Char -> Bool) -> Text -> Maybe Int
1507findIndex p t = S.findIndex p (stream t)
1508{-# INLINE findIndex #-}
1510-- | /O(n+m)/ The 'count' function returns the number of times the
1511-- query string appears in the given 'Text'. An empty query string is
1512-- invalid, and will cause an error to be raised.
1514-- In (unlikely) bad cases, this function's time complexity degrades
1516count :: Text -> Text -> Int
1518 | null pat = emptyError "count"
1519 | isSingleton pat = countChar (unsafeHead pat) src
1520 | otherwise = L.length (indices pat src)
1521{-# INLINE [1] count #-}
1524"TEXT count/singleton -> countChar" [~1] forall c t.
1525 count (singleton c) t = countChar c t
1528-- | /O(n)/ The 'countChar' function returns the number of times the
1529-- query element appears in the given 'Text'. Subject to fusion.
1530countChar :: Char -> Text -> Int
1531countChar c t = S.countChar c (stream t)
1532{-# INLINE countChar #-}
1534-------------------------------------------------------------------------------
1537-- | /O(n)/ 'zip' takes two 'Text's and returns a list of
1538-- corresponding pairs of bytes. If one input 'Text' is short,
1539-- excess elements of the longer 'Text' are discarded. This is
1540-- equivalent to a pair of 'unpack' operations.
1541zip :: Text -> Text -> [(Char,Char)]
1542zip a b = S.unstreamList $ S.zipWith (,) (stream a) (stream b)
1545-- | /O(n)/ 'zipWith' generalises 'zip' by zipping with the function
1546-- given as the first argument, instead of a tupling function.
1547-- Performs replacement on invalid scalar values.
1548zipWith :: (Char -> Char -> Char) -> Text -> Text -> Text
1549zipWith f t1 t2 = unstream (S.zipWith g (stream t1) (stream t2))
1550 where g a b = safe (f a b)
1551{-# INLINE zipWith #-}
1553-- | /O(n)/ Breaks a 'Text' up into a list of words, delimited by 'Char's
1554-- representing white space.
1555words :: Text -> [Text]
1556words t@(Text arr off len) = loop 0 0
1559 | n >= len = if start == n
1561 else [Text arr (start+off) (n-start)]
1564 then loop (start+1) (start+1)
1565 else Text arr (start+off) (n-start) : loop (n+d) (n+d)
1566 | otherwise = loop start (n+d)
1567 where Iter c d = iter t n
1570-- | /O(n)/ Breaks a 'Text' up into a list of 'Text's at
1571-- newline 'Char's. The resulting strings do not contain newlines.
1572lines :: Text -> [Text]
1573lines ps | null ps = []
1574 | otherwise = h : if null t
1576 else lines (unsafeTail t)
1577 where (# h,t #) = span_ (/= '\n') ps
1581-- | /O(n)/ Portably breaks a 'Text' up into a list of 'Text's at line
1584-- A line boundary is considered to be either a line feed, a carriage
1585-- return immediately followed by a line feed, or a carriage return.
1586-- This accounts for both Unix and Windows line ending conventions,
1587-- and for the old convention used on Mac OS 9 and earlier.
1588lines' :: Text -> [Text]
1589lines' ps | null ps = []
1590 | otherwise = h : case uncons t of
1593 | c == '\n' -> lines t'
1594 | c == '\r' -> case uncons t' of
1595 Just ('\n',t'') -> lines t''
1597 where (h,t) = span notEOL ps
1598 notEOL c = c /= '\n' && c /= '\r'
1599{-# INLINE lines' #-}
1602-- | /O(n)/ Joins lines, after appending a terminating newline to
1604unlines :: [Text] -> Text
1605unlines = concat . L.map (`snoc` '\n')
1606{-# INLINE unlines #-}
1608-- | /O(n)/ Joins words using single space characters.
1609unwords :: [Text] -> Text
1610unwords = intercalate (singleton ' ')
1611{-# INLINE unwords #-}
1613-- | /O(n)/ The 'isPrefixOf' function takes two 'Text's and returns
1614-- 'True' iff the first is a prefix of the second. Subject to fusion.
1615isPrefixOf :: Text -> Text -> Bool
1616isPrefixOf a@(Text _ _ alen) b@(Text _ _ blen) =
1617 alen <= blen && S.isPrefixOf (stream a) (stream b)
1618{-# INLINE [1] isPrefixOf #-}
1621"TEXT isPrefixOf -> fused" [~1] forall s t.
1622 isPrefixOf s t = S.isPrefixOf (stream s) (stream t)
1625-- | /O(n)/ The 'isSuffixOf' function takes two 'Text's and returns
1626-- 'True' iff the first is a suffix of the second.
1627isSuffixOf :: Text -> Text -> Bool
1628isSuffixOf a@(Text _aarr _aoff alen) b@(Text barr boff blen) =
1630 where d = blen - alen
1632 | otherwise = Text barr (boff+d) alen
1633{-# INLINE isSuffixOf #-}
1635-- | /O(n+m)/ The 'isInfixOf' function takes two 'Text's and returns
1636-- 'True' iff the first is contained, wholly and intact, anywhere
1637-- within the second.
1639-- In (unlikely) bad cases, this function's time complexity degrades
1641isInfixOf :: Text -> Text -> Bool
1642isInfixOf needle haystack
1643 | null needle = True
1644 | isSingleton needle = S.elem (unsafeHead needle) . S.stream $ haystack
1645 | otherwise = not . L.null . indices needle $ haystack
1646{-# INLINE [1] isInfixOf #-}
1649"TEXT isInfixOf/singleton -> S.elem/S.stream" [~1] forall n h.
1650 isInfixOf (singleton n) h = S.elem n (S.stream h)
1653-------------------------------------------------------------------------------
1656-- | /O(n)/ Return the suffix of the second string if its prefix
1657-- matches the entire first string.
1661-- > stripPrefix "foo" "foobar" == Just "bar"
1662-- > stripPrefix "" "baz" == Just "baz"
1663-- > stripPrefix "foo" "quux" == Nothing
1665-- This is particularly useful with the @ViewPatterns@ extension to
1668-- > {-# LANGUAGE ViewPatterns #-}
1669-- > import Data.Text as T
1671-- > fnordLength :: Text -> Int
1672-- > fnordLength (stripPrefix "fnord" -> Just suf) = T.length suf
1673-- > fnordLength _ = -1
1674stripPrefix :: Text -> Text -> Maybe Text
1675stripPrefix p@(Text _arr _off plen) t@(Text arr off len)
1676 | p `isPrefixOf` t = Just $! text arr (off+plen) (len-plen)
1677 | otherwise = Nothing
1679-- | /O(n)/ Find the longest non-empty common prefix of two strings
1680-- and return it, along with the suffixes of each string at which they
1683-- If the strings do not have a common prefix or either one is empty,
1684-- this function returns 'Nothing'.
1688-- > commonPrefixes "foobar" "fooquux" == Just ("foo","bar","quux")
1689-- > commonPrefixes "veeble" "fetzer" == Nothing
1690-- > commonPrefixes "" "baz" == Nothing
1691commonPrefixes :: Text -> Text -> Maybe (Text,Text,Text)
1692commonPrefixes t0@(Text arr0 off0 len0) t1@(Text arr1 off1 len1) = go 0 0
1694 go !i !j | i < len0 && j < len1 && a == b = go (i+d0) (j+d1)
1695 | i > 0 = Just (Text arr0 off0 i,
1696 text arr0 (off0+i) (len0-i),
1697 text arr1 (off1+j) (len1-j))
1698 | otherwise = Nothing
1699 where Iter a d0 = iter t0 i
1700 Iter b d1 = iter t1 j
1702-- | /O(n)/ Return the prefix of the second string if its suffix
1703-- matches the entire first string.
1707-- > stripSuffix "bar" "foobar" == Just "foo"
1708-- > stripSuffix "" "baz" == Just "baz"
1709-- > stripSuffix "foo" "quux" == Nothing
1711-- This is particularly useful with the @ViewPatterns@ extension to
1714-- > {-# LANGUAGE ViewPatterns #-}
1715-- > import Data.Text as T
1717-- > quuxLength :: Text -> Int
1718-- > quuxLength (stripSuffix "quux" -> Just pre) = T.length pre
1719-- > quuxLength _ = -1
1720stripSuffix :: Text -> Text -> Maybe Text
1721stripSuffix p@(Text _arr _off plen) t@(Text arr off len)
1722 | p `isSuffixOf` t = Just $! text arr off (len-plen)
1723 | otherwise = Nothing
1725-- | Add a list of non-negative numbers. Errors out on overflow.
1726sumP :: String -> [Int] -> Int
1729 | ax >= 0 = go ax xs
1730 | otherwise = overflowError fun
1734emptyError :: String -> a
1735emptyError fun = P.error $ "Data.Text." ++ fun ++ ": empty input"
1737overflowError :: String -> a
1738overflowError fun = P.error $ "Data.Text." ++ fun ++ ": size overflow"
1740-- | /O(n)/ Make a distinct copy of the given string, sharing no
1741-- storage with the original string.
1743-- As an example, suppose you read a large string, of which you need
1744-- only a small portion. If you do not use 'copy', the entire original
1745-- array will be kept alive in memory by the smaller string. Making a
1746-- copy \"breaks the link\" to the original array, allowing it to be
1747-- garbage collected if there are no other live references to it.
1749copy (Text arr off len) = Text (A.run go) 0 len
1751 go :: ST s (A.MArray s)
1754 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