{-# LANGUAGE FlexibleInstances #-}
{-# OPTIONS -fno-warn-orphans #-}
-- |
-- Module : Text.RegExp
-- Copyright : Thomas Wilke, Frank Huch, and Sebastian Fischer
-- License : BSD3
-- Maintainer : Sebastian Fischer <mailto:sebf@informatik.uni-kiel.de>
-- Stability : experimental
--
-- This library provides a simple and fast regular expression matcher
-- that is implemented in Haskell without binding to external
-- libraries.
--
-- There are different ways to implement regular expression
-- matching. Backtracking algorithms are simple but need bookkeeping
-- overhead for nondeterministic search. One can use deterministic
-- finite automata (DFA, see
-- <http://swtch.com/~rsc/regexp/regexp1.html>) to match regular
-- expressions faster. But for certain regular expressions these DFA
-- are exponentially large which sometimes leads to prohibitive memory
-- requirements.
--
-- We use a smart and simple algorithm to generate a DFA from a
-- regular expression and do not generate the DFA completely but on
-- the fly while parsing. This leads to a linear-time deterministic
-- algorithm with constant space requirements. More specifically, the
-- run time is limited by the product of the sizes of the regular
-- expression and the string and the memory is limited by the size of
-- the regular expression.
--
module Text.RegExp (
module Data.Semiring, Weight(..),
-- * Constructing regular expressions
RegExp, fromString,
eps, char, sym, psym, anySym, noMatch, alt, seq_, rep, rep1, opt, brep,
perm,
-- * Matching
(=~), acceptFull, acceptPartial, matchingCount, fullMatch, partialMatch
) where
import Data.Semiring
import qualified Data.String
import Text.RegExp.Data
import Text.RegExp.Parser
import Text.RegExp.Matching
-- |
-- Parses a regular expression from its string representation. If the
-- 'OverloadedStrings' language extension is enabled, string literals
-- can be used as regular expressions without using 'fromString'
-- explicitly. Implicit conversion is especially useful in combination
-- with functions like '=~' that take a value of type @RegExp Char@ as
-- argument.
--
-- Here are some examples of supported regular expressions along with
-- an explanation what they mean:
--
-- * @a@ matches the character @a@
--
-- * @[abc]@ matches any of the characters @a@, @b@, or @c@. It is
-- equivalent to @(a|b|c)@, but @|@ can be used to specify
-- alternatives between arbitrary regular expressions, not only
-- characters.
--
-- * @[^abc]@ matches anything but the characters @a@, @b@, or @c@.
--
-- * @\\d@ matches a digit and is equivalent to @[0-9]@. Moreover,
-- @\\D@ matches any non-digit character, @\\s@ and @\\S@ match
-- space and non-space characters and @\\w@ and @\\W@ match word
-- characters and non-word characters, that is, @\\w@ abbreviates
-- @[a-zA-Z_]@.
--
-- * @a?@ matches the empty word or the character @a@, @a*@ matches
-- zero or more occurrences of @a@, and @a+@ matches one or more
-- @a@'s.
--
-- * @.@ (the dot) matches one arbitrary character.
--
-- * @a{4,7}@ matches four to seven occurrences of @a@, @a{2}@
-- matches two.
--
fromString :: String -> RegExp Char
fromString = Data.String.fromString
instance Data.String.IsString (RegExp Char) where
fromString = parse
-- |
-- Matches a sequence of the given regular expressions in any
-- order. For example, the regular expression
--
-- @
-- perm (map char \"abc\")
-- @
--
-- has the same meaning as
--
-- @
-- abc|acb|bca|bac|cba|cab
-- @
--
-- and is represented as
--
-- @
-- a(bc|cb)|b(ca|ac)|c(ba|ab)
-- @
--
perm :: [RegExp c] -> RegExp c
perm [] = eps
perm [r] = r
perm rs = go rs []
where
go [p] qs = p `seq_` perm qs
go (p:ps) qs = (p `seq_` perm (ps ++ qs)) `alt` go ps (p:qs)
-- |
-- Alias for 'acceptFull' specialized for Strings. Useful in combination
-- with the 'IsString' instance for 'RegExp' 'Char'
--
(=~) :: RegExp Char -> String -> Bool
(=~) = acceptFull