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