{- |
Module      : Control.Lens.Grammar.Kleene
Description : Kleene star algebras & regular expressions
Copyright   : (C) 2026 - Eitan Chatav
License     : BSD-style (see the file LICENSE)
Maintainer  : Eitan Chatav <eitan.chatav@gmail.com>
Stability   : provisional
Portability : non-portable

Regular expressions form a Kleene star algebra. See Kleene,
[Representation of Events in Nerve Nets and Finite Automata]
(https://www.rand.org/pubs/research_memoranda/RM704.html)
-}

module Control.Lens.Grammar.Kleene
  ( -- * KleeneStarAlgebra
    KleeneStarAlgebra (..)
  , orK, anyK
    -- * RegEx
  , RegEx (..)
  , RegExam (..)
  , CategoryTest (..)
  ) where

import Control.Applicative
import Control.Lens.Grammar.Symbol
import Control.Lens.Grammar.Token
import Data.Foldable
import Data.MemoTrie
import Data.Monoid
import Data.Profunctor
import Data.Set (Set)
import qualified Data.Set as Set
import GHC.Generics

{- | A `KleeneStarAlgebra` is a ring
with a generally non-commutaive multiplication,
the `Monoid` concatenation operator `<>` with identity `mempty`;
and an idempotent addition, the alternation operator `>|<`
with identity `zeroK`.

It has three unary operators `optK`, `plusK` and the eponymous `starK`.

prop> starK x = optK (plusK x)
prop> plusK x = x <> starK x
prop> optK x = mempty >|< x

-}
class Monoid k => KleeneStarAlgebra k where
  starK, plusK, optK :: k -> k
  starK k
x = k -> k
forall k. KleeneStarAlgebra k => k -> k
optK (k -> k
forall k. KleeneStarAlgebra k => k -> k
plusK k
x)
  plusK k
x = k
x k -> k -> k
forall a. Semigroup a => a -> a -> a
<> k -> k
forall k. KleeneStarAlgebra k => k -> k
starK k
x
  optK k
x = k
forall a. Monoid a => a
mempty k -> k -> k
forall k. KleeneStarAlgebra k => k -> k -> k
>|< k
x
  infixl 3 >|<
  (>|<) :: k -> k -> k
  zeroK :: k
  default (>|<) :: (k ~ f a, Alternative f) => k -> k -> k
  default zeroK :: (k ~ f a, Alternative f) => k
  (>|<) = k -> k -> k
f a -> f a -> f a
forall a. f a -> f a -> f a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
(<|>)
  zeroK = k
f a
forall a. f a
forall (f :: * -> *) a. Alternative f => f a
empty

-- | cumulative alternation
orK :: (Foldable f, KleeneStarAlgebra k) => f k -> k
orK :: forall (f :: * -> *) k.
(Foldable f, KleeneStarAlgebra k) =>
f k -> k
orK = (k -> k -> k) -> k -> f k -> k
forall b a. (b -> a -> b) -> b -> f a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' k -> k -> k
forall k. KleeneStarAlgebra k => k -> k -> k
(>|<) k
forall k. KleeneStarAlgebra k => k
zeroK

-- | universal
anyK :: (Foldable f, KleeneStarAlgebra k) => (a -> k) -> f a -> k
anyK :: forall (f :: * -> *) k a.
(Foldable f, KleeneStarAlgebra k) =>
(a -> k) -> f a -> k
anyK a -> k
f = (k -> a -> k) -> k -> f a -> k
forall b a. (b -> a -> b) -> b -> f a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\k
b a
a -> k
b k -> k -> k
forall k. KleeneStarAlgebra k => k -> k -> k
>|< a -> k
f a
a) k
forall k. KleeneStarAlgebra k => k
zeroK

-- | The `RegEx`pression type is the prototypical `KleeneStarAlgebra`.
data RegEx token
  = Terminal [token]
  | NonTerminal String
  | Sequence (RegEx token) (RegEx token)
  | KleeneStar (RegEx token)
  | KleeneOpt (RegEx token)
  | KleenePlus (RegEx token)
  | RegExam (RegExam token (RegEx token))

{- | A component of both `RegEx`pressions
and `Control.Lens.Grammar.Boole.TokenTest`s, so that the latter can
be embedded in the former with `Control.Lens.Grammar.Boole.tokenClass`.
-}
data RegExam token alg
  = Fail
  | Pass
  | OneOf (Set token)
  | NotOneOf (Set token) (CategoryTest token)
  | Alternate alg alg

{- | `CategoryTest`s for `Categorized` tokens.-}
data CategoryTest token
  = AsIn (Categorize token)
  | NotAsIn (Set (Categorize token))

--instances
instance (Alternative f, Monoid k) => KleeneStarAlgebra (Ap f k)
deriving stock instance Generic (RegEx token)
deriving stock instance Generic (RegExam token alg)
deriving stock instance Generic1 (RegExam token)
deriving stock instance Generic (CategoryTest token)
deriving stock instance Categorized token => Eq (RegEx token)
deriving stock instance Categorized token => Ord (RegEx token)
deriving stock instance
  (Categorized token, Read token, Read (Categorize token))
    => Read (RegEx token)
deriving stock instance
  (Categorized token, Show token, Show (Categorize token))
    => Show (RegEx token)
instance TerminalSymbol token (RegEx token) where
  terminal :: [token] -> RegEx token
