packages feed

oglyad-0.1.6.0: src/Oglyad/Regex.hs

-- | the dialect of Rust's regex crate that andax's find(), find_all() and
-- sub() use (andax/fns/kokoro.rs in FyraLabs/anda).
--
-- it mirrors Rust's BoundedBacktracker: a Thompson NFA shaped like
-- regex-automata builds it, backtracked with a visited set of (state,
-- position) pairs. the visited set also decides which captures win when a
-- repeated group can match empty, so the NFA shape has to match Rust's to
-- get the same answers. it was checked against the real crate on every regex
-- in terrapkg/packages and ~300k fuzzed ones.
--
-- anything the parser doesn't handle, like \p{...}, nested classes or class
-- operations, is a compile error, which callers treat as "can't tell"
module Oglyad.Regex
  ( Regex,
    compile,
    captures,
    capturesAll,
    replaceAll,
  )
where

import Control.Applicative ((<|>))
import Control.Monad.ST (runST)
import Data.Char (GeneralCategory (..), generalCategory, isAlphaNum, isAsciiLower, isAsciiUpper, isDigit, isHexDigit, isPunctuation, isSpace, isSymbol, toLower, toUpper)
import Data.IntMap.Strict (IntMap)
import Data.IntMap.Strict qualified as IM
import Data.Text (Text)
import Data.Text qualified as T
import Data.Vector qualified as V
import Data.Vector.Unboxed qualified as VU
import Data.Vector.Unboxed.Mutable qualified as MVU
import Text.Read (readMaybe)

type Multiline = Bool

type WantBoundary = Bool

type Greedy = Bool

data Node
  = One (Char -> Bool)
  | LineStart Multiline
  | LineEnd Multiline
  | WordBoundary WantBoundary
  | Group (Maybe Int) Node
  | Alt [Node]
  | Seq [Node]
  | Repeat Int (Maybe Int) Greedy Node

data Regex = Regex
  { reProg :: Prog,
    reGroups :: Int,
    reNames :: [(Text, Int)]
  }

data Flags = Flags {fI, fM, fS :: Bool}

data ParseState = ParseState
  { stRest :: String,
    stGroupCount :: Int,
    stGroupNames :: [(Text, Int)]
  }

type Parse a = ParseState -> Either Text (a, ParseState)

compile :: Text -> Either Text Regex
compile src = do
  (node, st) <- alternation (Flags False False False) (ParseState (T.unpack src) 0 [])
  case stRest st of
    [] -> Right (Regex (toProg (stGroupCount st) node) (stGroupCount st) (stGroupNames st))
    c : _ -> Left ("unexpected " <> T.singleton c)

