Making regexp AST building linear time rather than quadratic for a{n}

diff --git a/basis/regexp/ast/ast.factor b/basis/regexp/ast/ast.factor
index 1c11ed5c7d58070ba5e51d29d48d2fb605963714..be657227e521a2c522a0adc20ff34bb4e6d6fdc7 100644 (file)
--- a/basis/regexp/ast/ast.factor
+++ b/basis/regexp/ast/ast.factor
@@ -1,7 +1,7 @@
 ! Copyright (C) 2008, 2009 Doug Coleman, Daniel Ehrenberg.
 ! See http://factorcode.org/license.txt for BSD license.
-USING: kernel arrays accessors fry sequences regexp.classes ;
-FROM: math.ranges => [a,b] ;
+USING: kernel arrays accessors fry sequences regexp.classes
+math.ranges math ;
 IN: regexp.ast
 
 TUPLE: negation term ;
@@ -49,10 +49,20 @@ SINGLETONS: unix-lines dotall multiline case-insensitive reversed-regexp ;
     <array> <concatenation> ;
 
 GENERIC: <times> ( term times -- term' )
+
 M: at-least <times>
     n>> swap [ repetition ] [ <star> ] bi 2array <concatenation> ;
+
+: to-times ( term n -- ast )
+    dup zero?
+    [ 2drop epsilon ]
+    [ dupd 1- to-times 2array <concatenation> <maybe> ]
+    if ;
+
 M: from-to <times>
-    [ n>> ] [ m>> ] bi [a,b] swap '[ _ repetition ] map <alternation> ;
+    [ n>> swap repetition ]
+    [ [ m>> ] [ n>> ] bi - to-times ] 2bi
+    2array <concatenation> ;
 
 : char-class ( ranges ? -- term )
     [ <or-class> ] dip [ <not-class> ] when ;