terminal = [token] -> RegEx token
forall token. [token] -> RegEx token
Terminal ([token] -> RegEx token)
-> ([token] -> [token]) -> [token] -> RegEx token
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [token] -> [token]
forall a. [a] -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList
instance NonTerminalSymbol (RegEx token) where
  nonTerminal :: String -> RegEx token
nonTerminal = String -> RegEx token
forall token. String -> RegEx token
NonTerminal
instance Categorized token => Tokenized token (RegEx token) where
  anyToken :: RegEx token
anyToken = RegExam token (RegEx token) -> RegEx token
forall token. RegExam token (RegEx token) -> RegEx token
RegExam RegExam token (RegEx token)
forall token alg. RegExam token alg
Pass
  token :: token -> RegEx token
token token
a = [token] -> RegEx token
forall token. [token] -> RegEx token
Terminal [token
a]
  oneOf :: forall (f :: * -> *). Foldable f => f token -> RegEx token
oneOf f token
as | f token -> Bool
forall a. f a -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null f token
as = RegExam token (RegEx token) -> RegEx token
forall token. RegExam token (RegEx token) -> RegEx token
RegExam RegExam token (RegEx token)
forall token alg. RegExam token alg
Fail
  oneOf f token
as | f token -> Int
forall a. f a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length f token
as Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1 = [token] -> RegEx token
forall token. [token] -> RegEx token
Terminal (f token -> [token]
forall a. f a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList f token
as)
  oneOf f token
as = RegExam token (RegEx token) -> RegEx token
forall token. RegExam token (RegEx token) -> RegEx token
RegExam (Set token -> RegExam token (RegEx token)
forall token alg. Set token -> RegExam token alg
OneOf ((token -> Set token -> Set token)
-> Set token -> f token -> Set token
forall a b. (a -> b -> b) -> b -> f a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr token -> Set token -> Set token
forall a. Ord a => a -> Set a -> Set a
Set.insert Set token
forall a. Set a
Set.empty f token
as))
  notOneOf :: forall (f :: * -> *). Foldable f => f token -> RegEx token
notOneOf f token
as | f token -> Bool
forall a. f a -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null f token
as = RegExam token (RegEx token) -> RegEx token
forall token. RegExam token (RegEx token) -> RegEx token
RegExam RegExam token (RegEx token)
forall token alg. RegExam token alg
Pass
  notOneOf f token
as = RegExam token (RegEx token) -> RegEx token
forall token. RegExam token (RegEx token) -> RegEx token
RegExam
    (Set token -> CategoryTest token -> RegExam token (RegEx token)
forall token alg.
Set token -> CategoryTest token -> RegExam token alg
NotOneOf ((token -> Set token -> Set token)
-> Set token -> f token -> Set token
forall a b. (a -> b -> b) -> b -> f a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr token -> Set token -> Set token
forall a. Ord a => a -> Set a -> Set a
Set.insert Set token
forall a. Set a
Set.empty f token
as) (Set (Categorize token) -> CategoryTest token
forall token. Set (Categorize token) -> CategoryTest token
NotAsIn Set (Categorize token)
forall a. Set a
Set.empty))
  asIn :: Categorize token -> RegEx token
asIn Categorize token
cat = RegExam token (RegEx token) -> RegEx token
forall token. RegExam token (RegEx token) -> RegEx token
RegExam (Set token -> CategoryTest token -> RegExam token (RegEx token)
forall token alg.
Set token -> CategoryTest token -> RegExam token alg
NotOneOf Set token
forall a. Set a
Set.empty (Categorize token -> CategoryTest token
forall token. Categorize token -> CategoryTest token
AsIn Categorize token
cat))
  notAsIn :: Categorize token -> RegEx token
notAsIn Categorize token
cat = RegExam token (RegEx token) -> RegEx token
forall token. RegExam token (RegEx token) -> RegEx token
RegExam
    (Set token -> CategoryTest token -> RegExam token (RegEx token)
forall token alg.
Set token -> CategoryTest token -> RegExam token alg
NotOneOf Set token
forall a. Set a
Set.empty (Set (Categorize token) -> CategoryTest token
forall token. Set (Categorize token) -> CategoryTest token
NotAsIn (Categorize token -> Set (Categorize token)
forall a. a -> Set a
Set.singleton Categorize token
cat)))
instance Categorized token => Semigroup (RegEx token) where
  Terminal [] <> :: RegEx token -> RegEx token -> RegEx token
<> RegEx token
rex = RegEx token
rex
  RegEx token
rex <> Terminal [] = RegEx token
rex
  RegExam RegExam token (RegEx token)
Fail <> RegEx token
_ = RegEx token
forall k. KleeneStarAlgebra k => k
zeroK
  RegEx token
_ <> RegExam RegExam token (RegEx token)
Fail = RegEx token
forall k. KleeneStarAlgebra k => k
zeroK
  Terminal [token]
str0 <> Terminal [token]
str1 = [token] -> RegEx token
forall token. [token] -> RegEx token
Terminal ([token]
str0 [token] -> [token] -> [token]
forall a. Semigroup a => a -> a -> a
<> [token]
str1)
  KleeneStar RegEx token
rex0 <> RegEx token
rex1
    | RegEx token
rex0 RegEx token -> RegEx token -> Bool
forall a. Eq a => a -> a -> Bool
== RegEx token
rex1 = RegEx token -> RegEx token
forall k. KleeneStarAlgebra k => k -> k
plusK RegEx token
rex0
  RegEx token
