    {-# LANGUAGE FlexibleInstances     #-}
    {-# LANGUAGE MultiParamTypeClasses #-}
    {-# LANGUAGE ScopedTypeVariables   #-}
    {-# LANGUAGE TypeSynonymInstances  #-}
    {-|

    Easy regular expression helpers, currently based on regex-tdfa. These should:

    - be cross-platform, not requiring C libraries

    - support unicode

    - support extended regular expressions

    - support replacement, with backreferences etc.

    - support splitting

    - have mnemonic names

    - have simple monomorphic types

    - work with simple strings

    Regex strings are automatically compiled into regular expressions the first
    time they are seen, and these are cached. If you use a huge number of unique
    regular expressions this might lead to increased memory usage. Several
    functions have memoised variants (*Memo), which also trade space for time.

    Currently two APIs are provided:

    - The old partial one (with ' suffixes') which will call error on any problem
      (eg with malformed regexps). This comes from hledger's origin as a
      command-line tool.

    - The new total one which will return an error message. This is better for
      long-running apps like hledger-web.

    Current limitations:

    - (?i) and similar are not supported

    -}

    module Hledger.Utils.Regex (
      -- * Regexp type and constructors
       Regexp(reString)
      ,toRegex
      ,toRegexCI
      ,toRegex'
      ,toRegexCI'
       -- * type aliases
      ,Replacement
      ,RegexError
       -- * total regex operations
      ,regexMatch
      ,regexReplace
      ,regexReplaceUnmemo
      ,regexReplaceAllBy
      )
    where

    import Control.Monad (foldM)
    import Data.Aeson (ToJSON(..), Value(String))
    import Data.Array ((!), elems, indices)
    import Data.Char (isDigit)
    import Data.List (foldl')
    import Data.MemoUgly (memo)
    import qualified Data.Text as T
    import Text.Regex.TDFA (
      Regex, CompOption(..), defaultCompOpt, defaultExecOpt,
      makeRegexOptsM, AllMatches(getAllMatches), match, MatchText,
      RegexLike(..), RegexMaker(..), RegexOptions(..), RegexContext(..)
      )

    import Hledger.Utils.UTF8IOCompat (error')

    -- | Regular expression. Extended regular expression-ish syntax ? But does not support eg (?i) syntax.
    data Regexp
      = Regexp   { Regexp -> String
    reString :: String, Regexp -> Regex
    reCompiled :: Regex }
      | RegexpCI { reString :: String, reCompiled :: Regex }

    instance Eq Regexp where
      Regexp   s1 :: String
    s1 _ == :: Regexp -> Regexp -> Bool
    == Regexp   s2 :: String
    s2 _ = String
    s1 String -> String -> Bool
    forall a. Eq a => a -> a -> Bool
    == String
    s2
      RegexpCI s1 :: String
    s1 _ == RegexpCI s2 :: String
    s2 _ = String
    s1 String -> String -> Bool
    forall a. Eq a => a -> a -> Bool
    == String
    s2
      _ == _ = Bool
    False

    instance Ord Regexp where
      Regexp   s1 :: String
    s1 _ compare :: Regexp -> Regexp -> Ordering
    `compare` Regexp   s2 :: String
    s2 _ = String
    s1 String -> String -> Ordering
    forall a. Ord a => a -> a -> Ordering
    `compare` String
    s2
      RegexpCI s1 :: String
    s1 _ `compare` RegexpCI s2 :: String
    s2 _ = String
    s1 String -> String -> Ordering
    forall a. Ord a => a -> a -> Ordering
    `compare` String
    s2
      Regexp _ _ `compare` RegexpCI _ _ = Ordering
    LT
      RegexpCI _ _ `compare` Regexp _ _ = Ordering
    GT

    instance Show Regexp where
      showsPrec :: Int -> Regexp -> ShowS
    showsPrec d :: Int
    d r :: Regexp
    r = Bool -> ShowS -> ShowS
    showParen (Int
    d Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    > Int
    app_prec) (ShowS -> ShowS) -> ShowS -> ShowS
    forall a b. (a -> b) -> a -> b
    $ ShowS
    reCons ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Int -> String -> ShowS
    forall a. Show a => Int -> a -> ShowS
    showsPrec (Int
    app_precInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +1) (Regexp -> String
    reString Regexp
    r)
        where app_prec :: Int
    app_prec = 10
              reCons :: ShowS
    reCons = case Regexp
    r of Regexp   _ _ -> String -> ShowS
    showString "Regexp "
                                 RegexpCI _ _ -> String -> ShowS
    showString "RegexpCI "

    instance Read Regexp where
      readsPrec :: Int -> ReadS Regexp
    readsPrec d :: Int
    d r :: String
    r =  Bool -> ReadS Regexp -> ReadS Regexp
    forall a. Bool -> ReadS a -> ReadS a
    readParen (Int
    d Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    > Int
    app_prec) (\r :: String
    r -> [(String -> Regexp
    toRegexCI' String
    m,String
    t) |
                                                        ("RegexCI",s :: String
    s) <- ReadS String
    lex String
    r,
                                                        (m :: String
    m,t :: String
    t) <- Int -> ReadS String
    forall a. Read a => Int -> ReadS a
    readsPrec (Int
    app_precInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +1) String
    s]) String
    r
                    [(Regexp, String)] -> [(Regexp, String)] -> [(Regexp, String)]
    forall a. [a] -> [a] -> [a]
    ++ Bool -> ReadS Regexp -> ReadS Regexp
    forall a. Bool -> ReadS a -> ReadS a
    readParen (Int
    d Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    > Int
    app_prec) (\r :: String
    r -> [(String -> Regexp
    toRegex' String
    m, String
    t) |
                                                        ("Regex",s :: String
    s) <- ReadS String
    lex String
    r,
                                                        (m :: String
    m,t :: String
    t) <- Int -> ReadS String
    forall a. Read a => Int -> ReadS a
    readsPrec (Int
    app_precInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +1) String
    s]) String
    r
        where app_prec :: Int
    app_prec = 10

    instance ToJSON Regexp where
      toJSON :: Regexp -> Value
    toJSON (Regexp   s :: String
    s _) = Text -> Value
    String (Text -> Value) -> (String -> Text) -> String -> Value
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . String -> Text
    T.pack (String -> Value) -> String -> Value
    forall a b. (a -> b) -> a -> b
    $ "Regexp "   String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    s
      toJSON (RegexpCI s :: String
    s _) = Text -> Value
    String (Text -> Value) -> (String -> Text) -> String -> Value
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . String -> Text
    T.pack (String -> Value) -> String -> Value
    forall a b. (a -> b) -> a -> b
    $ "RegexpCI " String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    s

    instance RegexLike Regexp String where
      matchOnce :: Regexp -> String -> Maybe MatchArray
    matchOnce = Regex -> String -> Maybe MatchArray
    forall regex source.
    RegexLike regex source =>
    regex -> source -> Maybe MatchArray
    matchOnce (Regex -> String -> Maybe MatchArray)
    -> (Regexp -> Regex) -> Regexp -> String -> Maybe MatchArray
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Regexp -> Regex
    reCompiled
      matchAll :: Regexp -> String -> [MatchArray]
    matchAll = Regex -> String -> [MatchArray]
    forall regex source.
    RegexLike regex source =>
    regex -> source -> [MatchArray]
    matchAll (Regex -> String -> [MatchArray])
    -> (Regexp -> Regex) -> Regexp -> String -> [MatchArray]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Regexp -> Regex
    reCompiled
      matchCount :: Regexp -> String -> Int
    matchCount = Regex -> String -> Int
    forall regex source.
    RegexLike regex source =>
    regex -> source -> Int
    matchCount (Regex -> String -> Int)
    -> (Regexp -> Regex) -> Regexp -> String -> Int
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Regexp -> Regex
    reCompiled
      matchTest :: Regexp -> String -> Bool
    matchTest = Regex -> String -> Bool
    forall regex source.
    RegexLike regex source =>
    regex -> source -> Bool
    matchTest (Regex -> String -> Bool)
    -> (Regexp -> Regex) -> Regexp -> String -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Regexp -> Regex
    reCompiled
      matchAllText :: Regexp -> String -> [MatchText String]
    matchAllText = Regex -> String -> [MatchText String]
    forall regex source.
    RegexLike regex source =>
    regex -> source -> [MatchText source]
    matchAllText (Regex -> String -> [MatchText String])
    -> (Regexp -> Regex) -> Regexp -> String -> [MatchText String]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Regexp -> Regex
    reCompiled
      matchOnceText :: Regexp -> String -> Maybe (String, MatchText String, String)
    matchOnceText = Regex -> String -> Maybe (String, MatchText String, String)
    forall regex source.
    RegexLike regex source =>
    regex -> source -> Maybe (source, MatchText source, source)
    matchOnceText (Regex -> String -> Maybe (String, MatchText String, String))
    -> (Regexp -> Regex)
    -> Regexp
    -> String
    -> Maybe (String, MatchText String, String)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Regexp -> Regex
    reCompiled

    instance RegexContext Regexp String String where
      match :: Regexp -> ShowS
    match = Regex -> ShowS
    forall regex source target.
    RegexContext regex source target =>
    regex -> source -> target
    match (Regex -> ShowS) -> (Regexp -> Regex) -> Regexp -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Regexp -> Regex
    reCompiled
      matchM :: Regexp -> String -> m String
    matchM = Regex -> String -> m String
    forall regex source target (m :: * -> *).
    (RegexContext regex source target, MonadFail m) =>
    regex -> source -> m target
    matchM (Regex -> String -> m String)
    -> (Regexp -> Regex) -> Regexp -> String -> m String
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Regexp -> Regex
    reCompiled

    -- Convert a Regexp string to a compiled Regex, or return an error message.
    toRegex :: String -> Either RegexError Regexp
    toRegex :: String -> Either String Regexp
    toRegex = (String -> Either String Regexp) -> String -> Either String Regexp
    forall a b. Ord a => (a -> b) -> a -> b
    memo ((String -> Either String Regexp)
     -> String -> Either String Regexp)
    -> (String -> Either String Regexp)
    -> String
    -> Either String Regexp
    forall a b. (a -> b) -> a -> b
    $ \s :: String
    s -> String -> Maybe Regexp -> Either String Regexp
    forall a. String -> Maybe a -> Either String a
    mkRegexErr String
    s (String -> Regex -> Regexp
    Regexp String
    s (Regex -> Regexp) -> Maybe Regex -> Maybe Regexp
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> String -> Maybe Regex
    forall regex compOpt execOpt source (m :: * -> *).
    (RegexMaker regex compOpt execOpt source, MonadFail m) =>
    source -> m regex
    makeRegexM String
    s)

    -- Like toRegex, but make a case-insensitive Regex.
    toRegexCI :: String -> Either RegexError Regexp
    toRegexCI :: String -> Either String Regexp
    toRegexCI = (String -> Either String Regexp) -> String -> Either String Regexp
    forall a b. Ord a => (a -> b) -> a -> b
    memo ((String -> Either String Regexp)
     -> String -> Either String Regexp)
    -> (String -> Either String Regexp)
    -> String
    -> Either String Regexp
    forall a b. (a -> b) -> a -> b
    $ \s :: String
    s -> String -> Maybe Regexp -> Either String Regexp
    forall a. String -> Maybe a -> Either String a
    mkRegexErr String
    s (String -> Regex -> Regexp
    RegexpCI String
    s (Regex -> Regexp) -> Maybe Regex -> Maybe Regexp
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> CompOption -> ExecOption -> String -> Maybe Regex
    forall regex compOpt execOpt source (m :: * -> *).
    (RegexMaker regex compOpt execOpt source, MonadFail m) =>
    compOpt -> execOpt -> source -> m regex
    makeRegexOptsM CompOption
    forall regex compOpt execOpt.
    RegexOptions regex compOpt execOpt =>
    compOpt
    defaultCompOpt{caseSensitive :: Bool
    caseSensitive=Bool
    False} ExecOption
    forall regex compOpt execOpt.
    RegexOptions regex compOpt execOpt =>
    execOpt
    defaultExecOpt String
    s)

    -- | Make a nice error message for a regexp error.
    mkRegexErr :: String -> Maybe a -> Either RegexError a
    mkRegexErr :: String -> Maybe a -> Either String a
    mkRegexErr s :: String
    s = Either String a
    -> (a -> Either String a) -> Maybe a -> Either String a
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe (String -> Either String a
    forall a b. a -> Either a b
    Left String
    errmsg) a -> Either String a
    forall a b. b -> Either a b
    Right
      where errmsg :: String
    errmsg = "this regular expression could not be compiled: " String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    s

    -- Convert a Regexp string to a compiled Regex, throw an error
    toRegex' :: String -> Regexp
    toRegex' :: String -> Regexp
    toRegex' = (String -> Regexp)
    -> (Regexp -> Regexp) -> Either String Regexp -> Regexp
    forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
    either String -> Regexp
    forall a. String -> a
    error' Regexp -> Regexp
    forall a. a -> a
    id (Either String Regexp -> Regexp)
    -> (String -> Either String Regexp) -> String -> Regexp
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . String -> Either String Regexp
    toRegex

    -- Like toRegex', but make a case-insensitive Regex.
    toRegexCI' :: String -> Regexp
    toRegexCI' :: String -> Regexp
    toRegexCI' = (String -> Regexp)
    -> (Regexp -> Regexp) -> Either String Regexp -> Regexp
    forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
    either String -> Regexp
    forall a. String -> a
    error' Regexp -> Regexp
    forall a. a -> a
    id (Either String Regexp -> Regexp)
    -> (String -> Either String Regexp) -> String -> Regexp
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . String -> Either String Regexp
    toRegexCI

    -- | A replacement pattern. May include numeric backreferences (\N).
    type Replacement = String

    -- | An regular expression compilation/processing error message.
    type RegexError = String

    -- helpers

    -- | Test whether a Regexp matches a String. This is an alias for `matchTest` for consistent
    -- naming.
    regexMatch :: Regexp -> String -> Bool
    regexMatch :: Regexp -> String -> Bool
    regexMatch = Regexp -> String -> Bool
    forall regex source.
    RegexLike regex source =>
    regex -> source -> Bool
    matchTest

    --------------------------------------------------------------------------------
    -- new total functions

    -- | A memoising version of regexReplace. Caches the result for each
    -- search pattern, replacement pattern, target string tuple.
    regexReplace :: Regexp -> Replacement -> String -> Either RegexError String
    regexReplace :: Regexp -> String -> String -> Either String String
    regexReplace re :: Regexp
    re repl :: String
    repl = (String -> Either String String) -> String -> Either String String
    forall a b. Ord a => (a -> b) -> a -> b
    memo ((String -> Either String String)
     -> String -> Either String String)
    -> (String -> Either String String)
    -> String
    -> Either String String
    forall a b. (a -> b) -> a -> b
    $ Regexp -> String -> String -> Either String String
    regexReplaceUnmemo Regexp
    re String
    repl

    -- helpers:

    -- Replace this regular expression with this replacement pattern in this
    -- string, or return an error message.
    regexReplaceUnmemo :: Regexp -> Replacement -> String -> Either RegexError String
    regexReplaceUnmemo :: Regexp -> String -> String -> Either String String
    regexReplaceUnmemo re :: Regexp
    re repl :: String
    repl s :: String
    s = (String -> MatchText String -> Either String String)
    -> String -> [MatchText String] -> Either String String
    forall (t :: * -> *) (m :: * -> *) b a.
    (Foldable t, Monad m) =>
    (b -> a -> m b) -> b -> t a -> m b
    foldM (String -> String -> MatchText String -> Either String String
    replaceMatch String
    repl) String
    s ([MatchText String] -> [MatchText String]
    forall a. [a] -> [a]
    reverse ([MatchText String] -> [MatchText String])
    -> [MatchText String] -> [MatchText String]
    forall a b. (a -> b) -> a -> b
    $ Regex -> String -> [MatchText String]
    forall regex source target.
    RegexContext regex source target =>
    regex -> source -> target
    match (Regexp -> Regex
    reCompiled Regexp
    re) String
    s :: [MatchText String])
      where
        -- Replace one match within the string with the replacement text
        -- appropriate for this match. Or return an error message.
        replaceMatch :: Replacement -> String -> MatchText String -> Either RegexError String
        replaceMatch :: String -> String -> MatchText String -> Either String String
    replaceMatch replpat :: String
    replpat s :: String
    s matchgroups :: MatchText String
    matchgroups =
          Either String String
    erepl Either String String
    -> (String -> Either String String) -> Either String String
    forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
    >>= \repl :: String
    repl -> String -> Either String String
    forall a b. b -> Either a b
    Right (String -> Either String String) -> String -> Either String String
    forall a b. (a -> b) -> a -> b
    $ String
    pre String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    repl String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    post
          where
            ((_,(off :: Int
    off,len :: Int
    len)):_) = MatchText String -> [(String, (Int, Int))]
    forall i e. Array i e -> [e]
    elems MatchText String
    matchgroups  -- groups should have 0-based indexes, and there should always be at least one, since this is a match
            (pre :: String
    pre, post' :: String
    post') = Int -> String -> (String, String)
    forall a. Int -> [a] -> ([a], [a])
    splitAt Int
    off String
    s
            post :: String
    post = Int -> ShowS
    forall a. Int -> [a] -> [a]
    drop Int
    len String
    post'
            -- The replacement text: the replacement pattern with all
            -- numeric backreferences replaced by the appropriate groups
            -- from this match. Or an error message.
            erepl :: Either String String
    erepl = Regexp
    -> (String -> Either String String)
    -> String
    -> Either String String
    forall (m :: * -> *).
    Monad m =>
    Regexp -> (String -> m String) -> String -> m String
    regexReplaceAllByM Regexp
    backrefRegex (MatchText String -> String -> Either String String
    lookupMatchGroup MatchText String
    matchgroups) String
    replpat
              where
                -- Given some match groups and a numeric backreference,
                -- return the referenced group text, or an error message.
                lookupMatchGroup :: MatchText String -> String -> Either RegexError String
                lookupMatchGroup :: MatchText String -> String -> Either String String
    lookupMatchGroup grps :: MatchText String
    grps ('\\':s :: String
    s@(_:_)) | (Char -> Bool) -> String -> Bool
    forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
    all Char -> Bool
    isDigit String
    s =
                  case String -> Int
    forall a. Read a => String -> a
    read String
    s of n :: Int
    n | Int
    n Int -> [Int] -> Bool
    forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
    `elem` MatchText String -> [Int]
    forall i e. Ix i => Array i e -> [i]
    indices MatchText String
    grps -> String -> Either String String
    forall a b. b -> Either a b
    Right (String -> Either String String) -> String -> Either String String
    forall a b. (a -> b) -> a -> b
    $ (String, (Int, Int)) -> String
    forall a b. (a, b) -> a
    fst (MatchText String
    grps MatchText String -> Int -> (String, (Int, Int))
    forall i e. Ix i => Array i e -> i -> e
    ! Int
    n)
                                 _                         -> String -> Either String String
    forall a b. a -> Either a b
    Left (String -> Either String String) -> String -> Either String String
    forall a b. (a -> b) -> a -> b
    $ "no match group exists for backreference \"\\"String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++String
    sString -> ShowS
    forall a. [a] -> [a] -> [a]
    ++"\""
                lookupMatchGroup _ s :: String
    s = String -> Either String String
    forall a b. a -> Either a b
    Left (String -> Either String String) -> String -> Either String String
    forall a b. (a -> b) -> a -> b
    $ "lookupMatchGroup called on non-numeric-backreference \""String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++String
    sString -> ShowS
    forall a. [a] -> [a] -> [a]
    ++"\", shouldn't happen"
        backrefRegex :: Regexp
    backrefRegex = String -> Regexp
    toRegex' "\\\\[0-9]+"  -- PARTIAL: should not fail

    -- regexReplace' :: Regexp -> Replacement -> String -> String
    -- regexReplace' re repl s =
    --     foldl (replaceMatch repl) s (reverse $ match (reCompiled re) s :: [MatchText String])
    --   where
    --     replaceMatch :: Replacement -> String -> MatchText String -> String
    --     replaceMatch replpat s matchgroups = pre ++ repl ++ post
    --       where
    --         ((_,(off,len)):_) = elems matchgroups  -- groups should have 0-based indexes, and there should always be at least one, since this is a match
    --         (pre, post') = splitAt off s
    --         post = drop len post'
    --         repl = regexReplaceAllBy backrefRegex (lookupMatchGroup matchgroups) replpat
    --           where
    --             lookupMatchGroup :: MatchText String -> String -> String
    --             lookupMatchGroup grps ('\\':s@(_:_)) | all isDigit s =
    --               case read s of n | n `elem` indices grps -> fst (grps ! n)
    --               -- PARTIAL:
    --                              _                         -> error' $ "no match group exists for backreference \"\\"++s++"\""
    --             lookupMatchGroup _ s = error' $ "lookupMatchGroup called on non-numeric-backreference \""++s++"\", shouldn't happen"
    --     backrefRegex = toRegex' "\\\\[0-9]+"  -- PARTIAL: should not fail

    -- helpers

    -- adapted from http://stackoverflow.com/questions/9071682/replacement-substition-with-haskell-regex-libraries:

    -- Replace all occurrences of a regexp in a string, transforming each match
    -- with the given pure function.
    regexReplaceAllBy :: Regexp -> (String -> String) -> String -> String
    regexReplaceAllBy :: Regexp -> ShowS -> ShowS
    regexReplaceAllBy re :: Regexp
    re transform :: ShowS
    transform s :: String
    s = ShowS
    prependdone String
    rest
      where
        (_, rest :: String
    rest, prependdone :: ShowS
    prependdone) = ((Int, String, ShowS) -> (Int, Int) -> (Int, String, ShowS))
    -> (Int, String, ShowS) -> [(Int, Int)] -> (Int, String, ShowS)
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    foldl' (Int, String, ShowS) -> (Int, Int) -> (Int, String, ShowS)
    go (0, String
    s, ShowS
    forall a. a -> a
    id) [(Int, Int)]
    matches
          where
            matches :: [(Int, Int)]
    matches = AllMatches [] (Int, Int) -> [(Int, Int)]
    forall (f :: * -> *) b. AllMatches f b -> f b
    getAllMatches (AllMatches [] (Int, Int) -> [(Int, Int)])
    -> AllMatches [] (Int, Int) -> [(Int, Int)]
    forall a b. (a -> b) -> a -> b
    $ Regex -> String -> AllMatches [] (Int, Int)
    forall regex source target.
    RegexContext regex source target =>
    regex -> source -> target
    match (Regexp -> Regex
    reCompiled Regexp
    re) String
    s :: [(Int, Int)]  -- offset and length
            go :: (Int,String,String->String) -> (Int,Int) ->  (Int,String,String->String)
            go :: (Int, String, ShowS) -> (Int, Int) -> (Int, String, ShowS)
    go (pos :: Int
    pos,todo :: String
    todo,prepend :: ShowS
    prepend) (off :: Int
    off,len :: Int
    len) =
              let (prematch :: String
    prematch, matchandrest :: String
    matchandrest) = Int -> String -> (String, String)
    forall a. Int -> [a] -> ([a], [a])
    splitAt (Int
    off Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    pos) String
    todo
                  (matched :: String
    matched, rest :: String
    rest) = Int -> String -> (String, String)
    forall a. Int -> [a] -> ([a], [a])
    splitAt Int
    len String
    matchandrest
              in (Int
    off Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    len, String
    rest, ShowS
    prepend ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (String
    prematchString -> ShowS
    forall a. [a] -> [a] -> [a]
    ++) ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (ShowS
    transform String
    matched String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++))

    -- Replace all occurrences of a regexp in a string, transforming each match
    -- with the given monadic function. Eg if the monad is Either, a Left result
    -- from the transform function short-circuits and is returned as the overall
    -- result.
    regexReplaceAllByM :: forall m. Monad m => Regexp -> (String -> m String) -> String -> m String
    regexReplaceAllByM :: Regexp -> (String -> m String) -> String -> m String
    regexReplaceAllByM re :: Regexp
    re transform :: String -> m String
    transform s :: String
    s =
        ((Int, String, ShowS) -> (Int, Int) -> m (Int, String, ShowS))
    -> (Int, String, ShowS) -> [(Int, Int)] -> m (Int, String, ShowS)
    forall (t :: * -> *) (m :: * -> *) b a.
    (Foldable t, Monad m) =>
    (b -> a -> m b) -> b -> t a -> m b
    foldM (Int, String, ShowS) -> (Int, Int) -> m (Int, String, ShowS)
    go (0, String
    s, ShowS
    forall a. a -> a
    id) [(Int, Int)]
    matches m (Int, String, ShowS)
    -> ((Int, String, ShowS) -> m String) -> m String
    forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
    >>= \(_, rest :: String
    rest, prependdone :: ShowS
    prependdone) -> String -> m String
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure (String -> m String) -> String -> m String
    forall a b. (a -> b) -> a -> b
    $ ShowS
    prependdone String
    rest
      where
        matches :: [(Int, Int)]
    matches = AllMatches [] (Int, Int) -> [(Int, Int)]
    forall (f :: * -> *) b. AllMatches f b -> f b
    getAllMatches (AllMatches [] (Int, Int) -> [(Int, Int)])
    -> AllMatches [] (Int, Int) -> [(Int, Int)]
    forall a b. (a -> b) -> a -> b
    $ Regex -> String -> AllMatches [] (Int, Int)
    forall regex source target.
    RegexContext regex source target =>
    regex -> source -> target
    match (Regexp -> Regex
    reCompiled Regexp
    re) String
    s :: [(Int, Int)]  -- offset and length
        go :: (Int,String,String->String) -> (Int,Int) -> m (Int,String,String->String)
        go :: (Int, String, ShowS) -> (Int, Int) -> m (Int, String, ShowS)
    go (pos :: Int
    pos,todo :: String
    todo,prepend :: ShowS
    prepend) (off :: Int
    off,len :: Int
    len) =
          let (prematch :: String
    prematch, matchandrest :: String
    matchandrest) = Int -> String -> (String, String)
    forall a. Int -> [a] -> ([a], [a])
    splitAt (Int
    off Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    pos) String
    todo
              (matched :: String
    matched, rest :: String
    rest) = Int -> String -> (String, String)
    forall a. Int -> [a] -> ([a], [a])
    splitAt Int
    len String
    matchandrest
          in String -> m String
    transform String
    matched m String
    -> (String -> m (Int, String, ShowS)) -> m (Int, String, ShowS)
    forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
    >>= \matched' :: String
    matched' -> (Int, String, ShowS) -> m (Int, String, ShowS)
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure (Int
    off Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    len, String
    rest, ShowS
    prepend ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (String
    prematchString -> ShowS
    forall a. [a] -> [a] -> [a]
    ++) ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (String
    matched' String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++))