<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html>
<head>
<!-- Generated by HsColour, http://www.cs.york.ac.uk/fp/darcs/hscolour/ -->
<title>Text/Regex/TDFA/Pattern.hs</title>
<link type='text/css' rel='stylesheet' href='hscolour.css' />
</head>
<body>
<pre><a name="line-1"></a><span class='hs-comment'>-- | This "Text.Regex.TDFA.Pattern" module provides the 'Pattern' data</span>
<a name="line-2"></a><span class='hs-comment'>-- type and its subtypes. This 'Pattern' type is used to represent</span>
<a name="line-3"></a><span class='hs-comment'>-- the parsed form of a Regular Expression. </span>
<a name="line-4"></a><span class='hs-keyword'>module</span> <span class='hs-conid'>Text</span><span class='hs-varop'>.</span><span class='hs-conid'>Regex</span><span class='hs-varop'>.</span><span class='hs-conid'>TDFA</span><span class='hs-varop'>.</span><span class='hs-conid'>Pattern</span>
<a name="line-5"></a> <span class='hs-layout'>(</span><span class='hs-conid'>Pattern</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span>
<a name="line-6"></a> <span class='hs-layout'>,</span><span class='hs-conid'>PatternSet</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span>
<a name="line-7"></a> <span class='hs-layout'>,</span><span class='hs-conid'>PatternSetCharacterClass</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span>
<a name="line-8"></a> <span class='hs-layout'>,</span><span class='hs-conid'>PatternSetCollatingElement</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span>
<a name="line-9"></a> <span class='hs-layout'>,</span><span class='hs-conid'>PatternSetEquivalenceClass</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span>
<a name="line-10"></a> <span class='hs-layout'>,</span><span class='hs-conid'>GroupIndex</span>
<a name="line-11"></a> <span class='hs-layout'>,</span><span class='hs-conid'>DoPa</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span>
<a name="line-12"></a> <span class='hs-layout'>,</span><span class='hs-varid'>showPattern</span>
<a name="line-13"></a><span class='hs-comment'>-- ** Internal use</span>
<a name="line-14"></a> <span class='hs-layout'>,</span><span class='hs-varid'>starTrans</span>
<a name="line-15"></a><span class='hs-comment'>-- ** Internal use, Operations to support debugging under ghci</span>
<a name="line-16"></a> <span class='hs-layout'>,</span><span class='hs-varid'>starTrans'</span><span class='hs-layout'>,</span><span class='hs-varid'>simplify'</span><span class='hs-layout'>,</span><span class='hs-varid'>dfsPattern</span>
<a name="line-17"></a> <span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-18"></a>
<a name="line-19"></a><span class='hs-comment'>{- By Chris Kuklewicz, 2007. BSD License, see the LICENSE file. -}</span>
<a name="line-20"></a>
<a name="line-21"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>List</span><span class='hs-layout'>(</span><span class='hs-varid'>intersperse</span><span class='hs-layout'>,</span><span class='hs-varid'>partition</span><span class='hs-layout'>)</span>
<a name="line-22"></a><span class='hs-keyword'>import</span> <span class='hs-keyword'>qualified</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Set</span> <span class='hs-keyword'>as</span> <span class='hs-conid'>Set</span><span class='hs-layout'>(</span><span class='hs-varid'>toAscList</span><span class='hs-layout'>,</span><span class='hs-varid'>toList</span><span class='hs-layout'>)</span>
<a name="line-23"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Set</span><span class='hs-layout'>(</span><span class='hs-conid'>Set</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- XXX EnumSet</span>
<a name="line-24"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Text</span><span class='hs-varop'>.</span><span class='hs-conid'>Regex</span><span class='hs-varop'>.</span><span class='hs-conid'>TDFA</span><span class='hs-varop'>.</span><span class='hs-conid'>Common</span><span class='hs-layout'>(</span><span class='hs-conid'>DoPa</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span><span class='hs-conid'>GroupIndex</span><span class='hs-layout'>,</span><span class='hs-varid'>common_error</span><span class='hs-layout'>)</span>
<a name="line-25"></a>
<a name="line-26"></a><a name="err"></a><span class='hs-definition'>err</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>String</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span>
<a name="line-27"></a><span class='hs-definition'>err</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>common_error</span> <span class='hs-str'>"Text.Regex.TDFA.Pattern"</span>
<a name="line-28"></a>
<a name="line-29"></a><a name="Pattern"></a><span class='hs-comment'>-- | Pattern is the type returned by the regular expression parser.</span>
<a name="line-30"></a><a name="Pattern"></a><span class='hs-comment'>-- This is consumed by the CorePattern module and the tender leaves</span>
<a name="line-31"></a><a name="Pattern"></a><span class='hs-comment'>-- are nibbled by the TNFA module.</span>
<a name="line-32"></a><a name="Pattern"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>Pattern</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>PEmpty</span>
<a name="line-33"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>PGroup</span> <span class='hs-layout'>(</span><span class='hs-conid'>Maybe</span> <span class='hs-conid'>GroupIndex</span><span class='hs-layout'>)</span> <span class='hs-conid'>Pattern</span> <span class='hs-comment'>-- Nothing to indicate non-matching PGroup (Nothing never used!)</span>
<a name="line-34"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>POr</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Pattern</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- flattened by starTrans</span>
<a name="line-35"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>PConcat</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Pattern</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- flattened by starTrans</span>
<a name="line-36"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>PQuest</span> <span class='hs-conid'>Pattern</span> <span class='hs-comment'>-- eliminated by starTrans</span>
<a name="line-37"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>PPlus</span> <span class='hs-conid'>Pattern</span> <span class='hs-comment'>-- eliminated by starTrans</span>
<a name="line-38"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>PStar</span> <span class='hs-conid'>Bool</span> <span class='hs-conid'>Pattern</span> <span class='hs-comment'>-- True means mayFirstBeNull is True</span>
<a name="line-39"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>PBound</span> <span class='hs-conid'>Int</span> <span class='hs-layout'>(</span><span class='hs-conid'>Maybe</span> <span class='hs-conid'>Int</span><span class='hs-layout'>)</span> <span class='hs-conid'>Pattern</span> <span class='hs-comment'>-- eliminated by starTrans</span>
<a name="line-40"></a> <span class='hs-comment'>-- The rest of these need an index of where in the regex string it is from</span>
<a name="line-41"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>PCarat</span> <span class='hs-layout'>{</span><span class='hs-varid'>getDoPa</span><span class='hs-keyglyph'>::</span><span class='hs-conid'>DoPa</span><span class='hs-layout'>}</span>
<a name="line-42"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>PDollar</span> <span class='hs-layout'>{</span><span class='hs-varid'>getDoPa</span><span class='hs-keyglyph'>::</span><span class='hs-conid'>DoPa</span><span class='hs-layout'>}</span>
<a name="line-43"></a> <span class='hs-comment'>-- The following test and accept a single character</span>
<a name="line-44"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>PDot</span> <span class='hs-layout'>{</span><span class='hs-varid'>getDoPa</span><span class='hs-keyglyph'>::</span><span class='hs-conid'>DoPa</span><span class='hs-layout'>}</span> <span class='hs-comment'>-- Any character (newline?) at all</span>
<a name="line-45"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>PAny</span> <span class='hs-layout'>{</span><span class='hs-varid'>getDoPa</span><span class='hs-keyglyph'>::</span><span class='hs-conid'>DoPa</span><span class='hs-layout'>,</span><span class='hs-varid'>getPatternSet</span><span class='hs-keyglyph'>::</span><span class='hs-conid'>PatternSet</span><span class='hs-layout'>}</span> <span class='hs-comment'>-- Square bracketed things</span>
<a name="line-46"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>PAnyNot</span> <span class='hs-layout'>{</span><span class='hs-varid'>getDoPa</span><span class='hs-keyglyph'>::</span><span class='hs-conid'>DoPa</span><span class='hs-layout'>,</span><span class='hs-varid'>getPatternSet</span><span class='hs-keyglyph'>::</span><span class='hs-conid'>PatternSet</span><span class='hs-layout'>}</span> <span class='hs-comment'>-- Inverted square bracketed things</span>
<a name="line-47"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>PEscape</span> <span class='hs-layout'>{</span><span class='hs-varid'>getDoPa</span><span class='hs-keyglyph'>::</span><span class='hs-conid'>DoPa</span><span class='hs-layout'>,</span><span class='hs-varid'>getPatternChar</span><span class='hs-keyglyph'>::</span><span class='hs-conid'>Char</span><span class='hs-layout'>}</span> <span class='hs-comment'>-- Backslashed Character</span>
<a name="line-48"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>PChar</span> <span class='hs-layout'>{</span><span class='hs-varid'>getDoPa</span><span class='hs-keyglyph'>::</span><span class='hs-conid'>DoPa</span><span class='hs-layout'>,</span><span class='hs-varid'>getPatternChar</span><span class='hs-keyglyph'>::</span><span class='hs-conid'>Char</span><span class='hs-layout'>}</span> <span class='hs-comment'>-- Specific Character</span>
<a name="line-49"></a> <span class='hs-comment'>-- The following are semantic tags created in starTrans, not the parser</span>
<a name="line-50"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>PNonCapture</span> <span class='hs-conid'>Pattern</span> <span class='hs-comment'>-- introduced by starTrans</span>
<a name="line-51"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>PNonEmpty</span> <span class='hs-conid'>Pattern</span> <span class='hs-comment'>-- introduced by starTrans</span>
<a name="line-52"></a> <span class='hs-keyword'>deriving</span> <span class='hs-layout'>(</span><span class='hs-conid'>Eq</span><span class='hs-layout'>,</span><span class='hs-conid'>Show</span><span class='hs-layout'>)</span>
<a name="line-53"></a>
<a name="line-54"></a><a name="showPattern"></a><span class='hs-comment'>-- | I have not been checking, but this should have the property that</span>
<a name="line-55"></a><span class='hs-comment'>-- parsing the resulting string should result in an identical Pattern.</span>
<a name="line-56"></a><span class='hs-comment'>-- This is not true if starTrans has created PNonCapture and PNonEmpty</span>
<a name="line-57"></a><span class='hs-comment'>-- values or a (PStar False). The contents of a "[ ]" grouping are</span>
<a name="line-58"></a><span class='hs-comment'>-- always shown in a sorted canonical order.</span>
<a name="line-59"></a><span class='hs-definition'>showPattern</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Pattern</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>String</span>
<a name="line-60"></a><span class='hs-definition'>showPattern</span> <span class='hs-varid'>pIn</span> <span class='hs-keyglyph'>=</span>
<a name="line-61"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>pIn</span> <span class='hs-keyword'>of</span>
<a name="line-62"></a> <span class='hs-conid'>PEmpty</span> <span class='hs-keyglyph'>-></span> <span class='hs-str'>"()"</span>
<a name="line-63"></a> <span class='hs-conid'>PGroup</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>paren</span> <span class='hs-layout'>(</span><span class='hs-varid'>showPattern</span> <span class='hs-varid'>p</span><span class='hs-layout'>)</span>
<a name="line-64"></a> <span class='hs-conid'>POr</span> <span class='hs-varid'>ps</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>concat</span> <span class='hs-varop'>$</span> <span class='hs-varid'>intersperse</span> <span class='hs-str'>"|"</span> <span class='hs-layout'>(</span><span class='hs-varid'>map</span> <span class='hs-varid'>showPattern</span> <span class='hs-varid'>ps</span><span class='hs-layout'>)</span>
<a name="line-65"></a> <span class='hs-conid'>PConcat</span> <span class='hs-varid'>ps</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>concatMap</span> <span class='hs-varid'>showPattern</span> <span class='hs-varid'>ps</span>
<a name="line-66"></a> <span class='hs-conid'>PQuest</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>showPattern</span> <span class='hs-varid'>p</span><span class='hs-layout'>)</span><span class='hs-varop'>++</span><span class='hs-str'>"?"</span>
<a name="line-67"></a> <span class='hs-conid'>PPlus</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>showPattern</span> <span class='hs-varid'>p</span><span class='hs-layout'>)</span><span class='hs-varop'>++</span><span class='hs-str'>"+"</span>
<a name="line-68"></a> <span class='hs-comment'>-- If PStar has mayFirstBeNull False then reparsing will forget this flag</span>
<a name="line-69"></a> <span class='hs-conid'>PStar</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>showPattern</span> <span class='hs-varid'>p</span><span class='hs-layout'>)</span><span class='hs-varop'>++</span><span class='hs-str'>"*"</span>
<a name="line-70"></a> <span class='hs-conid'>PBound</span> <span class='hs-varid'>i</span> <span class='hs-layout'>(</span><span class='hs-conid'>Just</span> <span class='hs-varid'>j</span><span class='hs-layout'>)</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>i</span><span class='hs-varop'>==</span><span class='hs-varid'>j</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>showPattern</span> <span class='hs-varid'>p</span> <span class='hs-varop'>++</span> <span class='hs-layout'>(</span><span class='hs-chr'>'{'</span><span class='hs-conop'>:</span><span class='hs-varid'>show</span> <span class='hs-varid'>i</span><span class='hs-layout'>)</span><span class='hs-varop'>++</span><span class='hs-str'>"}"</span>
<a name="line-71"></a> <span class='hs-conid'>PBound</span> <span class='hs-varid'>i</span> <span class='hs-varid'>mj</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>showPattern</span> <span class='hs-varid'>p</span> <span class='hs-varop'>++</span> <span class='hs-layout'>(</span><span class='hs-chr'>'{'</span><span class='hs-conop'>:</span><span class='hs-varid'>show</span> <span class='hs-varid'>i</span><span class='hs-layout'>)</span> <span class='hs-varop'>++</span> <span class='hs-varid'>maybe</span> <span class='hs-str'>",}"</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span><span class='hs-varid'>j</span> <span class='hs-keyglyph'>-></span> <span class='hs-chr'>','</span><span class='hs-conop'>:</span><span class='hs-varid'>show</span> <span class='hs-varid'>j</span><span class='hs-varop'>++</span><span class='hs-str'>"}"</span><span class='hs-layout'>)</span> <span class='hs-varid'>mj</span>
<a name="line-72"></a> <span class='hs-comment'>--</span>
<a name="line-73"></a> <span class='hs-conid'>PCarat</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-str'>"^"</span>
<a name="line-74"></a> <span class='hs-conid'>PDollar</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-str'>"$"</span>
<a name="line-75"></a> <span class='hs-conid'>PDot</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-str'>"."</span>
<a name="line-76"></a> <span class='hs-conid'>PAny</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>ps</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-chr'>'['</span><span class='hs-conop'>:</span><span class='hs-varid'>show</span> <span class='hs-varid'>ps</span><span class='hs-layout'>)</span><span class='hs-varop'>++</span><span class='hs-str'>"]"</span>
<a name="line-77"></a> <span class='hs-conid'>PAnyNot</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>ps</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-chr'>'['</span><span class='hs-conop'>:</span><span class='hs-chr'>'^'</span><span class='hs-conop'>:</span><span class='hs-varid'>show</span> <span class='hs-varid'>ps</span><span class='hs-layout'>)</span><span class='hs-varop'>++</span><span class='hs-str'>"]"</span>
<a name="line-78"></a> <span class='hs-conid'>PEscape</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>c</span> <span class='hs-keyglyph'>-></span> <span class='hs-chr'>'\\'</span><span class='hs-conop'>:</span><span class='hs-varid'>c</span><span class='hs-conop'>:</span><span class='hs-conid'>[]</span>
<a name="line-79"></a> <span class='hs-conid'>PChar</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>c</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>c</span><span class='hs-keyglyph'>]</span>
<a name="line-80"></a> <span class='hs-comment'>-- The following were not directly from the parser, and will not be parsed in properly</span>
<a name="line-81"></a> <span class='hs-conid'>PNonCapture</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>showPattern</span> <span class='hs-varid'>p</span>
<a name="line-82"></a> <span class='hs-conid'>PNonEmpty</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>showPattern</span> <span class='hs-varid'>p</span>
<a name="line-83"></a> <span class='hs-keyword'>where</span> <span class='hs-comment'>{-
<a name="line-84"></a> groupRange x n (y:ys) = if (fromEnum y)-(fromEnum x) == n then groupRange x (succ n) ys
<a name="line-85"></a> else (if n <=3 then take n [x..]
<a name="line-86"></a> else x:'-':(toEnum (pred n+fromEnum x)):[]) ++ groupRange y 1 ys
<a name="line-87"></a> groupRange x n [] = if n <=3 then take n [x..]
<a name="line-88"></a> else x:'-':(toEnum (pred n+fromEnum x)):[]
<a name="line-89"></a>-}</span>
<a name="line-90"></a> <span class='hs-varid'>paren</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-chr'>'('</span><span class='hs-conop'>:</span><span class='hs-varid'>s</span><span class='hs-layout'>)</span><span class='hs-varop'>++</span><span class='hs-str'>")"</span>
<a name="line-91"></a>
<a name="line-92"></a><a name="PatternSet"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>PatternSet</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>PatternSet</span> <span class='hs-layout'>(</span><span class='hs-conid'>Maybe</span> <span class='hs-layout'>(</span><span class='hs-conid'>Set</span> <span class='hs-conid'>Char</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-93"></a> <span class='hs-layout'>(</span><span class='hs-conid'>Maybe</span> <span class='hs-layout'>(</span><span class='hs-conid'>Set</span> <span class='hs-conid'>PatternSetCharacterClass</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-94"></a> <span class='hs-layout'>(</span><span class='hs-conid'>Maybe</span> <span class='hs-layout'>(</span><span class='hs-conid'>Set</span> <span class='hs-conid'>PatternSetCollatingElement</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-95"></a> <span class='hs-layout'>(</span><span class='hs-conid'>Maybe</span> <span class='hs-layout'>(</span><span class='hs-conid'>Set</span> <span class='hs-conid'>PatternSetEquivalenceClass</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-96"></a> <span class='hs-keyword'>deriving</span> <span class='hs-layout'>(</span><span class='hs-conid'>Eq</span><span class='hs-layout'>)</span>
<a name="line-97"></a>
<a name="line-98"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Show</span> <span class='hs-conid'>PatternSet</span> <span class='hs-keyword'>where</span>
<a name="line-99"></a> <span class='hs-varid'>showsPrec</span> <span class='hs-varid'>i</span> <span class='hs-layout'>(</span><span class='hs-conid'>PatternSet</span> <span class='hs-varid'>s</span> <span class='hs-varid'>scc</span> <span class='hs-varid'>sce</span> <span class='hs-varid'>sec</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span>
<a name="line-100"></a> <span class='hs-keyword'>let</span> <span class='hs-layout'>(</span><span class='hs-varid'>special</span><span class='hs-layout'>,</span><span class='hs-varid'>normal</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>maybe</span> <span class='hs-layout'>(</span><span class='hs-str'>""</span><span class='hs-layout'>,</span><span class='hs-str'>""</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>partition</span> <span class='hs-layout'>(</span><span class='hs-varop'>`elem`</span> <span class='hs-str'>"]-"</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-varop'>.</span> <span class='hs-conid'>Set</span><span class='hs-varop'>.</span><span class='hs-varid'>toAscList</span><span class='hs-layout'>)</span> <span class='hs-varid'>s</span>
<a name="line-101"></a> <span class='hs-varid'>charSpec</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-keyword'>if</span> <span class='hs-chr'>']'</span> <span class='hs-varop'>`elem`</span> <span class='hs-varid'>special</span> <span class='hs-keyword'>then</span> <span class='hs-layout'>(</span><span class='hs-chr'>']'</span><span class='hs-conop'>:</span><span class='hs-layout'>)</span> <span class='hs-keyword'>else</span> <span class='hs-varid'>id</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>byRange</span> <span class='hs-varid'>normal</span><span class='hs-layout'>)</span>
<a name="line-102"></a> <span class='hs-varid'>scc'</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>maybe</span> <span class='hs-str'>""</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>concatMap</span> <span class='hs-varid'>show</span><span class='hs-layout'>)</span> <span class='hs-varop'>.</span> <span class='hs-conid'>Set</span><span class='hs-varop'>.</span><span class='hs-varid'>toList</span><span class='hs-layout'>)</span> <span class='hs-varid'>scc</span>
<a name="line-103"></a> <span class='hs-varid'>sce'</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>maybe</span> <span class='hs-str'>""</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>concatMap</span> <span class='hs-varid'>show</span><span class='hs-layout'>)</span> <span class='hs-varop'>.</span> <span class='hs-conid'>Set</span><span class='hs-varop'>.</span><span class='hs-varid'>toList</span><span class='hs-layout'>)</span> <span class='hs-varid'>sce</span>
<a name="line-104"></a> <span class='hs-varid'>sec'</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>maybe</span> <span class='hs-str'>""</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>concatMap</span> <span class='hs-varid'>show</span><span class='hs-layout'>)</span> <span class='hs-varop'>.</span> <span class='hs-conid'>Set</span><span class='hs-varop'>.</span><span class='hs-varid'>toList</span><span class='hs-layout'>)</span> <span class='hs-varid'>sec</span>
<a name="line-105"></a> <span class='hs-keyword'>in</span> <span class='hs-varid'>shows</span> <span class='hs-varid'>charSpec</span>
<a name="line-106"></a> <span class='hs-varop'>.</span> <span class='hs-varid'>showsPrec</span> <span class='hs-varid'>i</span> <span class='hs-varid'>scc'</span> <span class='hs-varop'>.</span> <span class='hs-varid'>showsPrec</span> <span class='hs-varid'>i</span> <span class='hs-varid'>sce'</span> <span class='hs-varop'>.</span> <span class='hs-varid'>showsPrec</span> <span class='hs-varid'>i</span> <span class='hs-varid'>sec'</span>
<a name="line-107"></a> <span class='hs-varop'>.</span> <span class='hs-keyword'>if</span> <span class='hs-chr'>'-'</span> <span class='hs-varop'>`elem`</span> <span class='hs-varid'>special</span> <span class='hs-keyword'>then</span> <span class='hs-varid'>showChar</span> <span class='hs-chr'>'-'</span> <span class='hs-keyword'>else</span> <span class='hs-varid'>id</span>
<a name="line-108"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>byRange</span> <span class='hs-varid'>xAll</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>length</span> <span class='hs-varid'>xAll</span> <span class='hs-varop'><=</span><span class='hs-num'>3</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>xAll</span>
<a name="line-109"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>groupRange</span> <span class='hs-varid'>x</span> <span class='hs-num'>1</span> <span class='hs-varid'>xs</span>
<a name="line-110"></a> <span class='hs-varid'>byRange</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>undefined</span>
<a name="line-111"></a> <span class='hs-varid'>groupRange</span> <span class='hs-varid'>x</span> <span class='hs-varid'>n</span> <span class='hs-layout'>(</span><span class='hs-varid'>y</span><span class='hs-conop'>:</span><span class='hs-varid'>ys</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>if</span> <span class='hs-layout'>(</span><span class='hs-varid'>fromEnum</span> <span class='hs-varid'>y</span><span class='hs-layout'>)</span><span class='hs-comment'>-</span><span class='hs-layout'>(</span><span class='hs-varid'>fromEnum</span> <span class='hs-varid'>x</span><span class='hs-layout'>)</span> <span class='hs-varop'>==</span> <span class='hs-varid'>n</span> <span class='hs-keyword'>then</span> <span class='hs-varid'>groupRange</span> <span class='hs-varid'>x</span> <span class='hs-layout'>(</span><span class='hs-varid'>succ</span> <span class='hs-varid'>n</span><span class='hs-layout'>)</span> <span class='hs-varid'>ys</span>
<a name="line-112"></a> <span class='hs-keyword'>else</span> <span class='hs-layout'>(</span><span class='hs-keyword'>if</span> <span class='hs-varid'>n</span> <span class='hs-varop'><=</span><span class='hs-num'>3</span> <span class='hs-keyword'>then</span> <span class='hs-varid'>take</span> <span class='hs-varid'>n</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>x</span><span class='hs-keyglyph'>..</span><span class='hs-keyglyph'>]</span>
<a name="line-113"></a> <span class='hs-keyword'>else</span> <span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-chr'>'-'</span><span class='hs-conop'>:</span><span class='hs-layout'>(</span><span class='hs-varid'>toEnum</span> <span class='hs-layout'>(</span><span class='hs-varid'>pred</span> <span class='hs-varid'>n</span><span class='hs-varop'>+</span><span class='hs-varid'>fromEnum</span> <span class='hs-varid'>x</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span><span class='hs-conop'>:</span><span class='hs-conid'>[]</span><span class='hs-layout'>)</span> <span class='hs-varop'>++</span> <span class='hs-varid'>groupRange</span> <span class='hs-varid'>y</span> <span class='hs-num'>1</span> <span class='hs-varid'>ys</span>
<a name="line-114"></a> <span class='hs-varid'>groupRange</span> <span class='hs-varid'>x</span> <span class='hs-varid'>n</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>if</span> <span class='hs-varid'>n</span> <span class='hs-varop'><=</span><span class='hs-num'>3</span> <span class='hs-keyword'>then</span> <span class='hs-varid'>take</span> <span class='hs-varid'>n</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>x</span><span class='hs-keyglyph'>..</span><span class='hs-keyglyph'>]</span>
<a name="line-115"></a> <span class='hs-keyword'>else</span> <span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-chr'>'-'</span><span class='hs-conop'>:</span><span class='hs-layout'>(</span><span class='hs-varid'>toEnum</span> <span class='hs-layout'>(</span><span class='hs-varid'>pred</span> <span class='hs-varid'>n</span><span class='hs-varop'>+</span><span class='hs-varid'>fromEnum</span> <span class='hs-varid'>x</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span><span class='hs-conop'>:</span><span class='hs-conid'>[]</span>
<a name="line-116"></a>
<a name="line-117"></a><a name="PatternSetCharacterClass"></a><span class='hs-keyword'>newtype</span> <span class='hs-conid'>PatternSetCharacterClass</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>PatternSetCharacterClass</span> <span class='hs-layout'>{</span><span class='hs-varid'>unSCC</span><span class='hs-keyglyph'>::</span><span class='hs-conid'>String</span><span class='hs-layout'>}</span>
<a name="line-118"></a> <span class='hs-keyword'>deriving</span> <span class='hs-layout'>(</span><span class='hs-conid'>Eq</span><span class='hs-layout'>,</span><span class='hs-conid'>Ord</span><span class='hs-layout'>)</span>
<a name="line-119"></a><a name="PatternSetCollatingElement"></a><span class='hs-keyword'>newtype</span> <span class='hs-conid'>PatternSetCollatingElement</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>PatternSetCollatingElement</span> <span class='hs-layout'>{</span><span class='hs-varid'>unSCE</span><span class='hs-keyglyph'>::</span><span class='hs-conid'>String</span><span class='hs-layout'>}</span>
<a name="line-120"></a> <span class='hs-keyword'>deriving</span> <span class='hs-layout'>(</span><span class='hs-conid'>Eq</span><span class='hs-layout'>,</span><span class='hs-conid'>Ord</span><span class='hs-layout'>)</span>
<a name="line-121"></a><a name="PatternSetEquivalenceClass"></a><span class='hs-keyword'>newtype</span> <span class='hs-conid'>PatternSetEquivalenceClass</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>PatternSetEquivalenceClass</span> <span class='hs-layout'>{</span><span class='hs-varid'>unSEC</span><span class='hs-keyglyph'>::</span><span class='hs-conid'>String</span><span class='hs-layout'>}</span>
<a name="line-122"></a> <span class='hs-keyword'>deriving</span> <span class='hs-layout'>(</span><span class='hs-conid'>Eq</span><span class='hs-layout'>,</span><span class='hs-conid'>Ord</span><span class='hs-layout'>)</span>
<a name="line-123"></a>
<a name="line-124"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Show</span> <span class='hs-conid'>PatternSetCharacterClass</span> <span class='hs-keyword'>where</span>
<a name="line-125"></a> <span class='hs-varid'>showsPrec</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>showChar</span> <span class='hs-chr'>'['</span> <span class='hs-varop'>.</span> <span class='hs-varid'>showChar</span> <span class='hs-chr'>':'</span> <span class='hs-varop'>.</span> <span class='hs-varid'>shows</span> <span class='hs-layout'>(</span><span class='hs-varid'>unSCC</span> <span class='hs-varid'>p</span><span class='hs-layout'>)</span> <span class='hs-varop'>.</span> <span class='hs-varid'>showChar</span> <span class='hs-chr'>':'</span> <span class='hs-varop'>.</span> <span class='hs-varid'>showChar</span> <span class='hs-chr'>']'</span>
<a name="line-126"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Show</span> <span class='hs-conid'>PatternSetCollatingElement</span> <span class='hs-keyword'>where</span>
<a name="line-127"></a> <span class='hs-varid'>showsPrec</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>showChar</span> <span class='hs-chr'>'['</span> <span class='hs-varop'>.</span> <span class='hs-varid'>showChar</span> <span class='hs-chr'>'.'</span> <span class='hs-varop'>.</span> <span class='hs-varid'>shows</span> <span class='hs-layout'>(</span><span class='hs-varid'>unSCE</span> <span class='hs-varid'>p</span><span class='hs-layout'>)</span> <span class='hs-varop'>.</span> <span class='hs-varid'>showChar</span> <span class='hs-chr'>'.'</span> <span class='hs-varop'>.</span> <span class='hs-varid'>showChar</span> <span class='hs-chr'>']'</span>
<a name="line-128"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Show</span> <span class='hs-conid'>PatternSetEquivalenceClass</span> <span class='hs-keyword'>where</span>
<a name="line-129"></a> <span class='hs-varid'>showsPrec</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>showChar</span> <span class='hs-chr'>'['</span> <span class='hs-varop'>.</span> <span class='hs-varid'>showChar</span> <span class='hs-chr'>'='</span> <span class='hs-varop'>.</span> <span class='hs-varid'>shows</span> <span class='hs-layout'>(</span><span class='hs-varid'>unSEC</span> <span class='hs-varid'>p</span><span class='hs-layout'>)</span> <span class='hs-varop'>.</span> <span class='hs-varid'>showChar</span> <span class='hs-chr'>'='</span> <span class='hs-varop'>.</span> <span class='hs-varid'>showChar</span> <span class='hs-chr'>']'</span>
<a name="line-130"></a>
<a name="line-131"></a><span class='hs-comment'>-- == -- == -- == -- == -- == -- == -- == -- == -- == -- == -- == -- == -- == -- == -- == -- == -- == -- == </span>
<a name="line-132"></a>
<a name="line-133"></a><a name="starTrans"></a><span class='hs-comment'>-- | Do the transformation and simplification in a single traversal.</span>
<a name="line-134"></a><span class='hs-comment'>-- This removes the PPlus, PQuest, and PBound values, changing to POr</span>
<a name="line-135"></a><span class='hs-comment'>-- and PEmpty and PStar True/False. For some PBound values it adds</span>
<a name="line-136"></a><span class='hs-comment'>-- PNonEmpty and PNonCapture semantic marker. It also simplifies to</span>
<a name="line-137"></a><span class='hs-comment'>-- flatten out nested POr and PConcat instances and eliminate some</span>
<a name="line-138"></a><span class='hs-comment'>-- unneeded PEmpty values.</span>
<a name="line-139"></a><span class='hs-definition'>starTrans</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Pattern</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Pattern</span>
<a name="line-140"></a><span class='hs-definition'>starTrans</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>dfsPattern</span> <span class='hs-layout'>(</span><span class='hs-varid'>simplify'</span> <span class='hs-varop'>.</span> <span class='hs-varid'>starTrans'</span><span class='hs-layout'>)</span>
<a name="line-141"></a>
<a name="line-142"></a><a name="dfsPattern"></a><span class='hs-comment'>-- | Apply a Pattern transfomation function depth first</span>
<a name="line-143"></a><span class='hs-definition'>dfsPattern</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Pattern</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Pattern</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- ^ The transformation function</span>
<a name="line-144"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Pattern</span> <span class='hs-comment'>-- ^ The Pattern to transform</span>
<a name="line-145"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Pattern</span> <span class='hs-comment'>-- ^ The transformed Pattern</span>
<a name="line-146"></a><span class='hs-definition'>dfsPattern</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>dfs</span>
<a name="line-147"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>unary</span> <span class='hs-varid'>c</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>f</span> <span class='hs-varop'>.</span> <span class='hs-varid'>c</span> <span class='hs-varop'>.</span> <span class='hs-varid'>dfs</span>
<a name="line-148"></a> <span class='hs-varid'>dfs</span> <span class='hs-varid'>pattern</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>pattern</span> <span class='hs-keyword'>of</span>
<a name="line-149"></a> <span class='hs-conid'>POr</span> <span class='hs-varid'>ps</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-conid'>POr</span> <span class='hs-layout'>(</span><span class='hs-varid'>map</span> <span class='hs-varid'>dfs</span> <span class='hs-varid'>ps</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-150"></a> <span class='hs-conid'>PConcat</span> <span class='hs-varid'>ps</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-conid'>PConcat</span> <span class='hs-layout'>(</span><span class='hs-varid'>map</span> <span class='hs-varid'>dfs</span> <span class='hs-varid'>ps</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-151"></a> <span class='hs-conid'>PGroup</span> <span class='hs-varid'>i</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>unary</span> <span class='hs-layout'>(</span><span class='hs-conid'>PGroup</span> <span class='hs-varid'>i</span><span class='hs-layout'>)</span> <span class='hs-varid'>p</span>
<a name="line-152"></a> <span class='hs-conid'>PQuest</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>unary</span> <span class='hs-conid'>PQuest</span> <span class='hs-varid'>p</span>
<a name="line-153"></a> <span class='hs-conid'>PPlus</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>unary</span> <span class='hs-conid'>PPlus</span> <span class='hs-varid'>p</span>
<a name="line-154"></a> <span class='hs-conid'>PStar</span> <span class='hs-varid'>i</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>unary</span> <span class='hs-layout'>(</span><span class='hs-conid'>PStar</span> <span class='hs-varid'>i</span><span class='hs-layout'>)</span> <span class='hs-varid'>p</span>
<a name="line-155"></a> <span class='hs-conid'>PBound</span> <span class='hs-varid'>i</span> <span class='hs-varid'>mi</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>unary</span> <span class='hs-layout'>(</span><span class='hs-conid'>PBound</span> <span class='hs-varid'>i</span> <span class='hs-varid'>mi</span><span class='hs-layout'>)</span> <span class='hs-varid'>p</span>
<a name="line-156"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>f</span> <span class='hs-varid'>pattern</span>
<a name="line-157"></a>
<a name="line-158"></a><a name="reGroup"></a><span class='hs-comment'>{- Replace by PNonCapture
<a name="line-159"></a>unCapture = dfsPattern unCapture' where
<a name="line-160"></a> unCapture' (PGroup (Just _) p) = PGroup Nothing p
<a name="line-161"></a> unCapture' x = x
<a name="line-162"></a>-}</span>
<a name="line-163"></a><span class='hs-definition'>reGroup</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Pattern</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Pattern</span>
<a name="line-164"></a><span class='hs-definition'>reGroup</span> <span class='hs-varid'>p</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>PConcat</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-num'>2</span> <span class='hs-varop'><=</span> <span class='hs-varid'>length</span> <span class='hs-varid'>xs</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>PGroup</span> <span class='hs-conid'>Nothing</span> <span class='hs-varid'>p</span>
<a name="line-165"></a><span class='hs-definition'>reGroup</span> <span class='hs-varid'>p</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>POr</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-num'>2</span> <span class='hs-varop'><=</span> <span class='hs-varid'>length</span> <span class='hs-varid'>xs</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>PGroup</span> <span class='hs-conid'>Nothing</span> <span class='hs-varid'>p</span>
<a name="line-166"></a><span class='hs-definition'>reGroup</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>p</span>
<a name="line-167"></a>
<a name="line-168"></a><a name="starTrans'"></a><span class='hs-definition'>starTrans'</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Pattern</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Pattern</span>
<a name="line-169"></a><span class='hs-definition'>starTrans'</span> <span class='hs-varid'>pIn</span> <span class='hs-keyglyph'>=</span>
<a name="line-170"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>pIn</span> <span class='hs-keyword'>of</span> <span class='hs-comment'>-- We know that "p" has been simplified in each of these cases:</span>
<a name="line-171"></a> <span class='hs-conid'>PQuest</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>POr</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>p</span><span class='hs-layout'>,</span><span class='hs-conid'>PEmpty</span><span class='hs-keyglyph'>]</span>
<a name="line-172"></a>
<a name="line-173"></a><span class='hs-comment'>{- The PStar should not capture 0 characters on its first iteration,
<a name="line-174"></a> so set its mayFirstBeNull flag to False
<a name="line-175"></a> -}</span>
<a name="line-176"></a> <span class='hs-conid'>PPlus</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>canOnlyMatchNull</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>p</span>
<a name="line-177"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>asGroup</span> <span class='hs-varop'>$</span> <span class='hs-conid'>PConcat</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>reGroup</span> <span class='hs-varid'>p</span><span class='hs-layout'>,</span><span class='hs-conid'>PStar</span> <span class='hs-conid'>False</span> <span class='hs-varid'>p</span><span class='hs-keyglyph'>]</span>
<a name="line-178"></a>
<a name="line-179"></a><span class='hs-comment'>{- "An ERE matching a single character repeated by an '*' , '?' , or
<a name="line-180"></a> an interval expression shall not match a null expression unless
<a name="line-181"></a> this is the only match for the repetition or it is necessary to
<a name="line-182"></a> satisfy the exact or minimum number of occurrences for the interval
<a name="line-183"></a> expression."
<a name="line-184"></a> -}</span>
<a name="line-185"></a><span class='hs-comment'>{- p? is p|PEmpty which prefers even a 0-character match for p
<a name="line-186"></a> p{0,1} is p? is POr [p,PEmpty]
<a name="line-187"></a> p{0,2} is (pp?)? NOT p?p?
<a name="line-188"></a> p{0,3} is (p(pp?)?)?
<a name="line-189"></a> p{1,2} is like pp{0,1} is like pp? but see below
<a name="line-190"></a> p{2,5} is ppp{0,3} is pp(p(pp?)?)?
<a name="line-191"></a>
<a name="line-192"></a> But this is not always right. Because if the second use of p in
<a name="line-193"></a> p?p? matches 0 characters then the perhaps non 0 character match of
<a name="line-194"></a> the first p is overwritten.
<a name="line-195"></a>
<a name="line-196"></a> We need a new operation "p!" that means "p?" unless "p" match 0
<a name="line-197"></a> characters, in which case skip p as if it failed in "p?". Thus
<a name="line-198"></a> when p cannot accept 0 characters p! and p? are equivalent. And
<a name="line-199"></a> when p can only match 0 characters p! is PEmpty. So for
<a name="line-200"></a> simplicity, only use ! when p can match 0 characters but not only 0
<a name="line-201"></a> characters.
<a name="line-202"></a>
<a name="line-203"></a> Call this (PNonEmpty p) in the Pattern type.
<a name="line-204"></a> p! is PNonEmpty p is POr [PEmpty,p]
<a name="line-205"></a> IS THIS TRUE? Use QuickCheck?
<a name="line-206"></a>
<a name="line-207"></a> Note that if p cannot match 0 characters then p! is p? and vice versa
<a name="line-208"></a>
<a name="line-209"></a> The p{0,1} is still always p? and POr [p,PEmpty]
<a name="line-210"></a> Now p{0,2} means p?p! or (pp!)? and p{0,3} means (p(pp!)!)? or p?p!p!
<a name="line-211"></a> Equivalently p?p! and p?p!p!
<a name="line-212"></a> And p{2,2} is p'p and p{3,3} is p'p'p and p{4} is p'p'p'p
<a name="line-213"></a> The p{1,2} is pp! and p{1,3} is pp!p! or p(pp!)!
<a name="line-214"></a> And p{2,4} means p'pp!p! and p{3,6} is p'p'pp!p!p! or p'p'p(p(pp!)!)!
<a name="line-215"></a>
<a name="line-216"></a> But this second form still has a problem: the (pp!)! can have the first
<a name="line-217"></a> p match 0 and the second p match non-zero. This showed up for (.|$){1,3}
<a name="line-218"></a> since ($.!)! should not be a valid path but altered the qt_win commands.
<a name="line-219"></a>
<a name="line-220"></a> Thus only p'p'pp!p!p! has the right semantics. For completeness:
<a name="line-221"></a>
<a name="line-222"></a> if p can only match only 0 characters then the cases are
<a name="line-223"></a> p{0,0} is (), p{0,_} = p?, p{_,_} is p
<a name="line-224"></a>
<a name="line-225"></a> if p can match 0 or non-zero characters then cases are
<a name="line-226"></a> p{0,0} is (), p{0,1} is (p)?, p{0,2} is (pp!)?, p{0,3} is (pp!p!)?
<a name="line-227"></a> p{1,1} is p, p{1,2} is pp!, p{1,3} is pp!p!, p{1,4} is pp!p!p!
<a name="line-228"></a> p{2,2} is p'p,
<a name="line-229"></a> p{2,3} is p'pp!,
<a name="line-230"></a> p{2,4} is p'pp!p! or p'p(pp!)!
<a name="line-231"></a> p{2,5} is p'pp!p!p! or p'p(p(pp!)!)!
<a name="line-232"></a> p{3,3} is p'p'p, p{3,4} is p'p'pp!, p{3,5} is p'p'pp!p!, p{3,6} is p'p'pp!p!p!
<a name="line-233"></a>
<a name="line-234"></a> if p can only match 1 or more characters then cases are
<a name="line-235"></a> p{0,0} is ()
<a name="line-236"></a> p{0,1} is p?, p{0,2} is (pp?)?, p{0,3} is (p(pp?)?)?, p{0,4} is (pp{0,3})?
<a name="line-237"></a> p{1,1} is p, p{1,j} is pp{0,pred j}
<a name="line-238"></a> p{2,2} is p'p, p{2,3} is p'pp?, p{2,4} is p'p(pp?)?, p{2,5} = p'p{1,4} = p'(pp{0,3})
<a name="line-239"></a> p{3,3} is p'p'p, p{3,4} is p'p'pp?, p{3,5} is p'p'p(pp?)?, p{3,6} is
<a name="line-240"></a>
<a name="line-241"></a> And by this logic, the PStar False is really p*! So p{0,} is p*
<a name="line-242"></a> and p{1,} is pp*! and p{2,} is p'pp*! and p{3,} is p'p'pp*!
<a name="line-243"></a>
<a name="line-244"></a> The (nonEmpty' p) below is the only way PNonEmpty is introduced
<a name="line-245"></a> into the Pattern. It is always preceded by p inside a PConcat
<a name="line-246"></a> list. The p involved never simplifies to PEmpty. Thus it is
<a name="line-247"></a> impossible to have PNonEmpty directly nested, i.e. (PNonEmpty
<a name="line-248"></a> (PNonEmpty _)) never occurs even after simplifications.
<a name="line-249"></a>
<a name="line-250"></a> The (nonCapture' p) below is the only way PNonCapture is
<a name="line-251"></a> introduced into the Pattern. It is always followed by p inside a
<a name="line-252"></a> PConcat list.
<a name="line-253"></a>
<a name="line-254"></a>-}</span>
<a name="line-255"></a><span class='hs-comment'>-- Easy cases</span>
<a name="line-256"></a> <span class='hs-conid'>PBound</span> <span class='hs-varid'>i</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>i</span><span class='hs-varop'><</span><span class='hs-num'>0</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>PEmpty</span> <span class='hs-comment'>-- impossibly malformed</span>
<a name="line-257"></a> <span class='hs-conid'>PBound</span> <span class='hs-varid'>i</span> <span class='hs-layout'>(</span><span class='hs-conid'>Just</span> <span class='hs-varid'>j</span><span class='hs-layout'>)</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>i</span><span class='hs-varop'>></span><span class='hs-varid'>j</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>PEmpty</span> <span class='hs-comment'>-- impossibly malformed</span>
<a name="line-258"></a> <span class='hs-conid'>PBound</span> <span class='hs-keyword'>_</span> <span class='hs-layout'>(</span><span class='hs-conid'>Just</span> <span class='hs-num'>0</span><span class='hs-layout'>)</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>PEmpty</span>
<a name="line-259"></a><span class='hs-comment'>-- Medium cases</span>
<a name="line-260"></a> <span class='hs-conid'>PBound</span> <span class='hs-num'>0</span> <span class='hs-conid'>Nothing</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>canOnlyMatchNull</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>quest</span> <span class='hs-varid'>p</span>
<a name="line-261"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>PStar</span> <span class='hs-conid'>True</span> <span class='hs-varid'>p</span>
<a name="line-262"></a> <span class='hs-conid'>PBound</span> <span class='hs-num'>0</span> <span class='hs-layout'>(</span><span class='hs-conid'>Just</span> <span class='hs-num'>1</span><span class='hs-layout'>)</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>quest</span> <span class='hs-varid'>p</span>
<a name="line-263"></a><span class='hs-comment'>-- Hard cases</span>
<a name="line-264"></a> <span class='hs-conid'>PBound</span> <span class='hs-varid'>i</span> <span class='hs-conid'>Nothing</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>canOnlyMatchNull</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>p</span>
<a name="line-265"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>asGroup</span> <span class='hs-varop'>.</span> <span class='hs-conid'>PConcat</span> <span class='hs-varop'>$</span> <span class='hs-varid'>apply</span> <span class='hs-layout'>(</span><span class='hs-varid'>nc'p</span><span class='hs-conop'>:</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>pred</span> <span class='hs-varid'>i</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>reGroup</span> <span class='hs-varid'>p</span><span class='hs-layout'>,</span><span class='hs-conid'>PStar</span> <span class='hs-conid'>False</span> <span class='hs-varid'>p</span><span class='hs-keyglyph'>]</span>
<a name="line-266"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>nc'p</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>nonCapture'</span> <span class='hs-varid'>p</span>
<a name="line-267"></a> <span class='hs-conid'>PBound</span> <span class='hs-num'>0</span> <span class='hs-layout'>(</span><span class='hs-conid'>Just</span> <span class='hs-varid'>j</span><span class='hs-layout'>)</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>canOnlyMatchNull</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>quest</span> <span class='hs-varid'>p</span>
<a name="line-268"></a> <span class='hs-comment'>-- The first operation is quest NOT nonEmpty. This can be tested with</span>
<a name="line-269"></a> <span class='hs-comment'>-- "a\nb" "((^)?|b){0,3}" and "a\nb" "((^)|b){0,3}"</span>
<a name="line-270"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>quest</span> <span class='hs-varop'>.</span> <span class='hs-layout'>(</span><span class='hs-varid'>concat'</span> <span class='hs-varid'>p</span><span class='hs-layout'>)</span> <span class='hs-varop'>$</span>
<a name="line-271"></a> <span class='hs-varid'>apply</span> <span class='hs-layout'>(</span><span class='hs-varid'>nonEmpty'</span> <span class='hs-varop'>.</span> <span class='hs-layout'>(</span><span class='hs-varid'>concat'</span> <span class='hs-varid'>p</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>j</span><span class='hs-comment'>-</span><span class='hs-num'>2</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>nonEmpty'</span> <span class='hs-varid'>p</span><span class='hs-layout'>)</span>
<a name="line-272"></a><span class='hs-comment'>{- 0.99.6 remove
<a name="line-273"></a>| cannotMatchNull p -> apply (quest' . (concat' p)) (pred j) (quest' p)
<a name="line-274"></a>| otherwise -> POr [ simplify' (PConcat (p : replicate (pred j) (nonEmpty' p))) , PEmpty ]
<a name="line-275"></a>-}</span>
<a name="line-276"></a><span class='hs-comment'>{- 0.99.6 add, 0.99.7 remove
<a name="line-277"></a> PBound i (Just j) p | canOnlyMatchNull p -> p
<a name="line-278"></a> | i == j -> PConcat $ apply (p':) (pred i) [p]
<a name="line-279"></a> | otherwise -> PConcat $ apply (p':) (pred i)
<a name="line-280"></a> [p,apply (nonEmpty' . (concat' p)) (j-i-1) (nonEmpty' p) ]
<a name="line-281"></a> where p' = nonCapture' p
<a name="line-282"></a>-}</span>
<a name="line-283"></a><span class='hs-comment'>{- 0.99.7 add -}</span>
<a name="line-284"></a> <span class='hs-conid'>PBound</span> <span class='hs-varid'>i</span> <span class='hs-layout'>(</span><span class='hs-conid'>Just</span> <span class='hs-varid'>j</span><span class='hs-layout'>)</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>canOnlyMatchNull</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>p</span>
<a name="line-285"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>i</span> <span class='hs-varop'>==</span> <span class='hs-varid'>j</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>asGroup</span> <span class='hs-varop'>.</span> <span class='hs-conid'>PConcat</span> <span class='hs-varop'>$</span> <span class='hs-varid'>apply</span> <span class='hs-layout'>(</span><span class='hs-varid'>nc'p</span><span class='hs-conop'>:</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>pred</span> <span class='hs-varid'>i</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>reGroup</span> <span class='hs-varid'>p</span><span class='hs-keyglyph'>]</span>
<a name="line-286"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>asGroup</span> <span class='hs-varop'>.</span> <span class='hs-conid'>PConcat</span> <span class='hs-varop'>$</span> <span class='hs-varid'>apply</span> <span class='hs-layout'>(</span><span class='hs-varid'>nc'p</span><span class='hs-conop'>:</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>pred</span> <span class='hs-varid'>i</span><span class='hs-layout'>)</span>
<a name="line-287"></a> <span class='hs-keyglyph'>[</span><span class='hs-varid'>reGroup</span> <span class='hs-varid'>p</span><span class='hs-layout'>,</span><span class='hs-varid'>apply</span> <span class='hs-layout'>(</span><span class='hs-varid'>nonEmpty'</span> <span class='hs-varop'>.</span> <span class='hs-layout'>(</span><span class='hs-varid'>concat'</span> <span class='hs-varid'>p</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>j</span><span class='hs-comment'>-</span><span class='hs-varid'>i</span><span class='hs-comment'>-</span><span class='hs-num'>1</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>ne'p</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>]</span>
<a name="line-288"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>nc'p</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>nonCapture'</span> <span class='hs-varid'>p</span>
<a name="line-289"></a> <span class='hs-varid'>ne'p</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>nonEmpty'</span> <span class='hs-varid'>p</span>
<a name="line-290"></a><span class='hs-comment'>{- 0.99.6
<a name="line-291"></a>| cannotMatchNull p -> PConcat $ apply (p':) (pred i) $ (p:) $
<a name="line-292"></a> [apply (quest' . (concat' p)) (pred (j-i)) (quest' p)]
<a name="line-293"></a>| otherwise -> PConcat $ (replicate (pred i) p') ++ p : (replicate (j-i) (nonEmpty' p))
<a name="line-294"></a>-}</span>
<a name="line-295"></a> <span class='hs-conid'>PStar</span> <span class='hs-varid'>mayFirstBeNull</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>canOnlyMatchNull</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>if</span> <span class='hs-varid'>mayFirstBeNull</span> <span class='hs-keyword'>then</span> <span class='hs-varid'>quest</span> <span class='hs-varid'>p</span>
<a name="line-296"></a> <span class='hs-keyword'>else</span> <span class='hs-conid'>PEmpty</span>
<a name="line-297"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>pass</span>
<a name="line-298"></a> <span class='hs-comment'>-- Left intact</span>
<a name="line-299"></a> <span class='hs-conid'>PEmpty</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>pass</span>
<a name="line-300"></a> <span class='hs-conid'>PGroup</span> <span class='hs-layout'>{</span><span class='hs-layout'>}</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>pass</span>
<a name="line-301"></a> <span class='hs-conid'>POr</span> <span class='hs-layout'>{</span><span class='hs-layout'>}</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>pass</span>
<a name="line-302"></a> <span class='hs-conid'>PConcat</span> <span class='hs-layout'>{</span><span class='hs-layout'>}</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>pass</span>
<a name="line-303"></a> <span class='hs-conid'>PCarat</span> <span class='hs-layout'>{</span><span class='hs-layout'>}</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>pass</span>
<a name="line-304"></a> <span class='hs-conid'>PDollar</span> <span class='hs-layout'>{</span><span class='hs-layout'>}</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>pass</span>
<a name="line-305"></a> <span class='hs-conid'>PDot</span> <span class='hs-layout'>{</span><span class='hs-layout'>}</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>pass</span>
<a name="line-306"></a> <span class='hs-conid'>PAny</span> <span class='hs-layout'>{</span><span class='hs-layout'>}</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>pass</span>
<a name="line-307"></a> <span class='hs-conid'>PAnyNot</span> <span class='hs-layout'>{</span><span class='hs-layout'>}</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>pass</span>
<a name="line-308"></a> <span class='hs-conid'>PEscape</span> <span class='hs-layout'>{</span><span class='hs-layout'>}</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>pass</span>
<a name="line-309"></a> <span class='hs-conid'>PChar</span> <span class='hs-layout'>{</span><span class='hs-layout'>}</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>pass</span>
<a name="line-310"></a> <span class='hs-conid'>PNonCapture</span> <span class='hs-layout'>{</span><span class='hs-layout'>}</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>pass</span>
<a name="line-311"></a> <span class='hs-conid'>PNonEmpty</span> <span class='hs-layout'>{</span><span class='hs-layout'>}</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>pass</span> <span class='hs-comment'>-- TODO : remove PNonEmpty from program</span>
<a name="line-312"></a> <span class='hs-keyword'>where</span>
<a name="line-313"></a> <span class='hs-varid'>quest</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>POr</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>p</span><span class='hs-layout'>,</span><span class='hs-conid'>PEmpty</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- require p to have been simplified</span>
<a name="line-314"></a><span class='hs-comment'>-- quest' = (\ p -> simplify' $ POr [p,PEmpty]) -- require p to have been simplified</span>
<a name="line-315"></a> <span class='hs-varid'>concat'</span> <span class='hs-varid'>a</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>simplify'</span> <span class='hs-varop'>$</span> <span class='hs-conid'>PConcat</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>reGroup</span> <span class='hs-varid'>a</span><span class='hs-layout'>,</span><span class='hs-varid'>reGroup</span> <span class='hs-varid'>b</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- require a and b to have been simplified</span>
<a name="line-316"></a> <span class='hs-varid'>nonEmpty'</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>simplify'</span> <span class='hs-varop'>$</span> <span class='hs-conid'>POr</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>PEmpty</span><span class='hs-layout'>,</span><span class='hs-varid'>p</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- 2009-01-19 : this was PNonEmpty</span>
<a name="line-317"></a> <span class='hs-varid'>nonCapture'</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>PNonCapture</span>
<a name="line-318"></a> <span class='hs-varid'>apply</span> <span class='hs-varid'>f</span> <span class='hs-varid'>n</span> <span class='hs-varid'>x</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldr</span> <span class='hs-layout'>(</span><span class='hs-varop'>$</span><span class='hs-layout'>)</span> <span class='hs-varid'>x</span> <span class='hs-layout'>(</span><span class='hs-varid'>replicate</span> <span class='hs-varid'>n</span> <span class='hs-varid'>f</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- function f applied n times to x : f^n(x)</span>
<a name="line-319"></a> <span class='hs-varid'>asGroup</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>PGroup</span> <span class='hs-conid'>Nothing</span> <span class='hs-layout'>(</span><span class='hs-varid'>simplify'</span> <span class='hs-varid'>p</span><span class='hs-layout'>)</span>
<a name="line-320"></a> <span class='hs-varid'>pass</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>pIn</span>
<a name="line-321"></a>
<a name="line-322"></a><a name="simplify'"></a><span class='hs-comment'>-- | Function to transform a pattern into an equivalent, but less</span>
<a name="line-323"></a><span class='hs-comment'>-- redundant form. Nested 'POr' and 'PConcat' are flattened. PEmpty</span>
<a name="line-324"></a><span class='hs-comment'>-- is propagated.</span>
<a name="line-325"></a><span class='hs-definition'>simplify'</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Pattern</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Pattern</span>
<a name="line-326"></a><span class='hs-definition'>simplify'</span> <span class='hs-varid'>x</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>POr</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span>
<a name="line-327"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>ps'</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>span</span> <span class='hs-varid'>notPEmpty</span> <span class='hs-layout'>(</span><span class='hs-varid'>flatten</span> <span class='hs-varid'>x</span><span class='hs-layout'>)</span> <span class='hs-keyword'>of</span>
<a name="line-328"></a> <span class='hs-layout'>(</span><span class='hs-varid'>notEmpty</span><span class='hs-layout'>,</span><span class='hs-conid'>[]</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>notEmpty</span>
<a name="line-329"></a> <span class='hs-layout'>(</span><span class='hs-varid'>notEmpty</span><span class='hs-layout'>,</span><span class='hs-keyword'>_</span><span class='hs-conop'>:</span><span class='hs-varid'>rest</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>notEmpty</span> <span class='hs-varop'>++</span> <span class='hs-layout'>(</span><span class='hs-conid'>PEmpty</span><span class='hs-conop'>:</span><span class='hs-varid'>filter</span> <span class='hs-varid'>notPEmpty</span> <span class='hs-varid'>rest</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- keep 1st PEmpty only</span>
<a name="line-330"></a> <span class='hs-keyword'>in</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>ps'</span> <span class='hs-keyword'>of</span>
<a name="line-331"></a> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>PEmpty</span>
<a name="line-332"></a> <span class='hs-keyglyph'>[</span><span class='hs-varid'>p</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>p</span>
<a name="line-333"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>POr</span> <span class='hs-varid'>ps'</span>
<a name="line-334"></a><span class='hs-definition'>simplify'</span> <span class='hs-varid'>x</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>PConcat</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span>
<a name="line-335"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>ps'</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>filter</span> <span class='hs-varid'>notPEmpty</span> <span class='hs-layout'>(</span><span class='hs-varid'>flatten</span> <span class='hs-varid'>x</span><span class='hs-layout'>)</span>
<a name="line-336"></a> <span class='hs-keyword'>in</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>ps'</span> <span class='hs-keyword'>of</span>
<a name="line-337"></a> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>PEmpty</span>
<a name="line-338"></a> <span class='hs-keyglyph'>[</span><span class='hs-varid'>p</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>p</span>
<a name="line-339"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>PConcat</span> <span class='hs-varid'>ps'</span> <span class='hs-comment'>-- PConcat ps'</span>
<a name="line-340"></a><span class='hs-definition'>simplify'</span> <span class='hs-layout'>(</span><span class='hs-conid'>PStar</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>PEmpty</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>PEmpty</span>
<a name="line-341"></a><span class='hs-definition'>simplify'</span> <span class='hs-layout'>(</span><span class='hs-conid'>PNonCapture</span> <span class='hs-conid'>PEmpty</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>PEmpty</span> <span class='hs-comment'>-- 2009, perhaps useful</span>
<a name="line-342"></a><span class='hs-comment'>--simplify' (PNonEmpty PEmpty) = err "simplify' (PNonEmpty PEmpty) = should be Impossible!" -- 2009</span>
<a name="line-343"></a><span class='hs-definition'>simplify'</span> <span class='hs-varid'>other</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>other</span>
<a name="line-344"></a>
<a name="line-345"></a><a name="flatten"></a><span class='hs-comment'>-- | Function to flatten nested POr or nested PConcat applicataions.</span>
<a name="line-346"></a><span class='hs-definition'>flatten</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Pattern</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Pattern</span><span class='hs-keyglyph'>]</span>
<a name="line-347"></a><span class='hs-definition'>flatten</span> <span class='hs-layout'>(</span><span class='hs-conid'>POr</span> <span class='hs-varid'>ps</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-varid'>concatMap</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span><span class='hs-varid'>x</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>case</span> <span class='hs-varid'>x</span> <span class='hs-keyword'>of</span>
<a name="line-348"></a> <span class='hs-conid'>POr</span> <span class='hs-varid'>ps'</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>ps'</span>
<a name="line-349"></a> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>p</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>)</span> <span class='hs-varid'>ps</span><span class='hs-layout'>)</span>
<a name="line-350"></a><span class='hs-definition'>flatten</span> <span class='hs-layout'>(</span><span class='hs-conid'>PConcat</span> <span class='hs-varid'>ps</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-varid'>concatMap</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span><span class='hs-varid'>x</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>case</span> <span class='hs-varid'>x</span> <span class='hs-keyword'>of</span>
<a name="line-351"></a> <span class='hs-conid'>PConcat</span> <span class='hs-varid'>ps'</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>ps'</span>
<a name="line-352"></a> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>p</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>)</span> <span class='hs-varid'>ps</span><span class='hs-layout'>)</span>
<a name="line-353"></a><span class='hs-definition'>flatten</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>err</span> <span class='hs-str'>"flatten can only be applied to POr or PConcat"</span>
<a name="line-354"></a>
<a name="line-355"></a><a name="notPEmpty"></a><span class='hs-definition'>notPEmpty</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Pattern</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span>
<a name="line-356"></a><span class='hs-definition'>notPEmpty</span> <span class='hs-conid'>PEmpty</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span>
<a name="line-357"></a><span class='hs-definition'>notPEmpty</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>True</span>
<a name="line-358"></a>
<a name="line-359"></a><a name="canOnlyMatchNull"></a><span class='hs-comment'>-- | Determines if pIn will fail or accept [] and never accept any</span>
<a name="line-360"></a><span class='hs-comment'>-- characters. Treat PCarat and PDollar as True.</span>
<a name="line-361"></a><span class='hs-definition'>canOnlyMatchNull</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Pattern</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span>
<a name="line-362"></a><span class='hs-definition'>canOnlyMatchNull</span> <span class='hs-varid'>pIn</span> <span class='hs-keyglyph'>=</span>
<a name="line-363"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>pIn</span> <span class='hs-keyword'>of</span>
<a name="line-364"></a> <span class='hs-conid'>PEmpty</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>True</span>
<a name="line-365"></a> <span class='hs-conid'>PGroup</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>canOnlyMatchNull</span> <span class='hs-varid'>p</span>
<a name="line-366"></a> <span class='hs-conid'>POr</span> <span class='hs-varid'>ps</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>all</span> <span class='hs-varid'>canOnlyMatchNull</span> <span class='hs-varid'>ps</span>
<a name="line-367"></a> <span class='hs-conid'>PConcat</span> <span class='hs-varid'>ps</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>all</span> <span class='hs-varid'>canOnlyMatchNull</span> <span class='hs-varid'>ps</span>
<a name="line-368"></a> <span class='hs-conid'>PQuest</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>canOnlyMatchNull</span> <span class='hs-varid'>p</span>
<a name="line-369"></a> <span class='hs-conid'>PPlus</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>canOnlyMatchNull</span> <span class='hs-varid'>p</span>
<a name="line-370"></a> <span class='hs-conid'>PStar</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>canOnlyMatchNull</span> <span class='hs-varid'>p</span>
<a name="line-371"></a> <span class='hs-conid'>PBound</span> <span class='hs-keyword'>_</span> <span class='hs-layout'>(</span><span class='hs-conid'>Just</span> <span class='hs-num'>0</span><span class='hs-layout'>)</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>True</span>
<a name="line-372"></a> <span class='hs-conid'>PBound</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>canOnlyMatchNull</span> <span class='hs-varid'>p</span>
<a name="line-373"></a> <span class='hs-conid'>PCarat</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>True</span>
<a name="line-374"></a> <span class='hs-conid'>PDollar</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>True</span>
<a name="line-375"></a> <span class='hs-conid'>PNonCapture</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>canOnlyMatchNull</span> <span class='hs-varid'>p</span>
<a name="line-376"></a><span class='hs-comment'>-- PNonEmpty p -> canOnlyMatchNull p -- like PQuest</span>
<a name="line-377"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span><span class='hs-conid'>False</span>
<a name="line-378"></a>
<a name="line-379"></a><span class='hs-comment'>{-
<a name="line-380"></a>
<a name="line-381"></a>-- | If 'cannotMatchNull' returns 'True' then it is known that the
<a name="line-382"></a>-- 'Pattern' will never accept an empty string. If 'cannotMatchNull'
<a name="line-383"></a>-- returns 'False' then it is possible but not definite that the
<a name="line-384"></a>-- 'Pattern' could accept an empty string.
<a name="line-385"></a>cannotMatchNull :: Pattern -> Bool
<a name="line-386"></a>cannotMatchNull pIn =
<a name="line-387"></a> case pIn of
<a name="line-388"></a> PEmpty -> False
<a name="line-389"></a> PGroup _ p -> cannotMatchNull p
<a name="line-390"></a> POr [] -> False
<a name="line-391"></a> POr ps -> all cannotMatchNull ps
<a name="line-392"></a> PConcat [] -> False
<a name="line-393"></a> PConcat ps -> any cannotMatchNull ps
<a name="line-394"></a> PQuest _ -> False
<a name="line-395"></a> PPlus p -> cannotMatchNull p
<a name="line-396"></a> PStar {} -> False
<a name="line-397"></a> PBound 0 _ _ -> False
<a name="line-398"></a> PBound _ _ p -> cannotMatchNull p
<a name="line-399"></a> PCarat _ -> False
<a name="line-400"></a> PDollar _ -> False
<a name="line-401"></a> PNonCapture p -> cannotMatchNull p
<a name="line-402"></a>-- PNonEmpty _ -> False -- like PQuest
<a name="line-403"></a> _ -> True
<a name="line-404"></a>-}</span>
</pre></body>
</html>