rex0 <> KleeneStar RegEx token
rex1
    | RegEx token
rex0 RegEx token -> RegEx token -> Bool
forall a. Eq a => a -> a -> Bool
== RegEx token
rex1 = RegEx token -> RegEx token
forall k. KleeneStarAlgebra k => k -> k
plusK RegEx token
rex1
  RegEx token
rex0 <> RegEx token
rex1 = RegEx token -> RegEx token -> RegEx token
forall token. RegEx token -> RegEx token -> RegEx token
Sequence RegEx token
rex0 RegEx token
rex1
instance Categorized token => Monoid (RegEx token) where
  mempty :: RegEx token
mempty = [token] -> RegEx token
forall token. [token] -> RegEx token
Terminal []
instance Categorized token => KleeneStarAlgebra (RegEx token) where
  zeroK :: RegEx token
zeroK = RegExam token (RegEx token) -> RegEx token
forall token. RegExam token (RegEx token) -> RegEx token
RegExam RegExam token (RegEx token)
forall token alg. RegExam token alg
Fail
  optK :: RegEx token -> RegEx token
optK (RegExam RegExam token (RegEx token)
Fail) = RegEx token
forall a. Monoid a => a
mempty
  optK (Terminal []) = RegEx token
forall a. Monoid a => a
mempty
  optK (KleenePlus RegEx token
rex) = RegEx token -> RegEx token
forall k. KleeneStarAlgebra k => k -> k
starK RegEx token
rex
  optK RegEx token
rex = RegEx token -> RegEx token
forall token. RegEx token -> RegEx token
KleeneOpt RegEx token
rex
  starK :: RegEx token -> RegEx token
starK (RegExam RegExam token (RegEx token)
Fail) = RegEx token
forall a. Monoid a => a
mempty
  starK (Terminal []) = RegEx token
forall a. Monoid a => a
mempty
  starK RegEx token
rex = RegEx token -> RegEx token
forall token. RegEx token -> RegEx token
KleeneStar RegEx token
rex
  plusK :: RegEx token -> RegEx token
plusK (RegExam RegExam token (RegEx token)
Fail) = RegEx token
forall k. KleeneStarAlgebra k => k
zeroK
  plusK (Terminal []) = RegEx token
forall a. Monoid a => a
mempty
  plusK RegEx token
rex = RegEx token -> RegEx token
forall token. RegEx token -> RegEx token
KleenePlus RegEx token
rex
  KleenePlus RegEx token
rex >|< :: RegEx token -> RegEx token -> RegEx token
>|< Terminal [] = RegEx token -> RegEx token
forall k. KleeneStarAlgebra k => k -> k
starK RegEx token
rex
  Terminal [] >|< KleenePlus RegEx token
rex = RegEx token -> RegEx token
forall k. KleeneStarAlgebra k => k -> k
starK RegEx token
rex
  RegEx token
rex >|< Terminal [] = RegEx token -> RegEx token
forall k. KleeneStarAlgebra k => k -> k
optK RegEx token
rex
  Terminal [] >|< RegEx token
rex = RegEx token -> RegEx token
forall k. KleeneStarAlgebra k => k -> k
optK RegEx token
rex
  RegEx token
rex >|< RegExam RegExam token (RegEx token)
Fail = RegEx token
rex
  RegExam RegExam token (RegEx token)
Fail >|< RegEx token
rex = RegEx token
rex
  RegEx token
rex0 >|< RegEx token
rex1 | RegEx token
rex0 RegEx token -> RegEx token -> Bool
forall a. Eq a => a -> a -> Bool
== RegEx token
rex1 = RegEx token
rex0
  RegEx token
rex0 >|< RegEx token
rex1 = RegExam token (RegEx token) -> RegEx token
forall token. RegExam token (RegEx token) -> RegEx token
RegExam (RegEx token -> RegEx token -> RegExam token (RegEx token)
forall token alg. alg -> alg -> RegExam token alg
Alternate RegEx token
rex0 RegEx token
rex1)
instance Categorized token
  => Tokenized token (RegExam token alg) where
  anyToken :: RegExam token alg
anyToken = RegExam token alg
forall token alg. RegExam token alg
Pass
  token :: token -> RegExam token alg
token token
a = Set token -> RegExam token alg
forall token alg. Set token -> RegExam token alg
OneOf (token -> Set token
forall a. a -> Set a
Set.singleton token
a)
  oneOf :: forall (f :: * -> *). Foldable f => f token -> RegExam token alg
oneOf f token
as | f token -> Bool
forall a. f a -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null f token
as = RegExam token alg
forall token alg. RegExam token alg
Fail
  oneOf f token
as = Set token -> RegExam token alg
forall token alg. Set token -> RegExam token alg
OneOf ([token] -> Set token
forall a. Ord a => [a] -> Set a
Set.fromList (f token -> [token]
forall a. f a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList f token
as))
  notOneOf :: forall (f :: * -> *). Foldable f => f token -> RegExam token alg
notOneOf f token
as | f token -> Bool
forall a. f a -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null f token
as = RegExam token alg
forall token alg. RegExam token alg
Pass
  notOneOf f token
as =
    Set token -> CategoryTest token -> RegExam token alg
