Beginnings of lookahead and lookbehind

diff --git a/basis/regexp/ast/ast.factor b/basis/regexp/ast/ast.factor
index b804eacc090d65790d2df8a979b5ae2449393f52..bc808bafca8427ffc78da2f097625b8957da1432 100644 (file)
--- a/basis/regexp/ast/ast.factor
+++ b/basis/regexp/ast/ast.factor
@@ -16,7 +16,7 @@ C: <at-least> at-least
 TUPLE: tagged-epsilon tag ;
 C: <tagged-epsilon> tagged-epsilon
 
-CONSTANT: epsilon T{ tagged-epsilon }
+CONSTANT: epsilon T{ tagged-epsilon { tag t } }
 
 TUPLE: concatenation first second ;
 

diff --git a/basis/regexp/classes/classes-tests.factor b/basis/regexp/classes/classes-tests.factor
index 5eac0ea352710f0515a0de2439695d67170d79f8..8d660ffa3083fbbc4aa029e3c8ba0f168a2c938f 100644 (file)
--- a/basis/regexp/classes/classes-tests.factor
+++ b/basis/regexp/classes/classes-tests.factor
@@ -21,6 +21,7 @@ IN: regexp.classes.tests
 [ 1 ] [ 1 <not-class> <not-class> ] unit-test
 [ 1 ] [ { 1 1 } <and-class> ] unit-test
 [ 1 ] [ { 1 1 } <or-class> ] unit-test
+[ t ] [ { t t } <or-class> ] unit-test
 [ T{ primitive-class { class letter-class } } ] [ letter-class <primitive-class> dup 2array <and-class> ] unit-test
 [ T{ primitive-class { class letter-class } } ] [ letter-class <primitive-class> dup 2array <or-class> ] unit-test
 [ T{ or-class { seq { 2 3 1 } } } ] [ { 1 2 } <or-class> { 2 3 } <or-class> 2array <or-class> ] unit-test

diff --git a/basis/regexp/classes/classes.factor b/basis/regexp/classes/classes.factor
index 33652f760671fdc5251fef5e3fdf84daecf3f44e..c4673cf26bba4cdb06946299932d8234a470478e 100644 (file)
--- a/basis/regexp/classes/classes.factor
+++ b/basis/regexp/classes/classes.factor
@@ -140,7 +140,7 @@ GENERIC: combine-or ( class1 class2 -- combined ? )
 M: object combine-or replace-if-= ;
 
 M: t combine-or
-    drop f ;
+    nip t ;
 
 M: f combine-or
     drop t ;

diff --git a/basis/regexp/dfa/dfa-tests.factor b/basis/regexp/dfa/dfa-tests.factor
index b6ce13c723f01134777c178a3d6d37d0bd0f7696..129a639929eeaaf2b9037ee9895ee76ca090bf5b 100644 (file)
--- a/basis/regexp/dfa/dfa-tests.factor
+++ b/basis/regexp/dfa/dfa-tests.factor
@@ -1,5 +1,3 @@
 USING: regexp.dfa tools.test ;
 IN: regexp.dfa.tests
 
-[ [ ] [ ] while-changes ] must-infer
-

diff --git a/basis/regexp/dfa/dfa.factor b/basis/regexp/dfa/dfa.factor
index 01e3e01119ddb377d23eb9f299ea68cf27a85ea8..8839e5348540b886a5b08fa3582f85dac9f1d43e 100644 (file)
--- a/basis/regexp/dfa/dfa.factor
+++ b/basis/regexp/dfa/dfa.factor
@@ -2,35 +2,84 @@
 ! See http://factorcode.org/license.txt for BSD license.
 USING: accessors arrays assocs combinators fry kernel locals
 math math.order regexp.nfa regexp.transition-tables sequences
-sets sorting vectors regexp.ast ;
+sets sorting vectors regexp.ast regexp.classes ;
 IN: regexp.dfa
 
