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 :: (next-match) ( i string regexp quot: ( i string regexp -- j ) reverse? -- i start end ? )
  54     i string regexp quot call dup [| j |
  55         j i j
  56         reverse? [ swap [ 1 + ] bi@ ] when
  57         string
  58     ] [ drop f f f f ] if ; inline
  59
  60 : search-range ( i string reverse? -- seq )
  61     [ drop dup 1 + -1 ] [ length 1 ] if range boa ; inline
  62
  63 :: next-match ( i string regexp quot: ( i string regexp -- j ) reverse? -- i start end ? )
  64     f f f f
  65     i string reverse? search-range
  66     [ [ 2drop 2drop ] dip string regexp quot reverse? (next-match) dup ] find 2drop ; inline
  67
  68 : do-next-match ( i string regexp -- i start end ? )
  69     dup next-match>>
  70     execute( i string regexp -- i start end ? ) ; inline
  71
  72 :: (each-match) ( i string regexp quot: ( start end string -- ) -- )
  73     i string regexp do-next-match [| i' start end |
  74         start end string quot call
  75         i' string regexp quot (each-match)
  76     ] [ 3drop ] if ; inline recursive
  77
  78 : prepare-match-iterator ( string regexp -- i string regexp )
  79     [ check-string ] dip [ end/start nip ] 2keep ; inline
  80
  81 PRIVATE>
  82
  83 : each-match ( string regexp quot: ( start end string -- ) -- )
  84     [ prepare-match-iterator ] dip (each-match) ; inline
  85
  86 : map-matches ( string regexp quot: ( start end string -- obj ) -- seq )
  87     collector [ each-match ] dip >array ; inline
  88
  89 : all-matching-slices ( string regexp -- seq )
  90     [ slice boa ] map-matches ;
  91
  92 : all-matching-subseqs ( string regexp -- seq )
  93     [ subseq ] map-matches ;
  94
  95 : count-matches ( string regexp -- n )
  96     [ 0 ] 2dip [ 3drop 1 + ] each-match ;
  97
  98 <PRIVATE
  99
 100 :: (re-split) ( string regexp quot -- new-slices )
 101     0 string regexp [| end start end' string |
 102         end' ! leave it on the stack for the next iteration
 103         end start string quot call
 104     ] map-matches
 105     ! Final chunk
 106     swap string length string quot call suffix ; inline
 107
 108 PRIVATE>
 109
 110 : first-match ( string regexp -- slice/f )
 111     [ prepare-match-iterator do-next-match ] [ drop ] 2bi
 112     '[ _ slice boa nip ] [ 3drop f ] if ;
 113
 114 : re-contains? ( string regexp -- ? )
 115     prepare-match-iterator do-next-match [ 3drop ] dip >boolean ;
 116
 117 : re-split ( string regexp -- seq )
 118     [ slice boa ] (re-split) ;
 119
 120 : re-replace ( string regexp replacement -- result )
 121     [ [ subseq ] (re-split) ] dip join ;
 122
 123 <PRIVATE
 124
 125 : get-ast ( regexp -- ast )
 126     [ parse-tree>> ] [ options>> ] bi <with-options> ;
 127
 128 GENERIC: compile-regexp ( regex -- regexp )
 129
 130 : regexp-initial-word ( i string regexp -- i/f )
 131     [ compile-regexp ] with-compilation-unit match-index-from ;
 132
 133 M: regexp compile-regexp ( regexp -- regexp )
 134     dup '[
 135         dup \ regexp-initial-word =
 136         [ drop _ get-ast ast>dfa dfa>word ] when
 137     ] change-dfa ;
 138
 139 M: reverse-regexp compile-regexp ( regexp -- regexp )
 140     t backwards? [ call-next-method ] with-variable ;
 141
 142 DEFER: compile-next-match
 143
 144 : next-initial-word ( i string regexp -- i start end string )
 145     [ compile-next-match ] with-compilation-unit do-next-match ;
 146
 147 : compile-next-match ( regexp -- regexp )
 148     dup '[
 149         dup \ next-initial-word = [
 150             drop _ [ compile-regexp dfa>> def>> ] [ reverse-regexp? ] bi
 151             '[ { array-capacity string regexp } declare _ _ next-match ]
 152             (( i string regexp -- i start end string )) define-temp
 153         ] when
 154     ] change-next-match ;
 155
 156 PRIVATE>
 157
 158 : new-regexp ( string ast options class -- regexp )
 159     [ \ regexp-initial-word \ next-initial-word ] dip boa ; inline
 160
 161 : make-regexp ( string ast -- regexp )
 162     f f <options> regexp new-regexp ;
 163
 164 : <optioned-regexp> ( string options -- regexp )
 165     [ dup parse-regexp ] [ string>options ] bi*
 166     dup on>> reversed-regexp swap member?
 167     [ reverse-regexp new-regexp ]
 168     [ regexp new-regexp ] if ;
 169
 170 : <regexp> ( string -- regexp ) "" <optioned-regexp> ;
 171
 172 <PRIVATE
 173
 174 ! The following two should do some caching
 175
 176 : find-regexp-syntax ( string -- prefix suffix )
 177     {
 178         { "R/ "  "/"  }
 179         { "R! "  "!"  }
 180         { "R\" " "\"" }
 181         { "R# "  "#"  }
 182         { "R' "  "'"  }
 183         { "R( "  ")"  }
 184         { "R@ "  "@"  }
 185         { "R[ "  "]"  }
 186         { "R` "  "`"  }
 187         { "R{ "  "}"  }
 188         { "R| "  "|"  }
 189     } swap [ subseq? not nip ] curry assoc-find drop ;
 190
 191 : take-until ( end lexer -- string )
 192     dup skip-blank [
 193         [ index-from ] 2keep
 194         [ swapd subseq ]
 195         [ 2drop 1 + ] 3bi
 196     ] change-lexer-column ;
 197
 198 : parse-noblank-token ( lexer -- str/f )
 199     dup still-parsing-line? [ (parse-token) ] [ drop f ] if ;
 200
 201 : parsing-regexp ( accum end -- accum )
 202     lexer get [ take-until ] [ parse-noblank-token ] bi
 203     <optioned-regexp> compile-next-match suffix! ;
 204
 205 PRIVATE>
 206
 207 SYNTAX: R! CHAR: ! parsing-regexp ;
 208 SYNTAX: R" CHAR: " parsing-regexp ;
 209 SYNTAX: R# CHAR: # parsing-regexp ;
 210 SYNTAX: R' CHAR: ' parsing-regexp ;
 211 SYNTAX: R( CHAR: ) parsing-regexp ;
 212 SYNTAX: R/ CHAR: / parsing-regexp ;
 213 SYNTAX: R@ CHAR: @ parsing-regexp ;
 214 SYNTAX: R[ CHAR: ] parsing-regexp ;
 215 SYNTAX: R` CHAR: ` parsing-regexp ;
 216 SYNTAX: R{ CHAR: } parsing-regexp ;
 217 SYNTAX: R| CHAR: | parsing-regexp ;
 218
 219 USING: vocabs vocabs.loader ;
 220
 221 "prettyprint" vocab [
 222     "regexp.prettyprint" require
 223 ] when