forall token alg.
Set token -> CategoryTest token -> RegExam token alg
NotOneOf ([token] -> Set token
forall a. Ord a => [a] -> Set a
Set.fromList (f token -> [token]
forall a. f a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList f token
as)) (Set (Categorize token) -> CategoryTest token
forall token. Set (Categorize token) -> CategoryTest token
NotAsIn Set (Categorize token)
forall a. Set a
Set.empty)
  asIn :: Categorize token -> RegExam token alg
asIn Categorize token
cat = Set token -> CategoryTest token -> RegExam token alg
forall token alg.
Set token -> CategoryTest token -> RegExam token alg
NotOneOf Set token
forall a. Set a
Set.empty (Categorize token -> CategoryTest token
forall token. Categorize token -> CategoryTest token
AsIn Categorize token
cat)
  notAsIn :: Categorize token -> RegExam token alg
notAsIn Categorize token
cat =
    Set token -> CategoryTest token -> RegExam token alg
forall token alg.
Set token -> CategoryTest token -> RegExam token alg
NotOneOf Set token
forall a. Set a
Set.empty (Set (Categorize token) -> CategoryTest token
forall token. Set (Categorize token) -> CategoryTest token
NotAsIn (Categorize token -> Set (Categorize token)
forall a. a -> Set a
Set.singleton Categorize token
cat))
deriving stock instance
  (Categorized token, Read token, Read alg, Read (Categorize token))
    => Read (RegExam token alg)
deriving stock instance
  (Categorized token, Show token, Show alg, Show (Categorize token))
    => Show (RegExam token alg)
deriving stock instance Functor (RegExam token)
deriving stock instance Foldable (RegExam token)
deriving stock instance Traversable (RegExam token)
deriving stock instance (Categorized token, Eq alg)
  => Eq (RegExam token alg)
deriving stock instance (Categorized token, Ord alg)
  => Ord (RegExam token alg)
deriving stock instance Categorized token => Eq (CategoryTest token)
deriving stock instance Categorized token => Ord (CategoryTest token)
deriving stock instance
  (Categorized token, Read token, Read (Categorize token))
    => Read (CategoryTest token)
deriving stock instance
  (Categorized token, Show token, Show (Categorize token))
    => Show (CategoryTest token)
instance (Categorized token, HasTrie token)
  => HasTrie (RegEx token) where
    data (RegEx token :->: b) = RegExTrie
      { forall token b. (RegEx token :->: b) -> [token] :->: b
terminalTrie :: [token] :->: b
      , forall token b. (RegEx token :->: b) -> String :->: b
nonTerminalTrie :: String :->: b
      , forall token b.
(RegEx token :->: b) -> (RegEx token, RegEx token) :->: b
sequenceTrie :: (RegEx token, RegEx token) :->: b
      , forall token b.
(RegEx token :->: b) -> (RegEx token, RegEx token) :->: b
alternateTrie :: (RegEx token, RegEx token) :->: b
      , forall token b. (RegEx token :->: b) -> RegEx token :->: b
kleeneStarTrie :: RegEx token :->: b
      , forall token b. (RegEx token :->: b) -> RegEx token :->: b
kleeneOptTrie :: RegEx token :->: b
      , forall token b. (RegEx token :->: b) -> RegEx token :->: b
kleenePlusTrie :: RegEx token :->: b
      , forall token b. (RegEx token :->: b) -> b
failTrie :: b
      , forall token b. (RegEx token :->: b) -> b
passTrie :: b
      , forall token b. (RegEx token :->: b) -> [token] :->: b
oneOfTrie :: [token] :->: b
      , forall token b.
(RegEx token :->: b) -> ([token], Either Int [Int]) :->: b
notOneOfTrie :: ([token], Either Int [Int]) :->: b
      }
    trie :: forall b. (RegEx token -> b) -> RegEx token :->: b
