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