-- | a|b|c, up to a ')' or the end. (?flags) partway through applies to the
-- rest of the group, alternatives included, like Rust
alternation :: Flags -> Parse Node
alternation flags st0 = go flags st0 []
  where
    go fl st acc = do
      ((node, fl'), st') <- sequence' fl st []
      case stRest st' of
        '|' : rest -> go fl' st' {stRest = rest} (node : acc)
        _ -> Right (alt (reverse (node : acc)), st')
    alt [n] = n
    alt ns = Alt ns

sequence' :: Flags -> ParseState -> [Node] -> Either Text ((Node, Flags), ParseState)
sequence' fl st acc = case stRest st of
  [] -> done
  '|' : _ -> done
  ')' : _ -> done
  '(' : '?' : rest
    | (fs, ')' : rest') <- span (`elem` ("imsxUR-" :: String)) rest,
      not (null fs) -> do
        fl' <- setFlags fl fs
        sequence' fl' st {stRest = rest'} acc
  _ -> do
    (atom, st1) <- atomP fl st
    (node, st2) <- quantifier atom st1
    sequence' fl st2 (node : acc)
  where
    done = Right ((Seq (reverse acc), fl), st)

setFlags :: Flags -> String -> Either Text Flags
setFlags fl0 = go True fl0
  where
    go _ fl [] = Right fl
    go on fl (c : cs) = case c of
      '-' -> go False fl cs
      'i' -> go on fl {fI = on} cs
      'm' -> go on fl {fM = on} cs
      's' -> go on fl {fS = on} cs
      _ -> Left ("unsupported flag " <> T.singleton c)

quantifier :: Node -> Parse Node
quantifier atom st = case stRest st of
  '*' : rest -> lazy 0 Nothing rest
  '+' : rest -> lazy 1 Nothing rest
  '?' : rest -> lazy 0 (Just 1) rest
  '{' : rest
    | (a, rest1) <- span isDigit rest,
      not (null a) ->
        case rest1 of
          '}' : rest2 -> bounded a (Just a) rest2
          ',' : '}' : rest2 -> bounded a Nothing rest2
          ',' : rest2
            | (b, '}' : rest3) <- span isDigit rest2, not (null b) -> bounded a (Just b) rest3
          _ -> Left "bad repetition"
  _ -> Right (atom, st)
  where
    bounded a b rest = case (readMaybe a, traverse readMaybe b) of
      (Just lo, Just hi) | maybe True (>= lo) hi -> lazy lo hi rest
      _ -> Left "bad repetition"
    lazy lo hi = \case
      '?' : rest -> Right (Repeat lo hi False atom, st {stRest = rest})
      rest -> Right (Repeat lo hi True atom, st {stRest = rest})

atomP :: Flags -> Parse Node
atomP fl st = case stRest st of
  '(' : '?' : ':' : rest -> group Nothing st {stRest = rest}
  '(' : '?' : 'P' : '<' : rest -> named rest
  '(' : '?' : '<' : rest -> named rest
  '(' : '?' : _ -> Left "unsupported group"
  '(' : rest ->
    let n = stGroupCount st + 1
     in group (Just n) st {stRest = rest, stGroupCount = n}
  '[' : rest -> do
    (p, rest') <- bracketClass fl rest
    Right (One p, st {stRest = rest'})
  '.' : rest -> Right (One (\c -> fS fl || c /= '\n'), st {stRest = rest})
  '^' : rest -> Right (LineStart (fM fl), st {stRest = rest})
  '$' : rest -> Right (LineEnd (fM fl), st {stRest = rest})
  '\\' : rest -> do
    (node, rest') <- escape fl rest
    Right (node, st {stRest = rest'})
  c : rest
    | c `elem` ("*+?{" :: String) -> Left "repetition with nothing to repeat"
    | otherwise -> Right (One (charEq fl c), st {stRest = rest})
  [] -> Left "unexpected end"
  where
    group idx s = do
      (inner, s') <- alternation fl s
      case stRest s' of
        ')' : rest -> Right (Group idx inner, s' {stRest = rest})
        _ -> Left "unclosed group"
    named rest = case span (\c -> isAlphaNum c || c == '_') rest of
      (name, '>' : rest')
        | not (null name) ->
            let n = stGroupCount st + 1
             in group (Just n) st {stRest = rest', stGroupCount = n, stGroupNames = (T.pack name, n) : stGroupNames st}
      _ -> Left "bad group name"

charEq :: Flags -> Char -> Char -> Bool
charEq fl c
  | fI fl = \x -> toLower x == toLower c || toUpper x == toUpper c
  | otherwise = (== c)

escape :: Flags -> String -> Either Text (Node, String)
escape fl = \case
  'b' : rest -> Right (WordBoundary True, rest)
  'B' : rest -> Right (WordBoundary False, rest)
  'A' : rest -> Right (LineStart False, rest)
  'z' : rest -> Right (LineEnd False, rest)
  s -> do
    (p, rest) <- classEscape fl s
    Right (One p, rest)

classEscape :: Flags -> String -> Either Text (Char -> Bool, String)
classEscape fl = \case
  'd' : rest -> Right (isUnicodeDigit, rest)
  'D' : rest -> Right (not . isUnicodeDigit, rest)
  'w' : rest -> Right (isWord, rest)
  'W' : rest -> Right (not . isWord, rest)
  's' : rest -> Right (isSpace, rest)
  'S' : rest -> Right (not . isSpace, rest)
  'n' : rest -> lit '\n' rest
  't' : rest -> lit '\t' rest
  'r' : rest -> lit '\r' rest
  'f' : rest -> lit '\f' rest
  'v' : rest -> lit '\v' rest
  'x' : a : b : rest | isHexDigit a && isHexDigit b, Just n <- readMaybe ("0x" <> [a, b]) -> lit (toEnum n) rest
  c : rest
    | isPunctuation c || isSymbol c || c == ' ' -> lit c rest
  _ -> Left "unsupported escape"
  where
    lit c rest = Right (charEq fl c, rest)

isUnicodeDigit :: Char -> Bool
isUnicodeDigit c = generalCategory c == DecimalNumber

isWord :: Char -> Bool
isWord c = isAlphaNum c || c == '_'

bracketClass :: Flags -> String -> Either Text (Char -> Bool, String)
bracketClass fl s0 = do
  let (negated, s1) = case s0 of
        '^' : r -> (True, r)
        r -> (False, r)
  -- a ']' right at the start is a literal
  (items, rest) <- case s1 of
    ']' : r -> go [charEq fl ']'] r
    r -> go [] r
  let p c = any ($ c) items
  Right (if negated then not . p else p, rest)
  where
    go acc = \case
      ']' : rest -> Right (acc, rest)
      '[' : ':' : rest
        | (name, ':' : ']' : rest') <- span isAsciiLower rest -> do
            p <- posix name
            go (p : acc) rest'
      '[' : _ -> Left "nested classes aren't supported"
      '&' : '&' : _ -> Left "class operations aren't supported"
      '-' : '-' : _ -> Left "class operations aren't supported"
      '~' : '~' : _ -> Left "class operations aren't supported"
      s -> do
        (lo, rest) <- classItem s
        case (lo, rest) of
          (ItemChar c, '-' : rest') | take 1 rest' /= "]" -> do
            (hi, rest'') <- classItem rest'
            case hi of
              ItemChar d | c <= d -> go (range c d : acc) rest''
              _ -> Left "bad class range"
          (ItemChar c, _) -> go (charEq fl c : acc) rest
          (ItemSet p, _) -> go (p : acc) rest
    classItem = \case
      '\\' : rest -> case rest of
        c : rest' | isPunctuation c || isSymbol c || c == ' ' -> Right (ItemChar c, rest')
        'n' : rest' -> Right (ItemChar '\n', rest')
        't' : rest' -> Right (ItemChar '\t', rest')
        _ -> do
          (p, rest') <- classEscape fl rest
          Right (ItemSet p, rest')
      c : rest -> Right (ItemChar c, rest)
      [] -> Left "unclosed class"
    range lo hi
      | fI fl = \c -> any (\x -> lo <= x && x <= hi) [c, toLower c, toUpper c]
      | otherwise = \c -> lo <= c && c <= hi
    posix = \case
      "alnum" -> Right isAlphaNumAscii
      "alpha" -> Right (\c -> isAsciiLower c || isAsciiUpper c)
      "digit" -> Right isDigit
      "lower" -> Right isAsciiLower
      "upper" -> Right isAsciiUpper
      "space" -> Right (`elem` (" \t\n\r\f\v" :: String))
      "xdigit" -> Right isHexDigit
      "punct" -> Right (\c -> c < '\x80' && (isPunctuation c || isSymbol c))
      _ -> Left "unknown posix class"
    isAlphaNumAscii c = isDigit c || isAsciiLower c || isAsciiUpper c

data ClassItem = ItemChar Char | ItemSet (Char -> Bool)

data Look = AtLineStart Bool | AtLineEnd Bool | AtWordBoundary Bool

data State
  = SChar (Char -> Bool) !Int
  | -- | alternatives in preference order
    SUnion [Int]
  | SCapture !Int !Int
  | SLook Look !Int
  | SMatch

data Prog = Prog
  { progStates :: V.Vector State,
    progStart :: Int,
    -- | a start and an end per group, group 0 being the whole match
    progSlots :: Int
  }

data Build = Build {nextId :: !Int, builtStates :: IntMap State}

new :: State -> Build -> (Int, Build)
new st b@Build {..} = (nextId, b {nextId = nextId + 1, builtStates = IM.insert nextId st builtStates})

reserve :: Build -> (Int, Build)
reserve b@Build {..} = (nextId, b {nextId = nextId + 1})

fill :: Int -> State -> Build -> Build
fill i st b@Build {..} = b {builtStates = IM.insert i st builtStates}

toProg :: Int -> Node -> Prog
toProg groups node =
  let (matchId, b1) = new SMatch (Build 0 IM.empty)
      (end0, b2) = new (SCapture 1 matchId) b1
      (body, b3) = nfa node end0 b2
      (start, Build {nextId = n, builtStates = states}) = new (SCapture 0 body) b3
   in Prog (V.generate n (states IM.!)) start (2 * (groups + 1))

-- | the repetition shapes follow regex-automata's thompson compiler
-- (c_at_least, c_bounded, c_zero_or_one), since the visited set makes the
-- shape observable
nfa :: Node -> Int -> Build -> (Int, Build)
nfa node next b = case node of
  One p -> new (SChar p next) b
  LineStart multi -> new (SLook (AtLineStart multi) next) b
  LineEnd multi -> new (SLook (AtLineEnd multi) next) b
  WordBoundary want -> new (SLook (AtWordBoundary want) next) b
  Group Nothing inner -> nfa inner next b
  Group (Just g) inner ->
    let (close, b1) = new (SCapture (2 * g + 1) next) b
        (body, b2) = nfa inner close b1
     in new (SCapture (2 * g) body) b2
  Seq ns -> foldr (\n k nx bb -> let (s, bb') = k nx bb in nfa n s bb') (,) ns next b
  Alt ns ->
    let (starts, b1) = foldr (\n (acc, bb) -> let (s, bb') = nfa n next bb in (s : acc, bb')) ([], b) ns
     in new (SUnion starts) b1
  Repeat lo hi greedy inner -> case hi of
    Just 1
      | lo == 0 ->
          let (x, b1) = nfa inner next b
           in new (SUnion (order x next)) b1
    Just m
      | lo == m -> copies lo next b
      | otherwise ->
          -- the optional copies nest: once one is skipped, the rest are too
          let (opt, b1) = foldr (\_ (nx, bb) -> let (x, bb') = nfa inner nx bb in new (SUnion (order x next)) bb') (next, b) [1 .. m - lo]
           in copies lo opt b1
    Nothing
      | lo == 0 && minLen inner > 0 ->
          let (u, b1) = reserve b
              (x, b2) = nfa inner u b1
           in (u, fill u (SUnion (order x next)) b2)
      | lo == 0 ->
          -- x* where x can match empty is compiled as (x+)?, which keeps
          -- the preference order right (rust-lang/regex#779)
          let (plus, b1) = reserve b
              (x, b2) = nfa inner plus b1
              b3 = fill plus (SUnion (order x next)) b2
           in new (SUnion (order x next)) b3
      | otherwise ->
          let (loop, b1) = reserve b
              (lastCopy, b2) = nfa inner loop b1
              b3 = fill loop (SUnion (order lastCopy next)) b2
           in copies (lo - 1) lastCopy b3
    where
      order x nx = if greedy then [x, nx] else [nx, x]
      copies n nx bb = foldr (\_ (s, bb') -> nfa inner s bb') (nx, bb) [1 .. n]

minLen :: Node -> Int
minLen = \case
  One _ -> 1
  LineStart _ -> 0
  LineEnd _ -> 0
  WordBoundary _ -> 0
  Group _ n -> minLen n
  Seq ns -> sum (map minLen ns)
  Alt ns -> if null ns then 0 else minimum (map minLen ns)
  Repeat lo _ _ n -> lo * minLen n

-- | Rust switches to another engine past its limit. we only ever see version
-- strings, so refusing is fine
visitedLimit :: Int
visitedLimit = 20000000

data Frame = Step !Int !Int | Restore !Int !Int

-- | the visited set lives for the whole search, like Rust's. a (state,
-- position) that failed from one start fails from every later one too
searchFrom :: Regex -> VU.Vector Char -> Int -> Either Text (Maybe (VU.Vector Int))
searchFrom re input from
  | V.length states * width > visitedLimit = Left "text too long for the regex engine"
  | otherwise = Right $ runST $ do
      visited <- MVU.replicate (V.length states * width) False
      slots <- MVU.replicate (progSlots prog) (-1)
      let tryAt at
            | at > len = pure Nothing
            | otherwise =
                run [Step (progStart prog) at] >>= \case
                  Nothing -> tryAt (at + 1)
                  found -> pure found
          run = \case
            [] -> pure Nothing
            Restore slot old : rest -> MVU.write slots slot old >> run rest
            Step sid at : rest -> step sid at rest
          step sid at rest = do
            let key = sid * width + at
            seen <- MVU.read visited key
            if seen
              then run rest
              else do
                MVU.write visited key True
                case states V.! sid of
                  SChar p nx
                    | at < len && p (input VU.! at) -> step nx (at + 1) rest
                    | otherwise -> run rest
                  SUnion [] -> run rest
                  SUnion (x : xs) -> step x at (map (`Step` at) xs <> rest)
                  SCapture slot nx -> do
                    old <- MVU.read slots slot
                    MVU.write slots slot at
                    step nx at (Restore slot old : rest)
                  SLook l nx
                    | look l at -> step nx at rest
                    | otherwise -> run rest
                  SMatch -> Just <$> VU.freeze slots
      tryAt from
  where
    prog = reProg re
    states = progStates prog
    len = VU.length input
    width = len + 1
    look l at = case l of
      AtLineStart multi -> at == 0 || (multi && input VU.! (at - 1) == '\n')
      AtLineEnd multi -> at == len || (multi && input VU.! at == '\n')
      AtWordBoundary want -> (wordAt (at - 1) /= wordAt at) == want
    wordAt i = i >= 0 && i < len && isWord (input VU.! i)

data Match = Match {matchStart, matchEnd :: Int, matchSlots :: VU.Vector Int}

toMatch :: VU.Vector Int -> Match
toMatch slots = Match (slots VU.! 0) (slots VU.! 1) slots

-- | every non-overlapping match, like Rust's captures_iter. an empty match
-- right where the previous one ended is skipped
matches :: Regex -> VU.Vector Char -> Either Text [Match]
matches re input = go 0 Nothing
  where
    go from lastEnd
      | from > VU.length input = Right []
      | otherwise =
          searchFrom re input from >>= \case
            Nothing -> Right []
            Just slots
              | s == e && Just e == lastEnd -> go (s + 1) lastEnd
              | otherwise -> (m :) <$> go (if s == e then e + 1 else e) (Just e)
              where
                m@Match {matchStart = s, matchEnd = e} = toMatch slots

groupsOf :: Regex -> VU.Vector Char -> Match -> [Maybe Text]
groupsOf re input Match {matchSlots = slots} =
  [ if a >= 0 && b >= 0 then Just (T.pack (VU.toList (VU.slice a (b - a) input))) else Nothing
  | g <- [0 .. reGroups re],
    let a = slots VU.! (2 * g)
        b = slots VU.! (2 * g + 1)
  ]

chars :: Text -> VU.Vector Char
chars = VU.fromList . T.unpack

captures :: Regex -> Text -> Either Text (Maybe [Maybe Text])
captures re t = fmap (groupsOf re input . toMatch) <$> searchFrom re input 0
  where
    input = chars t

capturesAll :: Regex -> Text -> Either Text [[Maybe Text]]
capturesAll re t = map (groupsOf re input) <$> matches re input
  where
    input = chars t

-- | Rust's replace_all: $1, ${1}, $name and ${name} expand to groups (empty
-- when missing), $$ is a dollar sign. $name takes the longest run of
-- letters, digits and underscores, so "$1a" is the group named "1a"
replaceAll :: Regex -> Text -> Text -> Either Text Text
replaceAll re rep t = T.concat . go 0 <$> matches re input
  where
    input = chars t
    slice a b = T.pack (VU.toList (VU.slice a (b - a) input))
    go pos [] = [slice pos (VU.length input)]
    go pos (m@Match {matchStart = s, matchEnd = e} : ms) = slice pos s : expand (groupsOf re input m) : go e ms
    expand groups = T.pack (expandS groups (T.unpack rep))
    expandS groups = \case
      [] -> []
      '$' : '$' : rest -> '$' : expandS groups rest
      '$' : '{' : rest
        | (name, '}' : rest') <- span (/= '}') rest, not (null name) -> lookupGroup groups name <> expandS groups rest'
      '$' : rest
        | (name, rest') <- span (\c -> isAlphaNum c || c == '_') rest, not (null name) -> lookupGroup groups name <> expandS groups rest'
      c : rest -> c : expandS groups rest
    lookupGroup groups name =
      let idx = readMaybe name <|> lookup (T.pack name) (reNames re)
       in maybe "" T.unpack (idx >>= \i -> if i < length groups then groups !! i else Nothing)