trie RegEx token -> b
f = RegExTrie
      { terminalTrie :: [token] :->: b
terminalTrie = ([token] -> b) -> [token] :->: b
forall a b. HasTrie a => (a -> b) -> a :->: b
forall b. ([token] -> b) -> [token] :->: b
trie (RegEx token -> b
f (RegEx token -> b) -> ([token] -> RegEx token) -> [token] -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [token] -> RegEx token
forall token s. TerminalSymbol token s => [token] -> s
terminal)
      , nonTerminalTrie :: String :->: b
nonTerminalTrie = (String -> b) -> String :->: b
forall a b. HasTrie a => (a -> b) -> a :->: b
forall b. (String -> b) -> String :->: b
trie (RegEx token -> b
f (RegEx token -> b) -> (String -> RegEx token) -> String -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> RegEx token
forall s. NonTerminalSymbol s => String -> s
nonTerminal)
      , sequenceTrie :: (RegEx token, RegEx token) :->: b
sequenceTrie = ((RegEx token, RegEx token) -> b)
-> (RegEx token, RegEx token) :->: b
forall a b. HasTrie a => (a -> b) -> a :->: b
forall b.
((RegEx token, RegEx token) -> b)
-> (RegEx token, RegEx token) :->: b
trie (RegEx token -> b
f (RegEx token -> b)
-> ((RegEx token, RegEx token) -> RegEx token)
-> (RegEx token, RegEx token)
-> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (RegEx token -> RegEx token -> RegEx token)
-> (RegEx token, RegEx token) -> RegEx token
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry RegEx token -> RegEx token -> RegEx token
forall a. Semigroup a => a -> a -> a
(<>))
      , alternateTrie :: (RegEx token, RegEx token) :->: b
alternateTrie = ((RegEx token, RegEx token) -> b)
-> (RegEx token, RegEx token) :->: b
forall a b. HasTrie a => (a -> b) -> a :->: b
forall b.
((RegEx token, RegEx token) -> b)
-> (RegEx token, RegEx token) :->: b
trie (RegEx token -> b
f (RegEx token -> b)
-> ((RegEx token, RegEx token) -> RegEx token)
-> (RegEx token, RegEx token)
-> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (RegEx token -> RegEx token -> RegEx token)
-> (RegEx token, RegEx token) -> RegEx token
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry RegEx token -> RegEx token -> RegEx token
forall k. KleeneStarAlgebra k => k -> k -> k
(>|<))
      , kleeneStarTrie :: RegEx token :->: b
kleeneStarTrie = (RegEx token -> b) -> RegEx token :->: b
forall a b. HasTrie a => (a -> b) -> a :->: b
forall b. (RegEx token -> b) -> RegEx token :->: b
trie (RegEx token -> b
f (RegEx token -> b)
-> (RegEx token -> RegEx token) -> RegEx token -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RegEx token -> RegEx token
forall k. KleeneStarAlgebra k => k -> k
starK)
      , kleeneOptTrie :: RegEx token :->: b
kleeneOptTrie = (RegEx token -> b) -> RegEx token :->: b
forall a b. HasTrie a => (a -> b) -> a :->: b
forall b. (RegEx token -> b) -> RegEx token :->: b
trie (RegEx token -> b
f (RegEx token -> b)
-> (RegEx token -> RegEx token) -> RegEx token -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RegEx token -> RegEx token
forall k. KleeneStarAlgebra k => k -> k
optK)
      , kleenePlusTrie :: RegEx token :->: b
kleenePlusTrie = (RegEx token -> b) -> RegEx token :->: b
forall a b. HasTrie a => (a -> b) -> a :->: b
forall b. (RegEx token -> b) -> RegEx token :->: b
trie (RegEx token -> b
f (RegEx token -> b)
-> (RegEx token -> RegEx token) -> RegEx token -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RegEx token -> RegEx token
forall k. KleeneStarAlgebra k => k -> k
plusK)
      , failTrie :: b
failTrie = RegEx token -> b
f RegEx token
forall k. KleeneStarAlgebra k => k
zeroK
      , passTrie :: b
passTrie = RegEx token -> b
f RegEx token
forall token p. Tokenized token p => p
anyToken
      , oneOfTrie :: [token] :->: b
oneOfTrie = ([token] -> b) -> [token] :->: b
forall a b. HasTrie a => (a -> b) -> a :->: b
forall b. ([token] -> b) -> [token] :->: b
trie (RegEx token -> b
f (RegEx token -> b) -> ([token] -> RegEx token) -> [token] -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [token] -> RegEx token
forall token p (f :: * -> *).
(Tokenized token p, Foldable f) =>
f token -> p
forall (f :: * -> *). Foldable f => f token -> RegEx token
oneOf)
      , notOneOfTrie :: ([token], Either Int [Int]) :->: b
notOneOfTrie = (([token], Either Int [Int]) -> b)
-> ([token], Either Int [Int]) :->: b
forall a b. HasTrie a => (a -> b) -> a :->: b
forall b.
(([token], Either Int [Int]) -> b)
-> ([token], Either Int [Int]) :->: b
trie (RegEx token -> b
f (RegEx token -> b)
-> (([token], Either Int [Int]) -> RegEx token)
-> ([token], Either Int [Int])
-> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([token], Either Int [Int]) -> RegEx token
forall token.
Categorized token =>
([token], Either Int [Int]) -> RegEx token
testNotOneOf)
      }
    untrie :: forall b. (RegEx token :->: b) -> RegEx token -> b
untrie RegEx token :->: b
rex = \case
      Terminal [token]
word -> ([token] :->: b) -> [token] -> b
forall a b. HasTrie a => (a :->: b) -> a -> b
forall b. ([token] :->: b) -> [token] -> b
untrie ((RegEx token :->: b) -> [token] :->: b
forall token b. (RegEx token :->: b) -> [token] :->: b
terminalTrie RegEx token :->: b
rex) [token]
word
      NonTerminal String
name -> (String :->: b) -> String -> b
forall a b. HasTrie a => (a :->: b) -> a -> b
forall b. (String :->: b) -> String -> b
untrie ((RegEx token :->: b) -> String :->: b
forall token b. (RegEx token :->: b) -> String :->: b
nonTerminalTrie RegEx token :->: b
rex) String
name
      Sequence RegEx token
x1 RegEx token
x2 -> ((RegEx token, RegEx token) :->: b)
-> (RegEx token, RegEx token) -> b
forall a b. HasTrie a => (a :->: b) -> a -> b
forall b.
((RegEx token, RegEx token) :->: b)
-> (RegEx token, RegEx token) -> b
untrie ((RegEx token :->: b) -> (RegEx token, RegEx token) :->: b
forall token b.
(RegEx token :->: b) -> (RegEx token, RegEx token) :->: b
sequenceTrie RegEx token :->: b
rex) (RegEx token
x1,RegEx token
x2)
      KleeneStar RegEx token
