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     [ end/start ] 2keep
  53     [ check-string ] dip
  54     match-index-from
  55     [ swap = ] [ drop f ] if* ;
  56
  57 <PRIVATE
  58
  59 TUPLE: match { i read-only } { j read-only } { seq read-only } ;
  60
  61 : match-slice ( i string quot -- match/f )
  62     [ 2dup ] dip call
  63     [ swap match boa ] [ 2drop f ] if* ; inline
  64
  65 : search-range ( i string reverse? -- seq )
  66     [ drop 0 [a,b] ] [ length [a,b) ] if ; inline
  67
  68 : match>result ( match reverse? -- i start end string )
  69     over [
  70         [ [ i>> ] [ j>> tuck ] [ seq>> ] tri ] dip
  71         [ [ swap [ 1+ ] bi@ ] dip ] when
  72     ] [ 2drop f f f f ] if ; inline
  73
  74 :: next-match ( i string quot reverse? -- i start end string )
  75     i string reverse? search-range
  76     [ string quot match-slice ] map-find drop
  77     reverse? match>result ; inline
  78
  79 : do-next-match ( i string regexp -- i start end string )
  80     dup next-match>>
  81     execute-unsafe( i string regexp -- i start end string ) ;
  82
  83 : next-slice ( i string regexp -- i/f slice/f )
  84     do-next-match
  85     [ slice boa ] [ drop ] if* ; inline
  86
  87 PRIVATE>
  88
  89 TUPLE: match-iterator
  90     { string read-only }
  91     { regexp read-only }
  92     { i read-only }
  93     { value read-only } ;
  94
  95 : iterate ( iterator -- iterator'/f )
  96     dup
  97     [ i>> ] [ string>> ] [ regexp>> ] tri next-slice
  98     [ [ [ string>> ] [ regexp>> ] bi ] 2dip match-iterator boa ]
  99     [ 2drop f ] if* ;
 100
 101 : value ( iterator/f -- value/f )
 102     dup [ value>> ] when ;
 103
 104 : <match-iterator> ( string regexp -- match-iterator )
 105     [ check-string ] dip
 106     2dup end/start nip f
 107     match-iterator boa
 108     iterate ; inline
 109
 110 : all-matches ( string regexp -- seq )
 111     <match-iterator> [ iterate ] follow [ value ] map ;
 112
 113 : count-matches ( string regexp -- n )
 114     all-matches length ;
 115
 116 <PRIVATE
 117
 118 :: split-slices ( string slices -- new-slices )
 119     slices [ to>> ] map 0 prefix
 120     slices [ from>> ] map string length suffix
 121     [ string <slice> ] 2map ;
 122
 123 PRIVATE>
 124
 125 : first-match ( string regexp -- slice/f )
 126     <match-iterator> value ;
 127
 128 : re-contains? ( string regexp -- ? )
 129     first-match >boolean ;
 130
 131 : re-split1 ( string regexp -- before after/f )
 132     dupd first-match [ 1array split-slices first2 ] [ f ] if* ;
 133
 134 : re-split ( string regexp -- seq )
 135     dupd all-matches split-slices ;
 136
 137 : re-replace ( string regexp replacement -- result )
 138     [ re-split ] dip join ;
 139
 140 <PRIVATE
 141
 142 : get-ast ( regexp -- ast )
 143     [ parse-tree>> ] [ options>> ] bi <with-options> ;
 144
 145 GENERIC: compile-regexp ( regex -- regexp )
 146
 147 : regexp-initial-word ( i string regexp -- i/f )
 148     compile-regexp match-index-from ;
 149
 150 : do-compile-regexp ( regexp -- regexp )
 151     dup '[
 152         dup \ regexp-initial-word =
 153         [ drop _ get-ast ast>dfa dfa>word ] when
 154     ] change-dfa ;
 155
 156 M: regexp compile-regexp ( regexp -- regexp )
 157     do-compile-regexp ;
 158
 159 M: reverse-regexp compile-regexp ( regexp -- regexp )
 160     t backwards? [ do-compile-regexp ] with-variable ;
 161
 162 DEFER: compile-next-match
 163
 164 : next-initial-word ( i string regexp -- i start end string )
 165     compile-next-match do-next-match ;
 166
 167 : compile-next-match ( regexp -- regexp )
 168     dup '[
 169         dup \ next-initial-word = [
 170             drop _ [ compile-regexp dfa>> ] [ reverse-regexp? ] bi
 171             '[ _ '[ _ _ execute ] _ next-match ]
 172             (( i string regexp -- i start end string )) simple-define-temp
 173         ] when
 174     ] change-next-match ;
 175
 176 PRIVATE>
 177
 178 : new-regexp ( string ast options class -- regexp )
 179     [ \ regexp-initial-word \ next-initial-word ] dip boa ; inline
 180
 181 : make-regexp ( string ast -- regexp )
 182     f f <options> regexp new-regexp ;
 183
 184 : <optioned-regexp> ( string options -- regexp )
 185     [ dup parse-regexp ] [ string>options ] bi*
 186     dup on>> reversed-regexp swap member?
 187     [ reverse-regexp new-regexp ]
 188     [ regexp new-regexp ] if ;
 189
 190 : <regexp> ( string -- regexp ) "" <optioned-regexp> ;
 191
 192 <PRIVATE
 193
 194 ! The following two should do some caching
 195
 196 : find-regexp-syntax ( string -- prefix suffix )
 197     {
 198         { "R/ "  "/"  }
 199         { "R! "  "!"  }
 200         { "R\" " "\"" }
 201         { "R# "  "#"  }
 202         { "R' "  "'"  }
 203         { "R( "  ")"  }
 204         { "R@ "  "@"  }
 205         { "R[ "  "]"  }
 206         { "R` "  "`"  }
 207         { "R{ "  "}"  }
 208         { "R| "  "|"  }
 209     } swap [ subseq? not nip ] curry assoc-find drop ;
 210
 211 : take-until ( end lexer -- string )
 212     dup skip-blank [
 213         [ index-from ] 2keep
 214         [ swapd subseq ]
 215         [ 2drop 1+ ] 3bi
 216     ] change-lexer-column ;
 217
 218 : parse-noblank-token ( lexer -- str/f )
 219     dup still-parsing-line? [ (parse-token) ] [ drop f ] if ;
 220
 221 : parsing-regexp ( accum end -- accum )
 222     lexer get [ take-until ] [ parse-noblank-token ] bi
 223     <optioned-regexp> compile-next-match parsed ;
 224
 225 PRIVATE>
 226
 227 : R! CHAR: ! parsing-regexp ; parsing
 228 : R" CHAR: " parsing-regexp ; parsing
 229 : R# CHAR: # parsing-regexp ; parsing
 230 : R' CHAR: ' parsing-regexp ; parsing
 231 : R( CHAR: ) parsing-regexp ; parsing
 232 : R/ CHAR: / parsing-regexp ; parsing
 233 : R@ CHAR: @ parsing-regexp ; parsing
 234 : R[ CHAR: ] parsing-regexp ; parsing
 235 : R` CHAR: ` parsing-regexp ; parsing
 236 : R{ CHAR: } parsing-regexp ; parsing
 237 : R| CHAR: | parsing-regexp ; parsing
 238
 239 M: regexp pprint*
 240     [
 241         [
 242             [ raw>> dup find-regexp-syntax swap % swap % % ]
 243             [ options>> options>string % ] bi
 244         ] "" make
 245     ] keep present-text ;
 246