-:: (while-changes) ( obj quot: ( obj -- obj' ) comp: ( obj -- key ) old-key -- obj )
-    obj quot call :> new-obj
-    new-obj comp call :> new-key
-    new-key old-key =
-    [ new-obj ]
-    [ new-obj quot comp new-key (while-changes) ]
-    if ; inline recursive
-
-: while-changes ( obj quot pred -- obj' )
-    3dup nip call (while-changes) ; inline
-
 : find-delta ( states transition nfa -- new-states )
     transitions>> '[ _ swap _ at at ] gather sift ;
 
-: (find-epsilon-closure) ( states nfa -- new-states )
-    epsilon swap find-delta ;
+TUPLE: condition question yes no ;
+C: <condition> condition
+
+:: epsilon-loop ( state table nfa question -- )
+    state table at :> old-value
+    old-value question 2array <or-class> :> new-question
+    new-question old-value = [
+        new-question state table set-at
+        state nfa transitions>> at
+        [ drop tagged-epsilon? ] assoc-filter
+        [| trans to |
+            to [
+                table nfa
+                trans tag>> new-question 2array <and-class>
+                epsilon-loop
+            ] each
+        ] assoc-each
+    ] unless ;
+
+GENERIC# replace-question 2 ( class from to -- new-class )
+
+M: object replace-question
+    [ [ = ] keep ] dip swap ? ;
+
+: replace-compound ( class from to -- seq )
+    [ seq>> ] 2dip '[ _ _ replace-question ] map ;
+
+M: and-class replace-question
+    replace-compound <and-class> ;
+
+M: or-class replace-question
+    replace-compound <or-class> ;
+
+: answer ( table question answer -- new-table )
+    '[ _ _ replace-question ] assoc-map
+    [ nip ] assoc-filter ;
+
+DEFER: make-condition
+
+: (make-condition) ( table questions question -- condition )
+    [ 2nip ]
+    [ swap [ t answer ] dip make-condition ]
+    [ swap [ f answer ] dip make-condition ] 3tri
+    <condition> ;
+
+: make-condition ( table questions -- condition )
+    [ keys ] [ unclip (make-condition) ] if-empty ;
+
+GENERIC: class>questions ( class -- questions )
+: compound-questions ( class -- questions ) seq>> [ class>questions ] gather ;
+M: or-class class>questions compound-questions ;
+M: and-class class>questions compound-questions ;
+M: object class>questions 1array ;
+
+: table>condition ( table -- condition )
+    ! This is wrong, since actually an arbitrary and-class or or-class can be used
+    dup
+    values <or-class> class>questions t swap remove
+    make-condition ;
+
+: epsilon-table ( states nfa -- table )
+    [ H{ } clone tuck ] dip
+    '[ _ _ t epsilon-loop ] each ;
 
-: find-epsilon-closure ( states nfa -- new-states )
-    '[ dup _ (find-epsilon-closure) union ] [ length ] while-changes
-    natural-sort ;
+: find-epsilon-closure ( states nfa -- dfa-state )
+    epsilon-table table>condition ;
 
 : find-closure ( states transition nfa -- new-states )
     [ find-delta ] keep find-epsilon-closure ;
 
 : find-start-state ( nfa -- state )
-    [ start-state>> 1vector ] keep find-epsilon-closure ;
+    [ start-state>> 1array ] keep find-epsilon-closure ;
 
 : find-transitions ( dfa-state nfa -- next-dfa-state )
     transitions>>
@@ -49,7 +98,7 @@ IN: regexp.dfa
         [| trans |
             state trans nfa find-closure :> new-state
             new-state visited-states new-states add-todo-state
-            state new-state trans dfa add-transition
+            state new-state trans dfa set-transition
         ] each
         nfa dfa new-states visited-states new-transitions
     ] if-empty ;

diff --git a/basis/regexp/minimize/minimize-tests.factor b/basis/regexp/minimize/minimize-tests.factor
index ece7c8fd7c5832c100b85b5cad3867ea8b970a5c..c5564caa558ca6f0fa2096467b4e13136898c67e 100644 (file)
--- a/basis/regexp/minimize/minimize-tests.factor
+++ b/basis/regexp/minimize/minimize-tests.factor
@@ -47,3 +47,5 @@ IN: regexp.minimize.tests
         { final-states H{ { 3 3 } { 6 6 } } }
     } combine-states
 ] unit-test
+
+[ [ ] [ ] while-changes ] must-infer

diff --git a/basis/regexp/minimize/minimize.factor b/basis/regexp/minimize/minimize.factor
index c88c2a850be76f4a77dbadcf7518ef534ff607b8..b51faff3711fb9b8c5bed2dfb4df4b983f200396 100644 (file)
--- a/basis/regexp/minimize/minimize.factor
+++ b/basis/regexp/minimize/minimize.factor
@@ -8,7 +8,7 @@ IN: regexp.minimize
 : number-transitions ( transitions numbering -- new-transitions )
     dup '[
         [ _ at ]
-        [ [ first _ at ] assoc-map ] bi*
+        [ [ _ at ] assoc-map ] bi*
     ] assoc-map ;
 
 : table>state-numbers ( table -- assoc )