x -> (RegEx token :->: b) -> RegEx token -> b
forall a b. HasTrie a => (a :->: b) -> a -> b
forall b. (RegEx token :->: b) -> RegEx token -> b
untrie ((RegEx token :->: b) -> RegEx token :->: b
forall token b. (RegEx token :->: b) -> RegEx token :->: b
kleeneStarTrie RegEx token :->: b
rex) RegEx token
x
      KleenePlus RegEx token
x -> (RegEx token :->: b) -> RegEx token -> b
forall a b. HasTrie a => (a :->: b) -> a -> b
forall b. (RegEx token :->: b) -> RegEx token -> b
untrie ((RegEx token :->: b) -> RegEx token :->: b
forall token b. (RegEx token :->: b) -> RegEx token :->: b
kleenePlusTrie RegEx token :->: b
rex) RegEx token
x
      KleeneOpt RegEx token
x -> (RegEx token :->: b) -> RegEx token -> b
forall a b. HasTrie a => (a :->: b) -> a -> b
forall b. (RegEx token :->: b) -> RegEx token -> b
untrie ((RegEx token :->: b) -> RegEx token :->: b
forall token b. (RegEx token :->: b) -> RegEx token :->: b
kleeneOptTrie RegEx token :->: b
rex) RegEx token
x
      RegExam RegExam token (RegEx token)
Fail -> (RegEx token :->: b) -> b
forall token b. (RegEx token :->: b) -> b
failTrie RegEx token :->: b
rex
      RegExam RegExam token (RegEx token)
Pass -> (RegEx token :->: b) -> b
forall token b. (RegEx token :->: b) -> b
passTrie RegEx token :->: b
rex
      RegExam (OneOf Set token
chars) -> ([token] :->: b) -> [token] -> b
forall a b. HasTrie a => (a :->: b) -> a -> b
forall b. ([token] :->: b) -> [token] -> b
untrie ((RegEx token :->: b) -> [token] :->: b
forall token b. (RegEx token :->: b) -> [token] :->: b
oneOfTrie RegEx token :->: b
rex) (Set token -> [token]
forall a. Set a -> [a]
Set.toList Set token
chars)
      RegExam (NotOneOf Set token
chars (AsIn Categorize token
cat)) ->
        (([token], Either Int [Int]) :->: b)
-> ([token], Either Int [Int]) -> b
forall a b. HasTrie a => (a :->: b) -> a -> b
forall b.
(([token], Either Int [Int]) :->: b)
-> ([token], Either Int [Int]) -> b
untrie ((RegEx token :->: b) -> ([token], Either Int [Int]) :->: b
forall token b.
(RegEx token :->: b) -> ([token], Either Int [Int]) :->: b
notOneOfTrie RegEx token :->: b
rex) (Set token -> [token]
forall a. Set a -> [a]
Set.toList Set token
chars, Int -> Either Int [Int]
forall a b. a -> Either a b
Left (Categorize token -> Int
forall a. Enum a => a -> Int
fromEnum Categorize token
cat))
      RegExam (NotOneOf Set token
chars (NotAsIn Set (Categorize token)
cats)) ->
        (([token], Either Int [Int]) :->: b)
-> ([token], Either Int [Int]) -> b
forall a b. HasTrie a => (a :->: b) -> a -> b
forall b.
(([token], Either Int [Int]) :->: b)
-> ([token], Either Int [Int]) -> b
untrie ((RegEx token :->: b) -> ([token], Either Int [Int]) :->: b
forall token b.
(RegEx token :->: b) -> ([token], Either Int [Int]) :->: b
notOneOfTrie RegEx token :->: b
rex)
          (Set token -> [token]
forall a. Set a -> [a]
Set.toList Set token
chars, [Int] -> Either Int [Int]
forall a b. b -> Either a b
Right (Set Int -> [Int]
forall a. Set a -> [a]
Set.toList ((Categorize token -> Int) -> Set (Categorize token) -> Set Int
forall b a. Ord b => (a -> b) -> Set a -> Set b
Set.map Categorize token -> Int
forall a. Enum a => a -> Int
fromEnum Set (Categorize token)
cats)))
      RegExam (Alternate RegEx token
x1 RegEx token
x2) -> ((RegEx token, RegEx token) :->: b)
-> (RegEx token, RegEx token) -> b
forall a b. HasTrie a => (a :->: b) -> a -> b
forall b.
((RegEx token, RegEx token) :->: b)
-> (RegEx token, RegEx token) -> b
untrie ((RegEx token :->: b) -> (RegEx token, RegEx token) :->: b
forall token b.
(RegEx token :->: b) -> (RegEx token, RegEx token) :->: b
alternateTrie RegEx token :->: b
rex) (RegEx token
x1,RegEx token
x2)
    enumerate :: forall b. (RegEx token :->: b) -> [(RegEx token, b)]
