basis/regexp/regexp.factor

   1 ! Copyright (C) 2008, 2009 Doug Coleman, Daniel Ehrenberg.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: accessors combinators kernel kernel.private math sequences
   4 sequences.private strings sets assocs make lexer namespaces parser
   5 arrays fry locals regexp.parser splitting sorting regexp.ast
   6 regexp.negation regexp.compiler compiler.units words math.ranges ;
   7 IN: regexp
   8
   9 TUPLE: regexp
  10     { raw read-only }
  11     { parse-tree read-only }
  12     { options read-only }
  13     dfa next-match ;
  14
  15 TUPLE: reverse-regexp < regexp ;
  16
  17 <PRIVATE
  18
  19 M: lookahead question>quot ! Returns ( index string -- ? )
  20     term>> ast>dfa dfa>shortest-word '[ f _ execute ] ;
  21
  22 : <reversed-option> ( ast -- reversed )
  23     "r" string>options <with-options> ;
  24
  25 M: lookbehind question>quot ! Returns ( index string -- ? )
  26     term>> <reversed-option>
  27     ast>dfa dfa>reverse-shortest-word
  28     '[ [ 1 - ] dip f _ execute ] ;
  29
  30 : check-string ( string -- string )
  31     ! Make this configurable
  32     dup string? [ "String required" throw ] unless ;
  33
  34 : match-index-from ( i string regexp -- index/f )
  35     ! This word is unsafe. It assumes that i is a fixnum
  36     ! and that string is a string.
  37     dup dfa>> execute( index string regexp -- i/f ) ; inline
  38
  39 GENERIC: end/start ( string regexp -- end start )
  40 M: regexp end/start drop length 0 ;
  41 M: reverse-regexp end/start drop length 1 - -1 swap ;
  42
  43 PRIVATE>
  44
  45 : matches? ( string regexp -- ? )
  46     [ check-string ] dip
  47     [ end/start ] 2keep
  48     match-index-from
  49     [ = ] [ drop f ] if* ;
  50
  51 <PRIVATE
  52
  53 : search-range ( i string reverse? -- seq )
  54     [ drop -1 ] [ length ] if [a,b] ; inline
  55
  56 :: (next-match) ( i string regexp quot: ( i string regexp -- j ) reverse? -- start end ? )
  57     i string regexp quot call dup
  58     [| j | reverse? [ j i ] [ i j ] if string ] [ drop f f f ] if ; inline
  59
  60 :: next-match ( i string regexp quot: ( i string regexp -- j ) reverse? -- start end ? )
  61     f f f
  62     i string reverse? search-range
  63     [ [ 3drop ] dip string regexp quot reverse? (next-match) dup ] find 2drop ; inline
  64
  65 : do-next-match ( i string regexp -- start end ? )
  66     dup next-match>>
  67     execute( i string regexp -- start end ? ) ; inline
  68
  69 :: (each-match-forward) ( ... i string regexp quot: ( ... start end string -- ... ) -- ... )
  70     i string length <= [
  71         i string regexp do-next-match [| start end |
  72             start end string quot call
  73             start end eq? [ end 1 +  ] [ end ] if
  74             string regexp quot (each-match-forward)
  75         ] [ 2drop ] if
  76     ] when ; inline recursive
  77
  78 :: (each-match-backward) ( ... i string regexp quot: ( ... start end string -- ... ) -- ... )
  79     i -1 >= [
  80         i string regexp do-next-match [| start end |
  81             start 1 + end 1 + string quot call
  82             start end eq? [ start 1 - ] [ start ] if
  83             string regexp quot (each-match-backward)
  84         ] [ 2drop ] if
  85     ] when ; inline recursive
  86
  87 : (each-match) ( ... i string regexp quot: ( ... start end string -- ... ) -- ... )
  88     over reverse-regexp? [ (each-match-backward) ] [ (each-match-forward) ] if ; inline
  89
  90 GENERIC: match-iterator-start ( string regexp -- start )
  91 M: regexp match-iterator-start 2drop 0 ;
  92 M: reverse-regexp match-iterator-start drop length ;
  93
  94 : prepare-match-iterator ( string regexp -- i string regexp )
  95     [ check-string ] dip [ match-iterator-start ] 2keep ; inline
  96
  97 PRIVATE>
  98
  99 : each-match ( ... string regexp quot: ( ... start end string -- ... ) -- ... )
 100     [ prepare-match-iterator ] dip (each-match) ; inline
 101
 102 : map-matches ( ... string regexp quot: ( ... start end string -- ... obj ) -- ... seq )
 103     collector [ each-match ] dip >array ; inline
 104
 105 : all-matching-slices ( string regexp -- seq )
 106     [ <slice-unsafe> ] map-matches ;
 107
 108 : all-matching-subseqs ( string regexp -- seq )
 109     [ subseq ] map-matches ;
 110
 111 : count-matches ( string regexp -- n )
 112     [ 0 ] 2dip [ 3drop 1 + ] each-match ;
 113
 114 <PRIVATE
 115
 116 :: (re-split) ( string regexp quot: ( from to seq -- slice ) -- new-slices )
 117     0 string regexp [| end start end' string |
 118         end' ! leave it on the stack for the next iteration
 119         end start string quot call
 120     ] map-matches
 121     ! Final chunk
 122     swap string length string quot call suffix ; inline
 123
 124 PRIVATE>
 125
 126 :: first-match ( string regexp -- slice/f )
 127     string regexp prepare-match-iterator do-next-match [
 128         regexp reverse-regexp? [ [ 1 + ] bi@ ] when
 129         string <slice-unsafe>
 130     ] [ 2drop f ] if ;
 131
 132 : re-contains? ( string regexp -- ? )
 133     prepare-match-iterator do-next-match [ 2drop ] dip >boolean ;
 134
 135 : re-split ( string regexp -- seq )
 136     [ <slice-unsafe> ] (re-split) ;
 137
 138 : re-replace ( string regexp replacement -- result )
 139     [ [ subseq ] (re-split) ] dip join ;
 140
 141 :: re-replace-with ( string regexp quot: ( slice -- replacement ) -- result )
 142     [
 143         0 string regexp [
 144             drop [ [ string <slice-unsafe> , ] keep ] dip
 145             [ string <slice-unsafe> quot call( x -- x ) , ] keep
 146         ] each-match string [ length ] [ <slice-unsafe> ] bi ,
 147     ] { } make concat ;
 148
 149 <PRIVATE
 150
 151 : get-ast ( regexp -- ast )
 152     [ parse-tree>> ] [ options>> ] bi <with-options> ;
 153
 154 GENERIC: compile-regexp ( regex -- regexp )
 155
 156 : regexp-initial-word ( i string regexp -- i/f )
 157     [ compile-regexp ] with-compilation-unit match-index-from ;
 158
 159 M: regexp compile-regexp ( regexp -- regexp )
 160     dup '[
 161         dup \ regexp-initial-word =
 162         [ drop _ get-ast ast>dfa dfa>word ] when
 163     ] change-dfa ;
 164
 165 M: reverse-regexp compile-regexp ( regexp -- regexp )
 166     t backwards? [ call-next-method ] with-variable ;
 167
 168 DEFER: compile-next-match
 169
 170 : next-initial-word ( i string regexp -- start end string )
 171     [ compile-next-match ] with-compilation-unit do-next-match ;
 172
 173 : compile-next-match ( regexp -- regexp )
 174     dup '[
 175         dup \ next-initial-word = [
 176             drop _ [ compile-regexp dfa>> def>> ] [ reverse-regexp? ] bi
 177             '[ { array-capacity string regexp } declare _ _ next-match ]
 178             ( i string regexp -- start end string ) define-temp
 179         ] when
 180     ] change-next-match ;
 181
 182 PRIVATE>
 183
 184 : new-regexp ( string ast options class -- regexp )
 185     [ \ regexp-initial-word \ next-initial-word ] dip boa ; inline
 186
 187 : make-regexp ( string ast -- regexp )
 188     f f <options> regexp new-regexp ;
 189
 190 : <optioned-regexp> ( string options -- regexp )
 191     [ dup parse-regexp ] [ string>options ] bi*
 192     dup on>> reversed-regexp swap member?
 193     [ reverse-regexp new-regexp ]
 194     [ regexp new-regexp ] if ;
 195
 196 : <regexp> ( string -- regexp ) "" <optioned-regexp> ;
 197
 198 <PRIVATE
 199
 200 : take-until ( lexer -- string )
 201     dup skip-blank [
 202         dupd [
 203             [ CHAR: / -rot index-from ] keep
 204             over [ "Unterminated regexp" throw ] unless
 205             2dup [ 1 - ] dip nth CHAR: \\ =
 206             [ [ [ 1 + ] dip ] when ] keep
 207         ] loop over [ subseq ] dip 1 +
 208     ] change-lexer-column ;
 209
 210 : parse-noblank-token ( lexer -- str/f )
 211     dup still-parsing-line? [ (parse-raw) ] [ drop f ] if ;
 212
 213 : parse-regexp ( accum -- accum )
 214     lexer get [ take-until "\\/" "/" replace ] [ parse-noblank-token ] bi
 215     <optioned-regexp> compile-next-match suffix! ;
 216
 217 PRIVATE>
 218
 219 SYNTAX: R/ parse-regexp ;
 220
 221 USE: vocabs.loader
 222
 223 { "prettyprint" "regexp" } "regexp.prettyprint" require-when