@@ -66,6 +66,17 @@ IN: regexp.minimize
     <reversed>
     >hashtable ;
 
+:: (while-changes) ( obj quot: ( obj -- obj' ) comp: ( obj -- key ) old-key -- obj )
+    obj quot call :> new-obj
+    new-obj comp call :> new-key
+    new-key old-key =
+    [ new-obj ]
+    [ new-obj quot comp new-key (while-changes) ]
+    if ; inline recursive
+
+: while-changes ( obj quot pred -- obj' )
+    3dup nip call (while-changes) ; inline
+
 : state-classes ( transition-table -- synonyms )
     [ initialize-partitions ] keep
     '[ _ partition-more ] [ assoc-size ] while-changes

diff --git a/basis/regexp/nfa/nfa.factor b/basis/regexp/nfa/nfa.factor
index 68f7761394c93ca1df45316e4928eff23831b36b..302b1ebc55385d13614ab14b06f998857306dbac 100644 (file)
--- a/basis/regexp/nfa/nfa.factor
+++ b/basis/regexp/nfa/nfa.factor
@@ -55,8 +55,12 @@ M:: star nfa-node ( node -- start end )
     s1 s3 epsilon-transition
     s2 s3 ;
 
+GENERIC: modify-epsilon ( tag -- newtag )
+
+M: object modify-epsilon ;
+
 M: tagged-epsilon nfa-node
-    add-simple-entry ;
+    clone [ modify-epsilon ] change-tag add-simple-entry ;
 
 M: concatenation nfa-node ( node -- start end )
     [ first>> ] [ second>> ] bi

diff --git a/basis/regexp/parser/parser.factor b/basis/regexp/parser/parser.factor
index ed0762cc3ab39bb61b3f46c870345f1178ecc39d..18aef7fa49348feceb13a2fb0dd055856df1a772 100644 (file)
--- a/basis/regexp/parser/parser.factor
+++ b/basis/regexp/parser/parser.factor
@@ -137,10 +137,10 @@ Parenthized = "?:" Alternation:a => [[ a ]]
                 => [[ a on off parse-options <with-options> ]]
             | "?#" [^)]* => [[ f ]]
             | "?~" Alternation:a => [[ a <negation> ]]
-            | "?=" Alternation:a => [[ a <lookahead> ]]
-            | "?!" Alternation:a => [[ a <negation> <lookahead> ]]
-            | "?<=" Alternation:a => [[ a <lookbehind> ]]
-            | "?<!" Alternation:a => [[ a <negation> <lookbehind> ]]
+            | "?=" Alternation:a => [[ a <lookahead> <tagged-epsilon> ]]
+            | "?!" Alternation:a => [[ a <negation> <lookahead> <tagged-epsilon> ]]
+            | "?<=" Alternation:a => [[ a <lookbehind> <tagged-epsilon> ]]
+            | "?<!" Alternation:a => [[ a <negation> <lookbehind> <tagged-epsilon> ]]
             | Alternation
 
 Element = "(" Parenthized:p ")" => [[ p ]]

diff --git a/basis/regexp/transition-tables/transition-tables.factor b/basis/regexp/transition-tables/transition-tables.factor
index 2b0a5c2bcc473f77de2ae11ca9d848639275eaea..2fad7451b0eb0a3db12f4d449740e14bda0ea197 100644 (file)
--- a/basis/regexp/transition-tables/transition-tables.factor
+++ b/basis/regexp/transition-tables/transition-tables.factor
@@ -14,11 +14,20 @@ TUPLE: transition-table transitions start-state final-states ;
 : maybe-initialize-key ( key hashtable -- )
     2dup key? [ 2drop ] [ [ H{ } clone ] 2dip set-at ] if ;
 
-:: set-transition ( from to obj hash -- )
+:: (set-transition) ( from to obj hash -- )
+    to hash maybe-initialize-key
+    from hash at
+    [ [ to obj ] dip set-at ]
+    [ to obj associate from hash set-at ] if* ;
+
+: set-transition ( from to obj transition-table -- )
+    transitions>> (set-transition) ;
+
+:: (add-transition) ( from to obj hash -- )
     to hash maybe-initialize-key
     from hash at
     [ [ to obj ] dip push-at ]
     [ to 1vector obj associate from hash set-at ] if* ;
 
 : add-transition ( from to obj transition-table -- )
-    transitions>> set-transition ;
+    transitions>> (add-transition) ;