enumerate RegEx token :->: b
rex = [[(RegEx token, b)]] -> [(RegEx token, b)]
forall a. Monoid a => [a] -> a
mconcat
      [ ([token] -> RegEx token) -> ([token], b) -> (RegEx token, b)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Strong p =>
p a b -> p (a, c) (b, c)
first' [token] -> RegEx token
forall token. [token] -> RegEx token
Terminal (([token], b) -> (RegEx token, b))
-> [([token], b)] -> [(RegEx token, b)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ([token] :->: b) -> [([token], b)]
forall a b. HasTrie a => (a :->: b) -> [(a, b)]
forall b. ([token] :->: b) -> [([token], b)]
enumerate ((RegEx token :->: b) -> [token] :->: b
forall token b. (RegEx token :->: b) -> [token] :->: b
terminalTrie RegEx token :->: b
rex)
      , (String -> RegEx token) -> (String, b) -> (RegEx token, b)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Strong p =>
p a b -> p (a, c) (b, c)
first' String -> RegEx token
forall token. String -> RegEx token
NonTerminal ((String, b) -> (RegEx token, b))
-> [(String, b)] -> [(RegEx token, b)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (String :->: b) -> [(String, b)]
forall a b. HasTrie a => (a :->: b) -> [(a, b)]
forall b. (String :->: b) -> [(String, b)]
enumerate ((RegEx token :->: b) -> String :->: b
forall token b. (RegEx token :->: b) -> String :->: b
nonTerminalTrie RegEx token :->: b
rex)
      , ((RegEx token, RegEx token) -> RegEx token)
-> ((RegEx token, RegEx token), b) -> (RegEx token, b)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Strong p =>
p a b -> p (a, c) (b, c)
first' ((RegEx token -> RegEx token -> RegEx token)
-> (RegEx token, RegEx token) -> RegEx token
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry RegEx token -> RegEx token -> RegEx token
forall token. RegEx token -> RegEx token -> RegEx token
Sequence) (((RegEx token, RegEx token), b) -> (RegEx token, b))
-> [((RegEx token, RegEx token), b)] -> [(RegEx token, b)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ((RegEx token, RegEx token) :->: b)
-> [((RegEx token, RegEx token), b)]
forall a b. HasTrie a => (a :->: b) -> [(a, b)]
forall b.
((RegEx token, RegEx token) :->: b)
-> [((RegEx token, RegEx token), b)]
enumerate ((RegEx token :->: b) -> (RegEx token, RegEx token) :->: b
forall token b.
(RegEx token :->: b) -> (RegEx token, RegEx token) :->: b
sequenceTrie RegEx token :->: b
rex)
      , ((RegEx token, RegEx token) -> RegEx token)
-> ((RegEx token, RegEx token), b) -> (RegEx token, b)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Strong p =>
p a b -> p (a, c) (b, c)
first' (RegExam token (RegEx token) -> RegEx token
forall token. RegExam token (RegEx token) -> RegEx token
RegExam (RegExam token (RegEx token) -> RegEx token)
-> ((RegEx token, RegEx token) -> RegExam token (RegEx token))
-> (RegEx token, RegEx token)
-> RegEx token
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (RegEx token -> RegEx token -> RegExam token (RegEx token))
-> (RegEx token, RegEx token) -> RegExam token (RegEx token)
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry RegEx token -> RegEx token -> RegExam token (RegEx token)
forall token alg. alg -> alg -> RegExam token alg
Alternate) (((RegEx token, RegEx token), b) -> (RegEx token, b))
-> [((RegEx token, RegEx token), b)] -> [(RegEx token, b)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ((RegEx token, RegEx token) :->: b)
-> [((RegEx token, RegEx token), b)]
forall a b. HasTrie a => (a :->: b) -> [(a, b)]
forall b.
((RegEx token, RegEx token) :->: b)
-> [((RegEx token, RegEx token), b)]
enumerate ((RegEx token :->: b) -> (RegEx token, RegEx token) :->: b
forall token b.
(RegEx token :->: b) -> (RegEx token, RegEx token) :->: b
alternateTrie RegEx token :->: b
rex)
      , (RegEx token -> RegEx token)
-> (RegEx token, b) -> (RegEx token, b)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Strong p =>
p a b -> p (a, c) (b, c)
first' RegEx token -> RegEx token
forall token. RegEx token -> RegEx token
KleeneStar ((RegEx token, b) -> (RegEx token, b))
-> [(RegEx token, b)] -> [(RegEx token, b)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (RegEx token :->: b) -> [(RegEx token, b)]
forall a b. HasTrie a => (a :->: b) -> [(a, b)]
forall b. (RegEx token :->: b) -> [(RegEx token, b)]
enumerate ((RegEx token :->: b) -> RegEx token :->: b
forall token b. (RegEx token :->: b) -> RegEx token :->: b
kleeneStarTrie RegEx token :->: b
rex)
      , (RegEx token -> RegEx token)
-> (RegEx token, b) -> (RegEx token, b)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Strong p =>
p a b -> p (a, c) (b, c)
first' RegEx token -> RegEx token
forall token. RegEx token -> RegEx token
KleeneOpt ((RegEx token, b) -> (RegEx token, b))
-> [(RegEx token, b)] -> [(RegEx token, b)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (RegEx token :->: b) -> [(RegEx token, b)]
forall a b. HasTrie a => (a :->: b) -> [(a, b)]
forall b. (RegEx token :->: b) -> [(RegEx token, b)]
enumerate ((RegEx token :->: b) -> RegEx token :->: b
forall token b. (RegEx token :->: b) -> RegEx token :->: b
kleeneOptTrie RegEx token :->: b
rex)
      , (RegEx token -> RegEx token)
-> (RegEx token, b) -> (RegEx token, b)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Strong p =>
p a b -> p (a, c) (b, c)
first' RegEx token -> RegEx token
forall token. RegEx token -> RegEx token
KleenePlus ((RegEx token, b) -> (RegEx token, b))
-> [(RegEx token, b)] -> [(RegEx token, b)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (RegEx token :->: b) -> [(RegEx token, b)]
forall a b. HasTrie a => (a :->: b) -> [(a, b)]
forall b. (RegEx token :->: b) -> [(RegEx token, b)]
enumerate ((RegEx token :->: b) -> RegEx token :->: b
forall token b. (RegEx token :->: b) -> RegEx token :->: b
kleenePlusTrie RegEx token :->: b
rex)
      , [(RegExam token (RegEx token) -> RegEx token
forall token. RegExam token (RegEx token) -> RegEx token
RegExam RegExam token (RegEx token)
forall token alg. RegExam token alg
Fail, (RegEx token :->: b) -> b
forall token b. (RegEx token :->: b) -> b
failTrie RegEx token :->: b
rex)]
      , [(RegExam token (RegEx token) -> RegEx token
forall token. RegExam token (RegEx token) -> RegEx token
RegExam RegExam token (RegEx token)
forall token alg. RegExam token alg
Pass, (RegEx token :->: b) -> b
forall token b. (RegEx token :->: b) -> b
passTrie RegEx token :->: b
rex)]
      , ([token] -> RegEx token) -> ([token], b) -> (RegEx token, b)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Strong p =>
p a b -> p (a, c) (b, c)
first' (RegExam token (RegEx token) -> RegEx token
forall token. RegExam token (RegEx token) -> RegEx token
RegExam (RegExam token (RegEx token) -> RegEx token)
-> ([token] -> RegExam token (RegEx token))
-> [token]
-> RegEx token
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Set token -> RegExam token (RegEx token)
forall token alg. Set token -> RegExam token alg
OneOf (Set token -> RegExam token (RegEx token))
-> ([token] -> Set token) -> [token] -> RegExam token (RegEx token)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [token] -> Set token
forall a. Ord a => [a] -> Set a
Set.fromList) (([token], b) -> (RegEx token, b))
-> [([token], b)] -> [(RegEx token, b)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ([token] :->: b) -> [([token], b)]
forall a b. HasTrie a => (a :->: b) -> [(a, b)]
forall b. ([token] :->: b) -> [([token], b)]
enumerate ((RegEx token :->: b) -> [token] :->: b
forall token b. (RegEx token :->: b) -> [token] :->: b
oneOfTrie RegEx token :->: b
rex)
      , (([token], Either Int [Int]) -> RegEx token)
-> (([token], Either Int [Int]), b) -> (RegEx token, b)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Strong p =>
p a b -> p (a, c) (b, c)
first' ([token], Either Int [Int]) -> RegEx token
forall token.
Categorized token =>
([token], Either Int [Int]) -> RegEx token
testNotOneOf ((([token], Either Int [Int]), b) -> (RegEx token, b))
-> [(([token], Either Int [Int]), b)] -> [(RegEx token, b)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (([token], Either Int [Int]) :->: b)
-> [(([token], Either Int [Int]), b)]
forall a b. HasTrie a => (a :->: b) -> [(a, b)]
forall b.
(([token], Either Int [Int]) :->: b)
-> [(([token], Either Int [Int]), b)]
enumerate ((RegEx token :->: b) -> ([token], Either Int [Int]) :->: b
forall token b.
(RegEx token :->: b) -> ([token], Either Int [Int]) :->: b
notOneOfTrie RegEx token :->: b
rex)
      ]
testNotOneOf
  :: Categorized token
  => ([token], Either Int [Int]) -> RegEx token
testNotOneOf :: forall token.
Categorized token =>
([token], Either Int [Int]) -> RegEx token
testNotOneOf ([token]
chars, Either Int [Int]
catTest) = RegExam token (RegEx token) -> RegEx token
forall token. RegExam token (RegEx token) -> RegEx token
RegExam (RegExam token (RegEx token) -> RegEx token)
-> RegExam token (RegEx token) -> RegEx token
forall a b. (a -> b) -> a -> b
$
  Set token -> CategoryTest token -> RegExam token (RegEx token)
forall token alg.
Set token -> CategoryTest token -> RegExam token alg
NotOneOf ([token] -> Set token
forall a. Ord a => [a] -> Set a
Set.fromList [token]
chars) ((Int -> CategoryTest token)
-> ([Int] -> CategoryTest token)
-> Either Int [Int]
-> CategoryTest token
forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
either (Categorize token -> CategoryTest token
forall token. Categorize token -> CategoryTest token
AsIn (Categorize token -> CategoryTest token)
-> (Int -> Categorize token) -> Int -> CategoryTest token
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Categorize token
forall a. Enum a => Int -> a
toEnum) (Set (Categorize token) -> CategoryTest token
forall token. Set (Categorize token) -> CategoryTest token
NotAsIn (Set (Categorize token) -> CategoryTest token)
-> ([Int] -> Set (Categorize token)) -> [Int] -> CategoryTest token
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> Categorize token) -> Set Int -> Set (Categorize token)
forall b a. Ord b => (a -> b) -> Set a -> Set b
Set.map Int -> Categorize token
forall a. Enum a => Int -> a
toEnum (Set Int -> Set (Categorize token))
-> ([Int] -> Set Int) -> [Int] -> Set (Categorize token)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Int] -> Set Int
forall a. Ord a => [a] -> Set a
Set.fromList) Either Int [Int]
catTest)