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 compiler.units 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 ) ; inline
  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 ] with-compilation-unit match-index-from ;
 133
 134 M: regexp 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: reverse-regexp compile-regexp ( regexp -- regexp )
 141     t backwards? [ call-next-method ] with-variable ;
 142
 143 DEFER: compile-next-match
 144
 145 : next-initial-word ( i string regexp -- i start end string )
 146     [ compile-next-match ] with-compilation-unit do-next-match ;
 147
 148 : compile-next-match ( regexp -- regexp )
 149     dup '[
 150         dup \ next-initial-word = [
 151             drop _ [ compile-regexp dfa>> def>> ] [ reverse-regexp? ] bi
 152             '[ { array-capacity string regexp } declare _ _ next-match ]
 153             (( i string regexp -- i start end string )) define-temp
 154         ] when
 155     ] change-next-match ;
 156
 157 PRIVATE>
 158
 159 : new-regexp ( string ast options class -- regexp )
 160     [ \ regexp-initial-word \ next-initial-word ] dip boa ; inline
 161
 162 : make-regexp ( string ast -- regexp )
 163     f f <options> regexp new-regexp ;
 164
 165 : <optioned-regexp> ( string options -- regexp )
 166     [ dup parse-regexp ] [ string>options ] bi*
 167     dup on>> reversed-regexp swap member?
 168     [ reverse-regexp new-regexp ]
 169     [ regexp new-regexp ] if ;
 170
 171 : <regexp> ( string -- regexp ) "" <optioned-regexp> ;
 172
 173 <PRIVATE
 174
 175 ! The following two should do some caching
 176
 177 : find-regexp-syntax ( string -- prefix suffix )
 178     {
 179         { "R/ "  "/"  }
 180         { "R! "  "!"  }
 181         { "R\" " "\"" }
 182         { "R# "  "#"  }
 183         { "R' "  "'"  }
 184         { "R( "  ")"  }
 185         { "R@ "  "@"  }
 186         { "R[ "  "]"  }
 187         { "R` "  "`"  }
 188         { "R{ "  "}"  }
 189         { "R| "  "|"  }
 190     } swap [ subseq? not nip ] curry assoc-find drop ;
 191
 192 : take-until ( end lexer -- string )
 193     dup skip-blank [
 194         [ index-from ] 2keep
 195         [ swapd subseq ]
 196         [ 2drop 1+ ] 3bi
 197     ] change-lexer-column ;
 198
 199 : parse-noblank-token ( lexer -- str/f )
 200     dup still-parsing-line? [ (parse-token) ] [ drop f ] if ;
 201
 202 : parsing-regexp ( accum end -- accum )
 203     lexer get [ take-until ] [ parse-noblank-token ] bi
 204     <optioned-regexp> compile-next-match parsed ;
 205
 206 PRIVATE>
 207
 208 : R! CHAR: ! parsing-regexp ; parsing
 209 : R" CHAR: " parsing-regexp ; parsing
 210 : R# CHAR: # parsing-regexp ; parsing
 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
 220 M: regexp pprint*
 221     [
 222         [
 223             [ raw>> dup find-regexp-syntax swap % swap % % ]
 224             [ options>> options>string % ] bi
 225         ] "" make
 226     ] keep present-text ;
 227